Space-Time Tradeoffs for Spatial Conjunctive Queries

Aryan Esmailpour, Xiao Hu, Stavros Sintos · 2025

Read Space-Time Tradeoffs for Spatial Conjunctive Queries by Aryan Esmailpour, Xiao Hu, Stavros Sintos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10050.txt.

Introduction

Aryan Esmailpour and 2 co-authors map the unavoidable trade between memory and speed for spatial questions over joined data in a 2025 database theory paper. A conjunctive query first combines tables, and users then ask spatial things about the outcome: is anything in this box, how many points fall there, what sits nearest. Such questions power analytics from attribute filtering to counting shapes inside temporal graphs.

Known indexes either answer slowly or balloon to the size of the full result list, neither acceptable at scale. The authors prove lower bounds that fence the whole trade-off for star-shaped and path-shaped queries, showing exactly how answer time and storage must relate. Any future index for spatial conjunctive search now has a proven frontier it cannot cross, and a target to aim at.

Catalog record

CREATORAryan Esmailpour, Xiao Hu, Stavros Sintos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-10050

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Space-Time Tradeoffs for Spatial Conjunctive Queries Aryan Esmailpour, Xiao Hu, Stavros Sintos Abstract . Given a conjunctive query and a database instance, we aim to develop an index that can efficiently answer spatial queries on the results of a conjunctive query. We are interested in some commonly used spatial queries, such as range emptiness, range count, and nearest neighbor queries. These queries have essential applications in data analytics, such as filtering relational data based on attribute ranges and temporal graph analysis for counting graph structures like stars, paths, and cliques. Furthermore, this line of research can accelerate relational algorithms that incorporate spatial queries in their workflow, such as relational clustering. Known approaches either have to spend O ~ ​ ( N ) \tilde{O}(N) query time or use space as large as the number of query results, which are inefficient or unrealistic to employ in practice. Hence, we aim to construct an index that answers spatial conjunctive queries in both time- and space-efficient ways. In this paper, we establish lower bounds on the tradeoff between answering time and space usage. For k k -star (resp. k k -path) queries, we show that any index for range emptiness, range counting or nearest neighbor queries with T T answering time requires Ω ⁡ ( N + N k T k ) \Omega\left(N+\frac{N^{k}}{T^{k}}\right) (resp. Ω ⁡ ( N + N 2 T 2 / ( k − 1 ) ) \Omega\left(N+\frac{N^{2}}{T^{2/(k-1)}}\right) ) space. Then, we construct optimal indexes for answering range emptiness and range counting problems over k k -star and k k -path queries. Extending this result, we build an index for hierarchical queries. By resorting to the generalized hypertree decomposition, we can extend our index to arbitrary conjunctive queries for supporting spatial conjunctive queries. Finally, we show how our new indexes can be used to improve the running time of known algorithms in the relational setting. 1. Introduction In the digital age, tera-bytes of data are generated every second. A large amount of raw data would be useless if we could not analyze them to extract valuable knowledge. One standard way to extract knowledge is by asking data queries on the input data. A data analyst might ask several queries to an index built on the entire or a subset of the input data set. In relational databases, data is gathered and stored across various tables, where each row corresponds to a tuple and each column to an attribute. Two tuples stored in different tables can be joined if their shared attributes are equal. This setting is quite common in practical database management systems (DBMS) since more than 70% of DBMS are relational and more than 65% of the data sets in learning tasks are relational data ( kaggle ; link1 ) . Spatial conjunctive queries (SCQ) are spatial queries defined on the results of a conjunctive query (CQ) over relational data. The most common spatial queries include range emptiness, range counting, and nearest neighbor queries. Due to the importance and ubiquitousness of relational data and spatial queries, SCQs have significant applications in several domains, such as geographic information systems, social networks, and temporal graph analysis. Example 1.1. A crypto exchange startup has a table \mathsf{SellOffer}(\mathsf{sellerID},\mathsf{CSS},\mathsf{currency}) for all selling offers, containing the seller’s id, seller’s credit score, and the currency the seller wants to sell (bitcoin, Ethereum, etc.). It also contains a table for all buyers \mathsf{Buyer}(\mathsf{buyerID},\mathsf{CSB},\mathsf{currency}) that contains the buyer’s id, buyer’s credit score, and the currency the buyer will use to pay. Notice that each seller can make multiple offers, and each buyer might be interested in multiple offers. The startup wants to support a Nearest Neighbor classifier on the pairs (\mathsf{CSS},\mathsf{CSB}) , where the credit score of a buyer is paired with the credit score of a seller if the buyer and the seller are interested in the same currency. The startup aims to construct an index for nearest neighbor queries such that, given a query point (x,y) , the goal is to find the nearest neighbor in \pi_{\mathsf{CSS},\mathsf{CSB}}(\mathsf{SellOffer}\Join\mathsf{Buyer}) ), where \pi is the projection operation, and \Join is the join operation. Example 1.2. Let G(V,E) be a graph representing a social network with |V| users and N=|E| edges representing the friendships between the users. Every user u is associated with a social score, indicating their performance on social media ( linkHookle ) . A team of researchers aims to count the number of 3 -star user-patterns where the center node has high score and the rest of nodes have low score (nodes u,v,w,z form a 3 -star with center u , if v,w,z are all connected to u ) to understand how the social network influences user interactions. More formally, let R(\mathsf{userA},\mathsf{userB}) be a relation that has a tuple for each edge (u,v)\in E . Furthermore, let S(\mathsf{userA},\mathsf{score}) be a relation that has a tuple for each node of the graph along with their social score. The researchers aim to construct an index such that given a query rectangle [x_{l},x_{r}]\times[y_{l},y_{r}]\times[z_{l},z_{r}]\times[w_{l},w_{r}] (a rectangle contains one interval for every attribute) the goal is to count the number of tuples in R(A_{1},B)\Join R(A_{2},B)\Join R(A_{3},B)\Join\sigma_{x_{l}\leq C_{1}\leq x_{r}}(S(A_{1},C_{1}))\Join\sigma_{y_{l}\leq C_{2}\leq y_{r}}(S(A_{2},C_{2}))\Join\sigma_{z_{l}\leq C_{3}\leq z_{r}}(S(A_{3},C_{3}))\Join\sigma_{w_{l}\leq C_{4}\leq w_{r}}(S_{4}(B,C_{4})) , where \sigma is the selection operation. Interestingly, in addition to all their real applications, SCQs play a key role in optimization problems over relational data. For example, Agarwal et al. ( agarwal2025computing ) , designed efficient algorithms to find a diverse set on the results of a join (or conjunctive) query in relational data. In their algorithms, they repeatedly use an oracle to count the number of results of a conjunctive query that lie in a query rectangle and an oracle to compute nearest neighbor queries on the results of a conjunctive query. Furthermore, Esmailpour and Sintos ( esmailpour2025improved ) designed efficient algorithms for k -means and k -median clustering on the results of a join query in relational data, using similar spatial oracles. In both papers, the authors constructed indexes with O(N) query time to model the required spatial oracles. There are two main ways to handle SCQs. For range emptiness or range counting queries, given a query hyper-rectangle, one approach ( agarwal2025computing ; esmailpour2025improved ) is to filter out tuples from the input databases that do not satisfy the linear constraints and then run a standard join algorithm on the remaining tuples. While the space used is only O(N) , the query time of this approach is \Omega(N) (such as Yannakakis algorithm ( yannakakis1981algorithms ) ) to count the number of join results of an acyclic query). Similarly, for nearest neighbor queries, the indexes constructed in ( deep2022ranked ; deep2021ranked ; tziavelis2020optimal ) can be used as described in ( agarwal2025computing ) to compute the nearest neighbor of a query point q in O(N) time for join (or conjunctive) queries using O(N) space. The other approach is first to materialize all join results and then construct a geometric index (for example, a range tree ( de1997computational ) for range counting or quadtree ( finkel1974quad ) for approximate nearest neighbor queries) on the join results. While the query time on these indexes is only \tilde{O}(1) (we use \tilde{O} notation to hide {\textsf{polylog}}(n) factors) the space usage is

Read the complete text