acceptodds
Under review as a conference paper at ICLR 2027

Learning-Augmented Range Search

Abstract

Multidimensional range search underlies spatial databases, geographic information systems, and location-based services, where queries often concentrate on a few popular regions. Standard structures such as skip quadtrees provide efficient worst-case guarantees but do not exploit this recurring demand to accelerate common queries. Workload predictions offer an opportunity to reduce search costs, provided that performance remains reliable when predictions are inaccurate or query patterns change. We introduce LASQ, a learning-augmented skip quadtree that combines these benefits. The key idea is to predict the frequencies of critical cubes, the quadtree cells whose searches dominate the cost of answering a range query, and make frequently needed cubes easier to reach. For fixed dimension and approximation parameter , LASQ correctly answers -approximate weighted range-sum queries with expected cost , averaged over the query distribution. Here, is an analogue of cross-entropy for the true and predicted critical-cube frequencies. Accurate predictions yield the corresponding entropy-like bound, while every query takes expected time regardless of prediction accuracy. The structure uses expected space and requires expected preprocessing time. Experiments on real and synthetic spatial data demonstrate substantial reductions in the cubes examined per query over the standard skip quadtree with accurate predictions, alongside resilience to prediction errors.

Primary area:
optimization
Keywords:
range search, learning augmented data structure, robustness, frequency prediction

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_d4NjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

In this paper, the authors builds the learning-augmented skip quadtree structure (LASQ), which can make some frequently used regions to be easy for searching in this structure. Experimental results on some real and synthetic datasets have shown that using LASQ can reduce the number of cubes examined per query.

Critical strengths

S1: The technical contribution of this paper sounds to be very solid. The authors have provided significant theoretical analysis for showing how this structure can achieve low time complexity with accuracy guarantee.

S2: Developing a new indexing structure that can improve the range search is very important.

Critical weaknesses

W1: There is a lack of experimental evaluation for those competitors, including those papers in learned index structures. Although the authors mention that they cannot provide the worst-case query guarantees, the authors should at least show why their method can practically achieve better performance compared with these index structures (as they are the representative approach in the literature).

W2: The authors tend to use some small-scale datasets (at most 10^5-scale) for illustrating the performance, which is not acceptable. Nowadays, many large-scale location datasets are available. For example, Ref. [a] has already adopted the 200 million OSM point dataset for conducting experimental evaluation. Therefore, it is not meaningful to simply use small-scale datasets for conducting experiments.

[a] Learned Index: A Comprehensive Experimental Evaluation. VLDB 2023.

W3: The presentation is very hard to follow. The authors provide many definitions in this paper. However, many definitions have not been used (or referred) in the later part of the paper. Therefore, I just wonder why the authors need to write these definitions. With many definitions and unclear connection, it is very hard for readers to understand the idea of this work.

Questions for authors

Q1: Can the authors compare some competitors in some learned index structures with this method?

Q2: Can the authors use some large-scale datasets for conducting the experiments?

Q3: Can the authors comment for why it is necessary to use many definitions in this paper?

3 comments
AuthorsOpenReview ↗

Response to d4Nj on learned-index comparisons, scalability, and presentation

Thank you for your careful reading and thoughtful comments. We appreciate your recognition of the technical contribution and the importance of improving multidimensional range search. Below, we address your questions using the revised paper’s C++ comparisons with learned indexes, its evaluation on larger datasets, and its new roadmap connecting the definitions to the main theorem.

W1/Q1 (learned indexes). Flood, LISA, and Tsunami answer only one kind of query, axis-aligned boxes, while LASQ handles balls and, more generally, any convex range (Theorem 19). To answer this question, we added Appendix C.3, which compares them with LASQ on the queries they all support, squares. Time per query in µs (Tables 8 and 9):

SquaresFloodLISATsunamiLASQ
OSM Michigan, default size0.4104.830.1410.439
OSM Michigan, query size ×10,00037,14931,7301072.09
Deep forest, 10M points20,46417,87016.71.52

To answer your question directly: LASQ is not faster everywhere. On small squares, Tsunami is the fastest and Flood is about as fast as LASQ. LASQ is faster on larger ranges, on deep data, and under a workload shift. As the query size grows to 10,000 times the default, the time per query of Flood, LISA and Tsunami grows by roughly three to five orders of magnitude, while that of LASQ remains below 5 µs at every size (Tables 8 and 9, Figure 11), consistent with its O(log⁡n)O(\log n) expected query time, which does not depend on the number of points in the range (Theorem 12). On the deep forest, LASQ is 11 to 13,668 times faster than the three. Finally, LASQ is robust to wrong predictions, and Tsunami, which also learns from queries, is not: trained on queries with Zipf exponent 3 or 10 and tested at the default 1.5, Tsunami becomes up to 20.5× and 4,028× slower than LASQ (Table 10), while LASQ, trained on the same queries, stays within 47% of its time without the shift. Appendix C.3 gives the results on all datasets and query sizes, including 3D data (Tables 8 and 9, Figures 10–12), and the full workload shift (Table 10, Figure 13).

W2/Q2 (large-scale data). For this question, we replaced the datasets with much larger ones: all 44.1M OpenStreetMap nodes of Michigan, the full Gowalla set (1.26M points), a 3D LiDAR scan of 20.1M points, and the deep forest up to 10M points (Table 3). On OSM Michigan, LASQ builds in 11.4 s, uses 79 bytes per point, and answers a query in 0.46 µs, against 11.2 s, 102 bytes, and 1.02 µs for the skip quadtree (Tables 4, 11, and 12).

As for [a], it studies one-dimensional learned indexes, and its 200M OSM keys are cell IDs queried by (one-dimensional) intervals. Existing multidimensional benchmarks are smaller: the largest real dataset in the survey of Liu et al. (VLDB J. 2025) has 63M OSM points, so our 44.1M benchmark is on the same scale. Appendix C.1 describes every dataset and the measurement protocol (Tables 2 and 3), and Appendix C.4 gives the build time and memory on each (Tables 11 and 12).

W3/Q3 (why so many definitions). To address this question, we added a paragraph at the start of Section 3, "How the definitions fit together", that walks from a query to the main theorem and names the result that uses each definition, and a table, Table 13 in Appendix E, that lists every notion with where it is defined and first used. We also moved two technical definitions out of the main text, which now has six definitions instead of eight: the definition of quadrants and interesting cubes is now part of the text of Section 2.2, and the formal definition of QiQ_i as a rooted tree moved to Appendix A.5 (Definition 31), with a one-sentence description left in Section 3.3. Briefly: Definitions 3–4 fix what a query computes, and the slack of the annulus is what allows fast queries in linear space. Definition 5 is the in/out/stabbing test that Algorithm 1 applies. Definition 6 marks the critical cubes, where a query has to split, and a query has only a constant number of critical stabbing cubes (Lemma 13). Definition 7 is what we predict, the critical-stabbing frequencies, whose sum is bounded (Lemma 14) and which can be learned from a query log (Theorem 10). The frequency classes and promotion depths turn these predictions into levels (Lemmas 15 and 16), and Definition 11 builds the levels on the compressed quadtree, searchable in O(n)O(n) space (Lemmas 38 and 43). Theorem 12 puts these steps together. The new paragraph of Section 3 gives this chain in full, and Table 13 can serve as a reference while reading Sections 2–4.

Reviewer_d4NjOpenReview ↗

Reply to the Rebuttals

I think that the authors have addressed my comments regarding the W1/Q1 and W2/Q2. But I still think that the authors need to clearly revise the manuscript to enhance the readibility of this paper. Overall, I think the scores reflect what I think for this paper.

Dear Reviewer,

Thank you for revisiting our rebuttal and revised manuscript. We are pleased that the additional experiments and comparisons have addressed your concerns regarding W1/Q1 and W2/Q2.

We also appreciate your continued concern about readability. We have already made several changes to clarify the structure and connections between definitions, and we will continue refining the exposition in the final version.

Thank you again for your constructive feedback and consideration.

Reviewer_uChuOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LASQ, a learning-augmented skip quadtree for multidimensional approximate range search. LASQ predicts the frequencies of critical cubes involved in range queries and uses these predictions to construct a hierarchy that prioritizes frequently accessed regions. The authors establish theoretical guarantees for consistency and robustness, achieving an expected query cost of (O(1+H(f,\hat{f}))) over the query distribution while maintaining (O(\log n)) expected cost for individual queries, regardless of prediction accuracy, for fixed dimension and approximation parameter. Experiments on real and synthetic spatial datasets show that LASQ reduces the number of examined cubes compared with conventional quadtrees and skip quadtrees.

Critical strengths
  1. Novel learning-augmented approach to multidimensional range search: The paper extends learning-augmented search structures beyond individual point lookups to multidimensional range queries. Predicting critical-cube frequencies rather than individual point-access frequencies is an interesting approach that addresses the characteristics of range searching.

  2. Strong theoretical guarantees: The paper establishes both consistency and robustness guarantees, demonstrating that accurate predictions improve expected query efficiency while inaccurate predictions do not compromise the asymptotic expected query complexity. These guarantees provide a solid theoretical foundation for the proposed approach.

Critical weaknesses
  1. Insufficient comparison with existing learned spatial indexes: The experiments compare LASQ only against conventional quadtrees and skip quadtrees. Existing learned multidimensional indexes, such as Flood, LISA, and Tsunami, also support range queries and should be considered as baselines. Although these approaches differ in their theoretical guarantees and query semantics, comparisons under clearly specified conditions would help establish the practical significance of LASQ.

  2. Limited experimental evaluation of practical performance The experiments primarily measure the number of examined cubes rather than actual query execution time. This metric does not fully capture the overhead of geometric intersection tests, pointer traversal, and memory access. Furthermore, the evaluation relies mainly on two-dimensional datasets and Zipf-skewed queries centered at data points. Consequently, it remains unclear whether the reported improvements translate into meaningful latency reductions across diverse query workloads.

Questions for authors
  1. Comparison with learned spatial indexes: Could the authors compare LASQ with existing learned multidimensional indexes, such as Flood, LISA, and Tsunami? Given the differences in approximation guarantees, comparisons using clearly defined query semantics would help clarify the relative advantages of LASQ.

  2. Actual query latency: Could the authors report wall-clock query execution times rather than only the number of examined cubes? In particular, do the reported improvements remain significant when geometric intersection tests, pointer traversal, and other computational overheads are included?

  3. Generalizability across workloads: Could the authors evaluate LASQ under more diverse query workloads, including uniformly distributed query centers, different levels of query skewness, and higher-dimensional datasets? Such results would help determine whether the improvements depend strongly on the current experimental settings.

6 comments
AuthorsOpenReview ↗

Response to uChu on learned indexes, query latency, and workload diversity

We appreciate your careful, constructive review and your recognition that critical-cube predictions extend learning-augmented search to multidimensional range queries. We agree that clearly specifying query semantics helps put the comparison with learned indexes in context. Below, we address your questions about these comparisons, wall-clock latency, and workload diversity using the C++ evaluation in Appendix C of the revised paper.

Weakness 1 and Q1 (Flood, LISA, Tsunami). As you note, the semantics differ: Flood, LISA, and Tsunami answer only one kind of query, namely axis-aligned boxes, while LASQ handles balls and, more generally, any convex range (Theorem 19). So, for this question, we added Appendix C.3, in which all four answer the queries they all support, squares (cubes in 3D), on the same machine. Flood, LISA, and Tsunami count exactly, LASQ within ε=0.1\varepsilon = 0.1, and every run checks 1000 answers. Time per query in µs (Tables 8 and 9):

SquaresFloodLISATsunamiLASQ
OSM Michigan, default size0.4104.830.1410.439
OSM Michigan, query size ×10,00037,14931,7301072.09
Deep forest, 10M points20,46417,87016.71.52

On default (small-sized) squares, Tsunami is the fastest and Flood is on par with LASQ. As the query size grows to 10,000 times the default, however, the time per query of the three grows by roughly three to five orders of magnitude, while that of LASQ remains below 5 µs at every size (Tables 8 and 9, Figure 11), consistent with its O(log⁡n)O(\log n) expected query time, which does not depend on the number of points in the range (Theorem 12). On the deep forest, LASQ is 11 to 13,668 times faster than the three other algorithms.

The second difference is robustness: LASQ is robust to wrong predictions, and Tsunami, which also learns from queries, is not: trained on queries with Zipf exponent 3 or 10 and tested at the default 1.5, Tsunami becomes up to 20.5× and 4,028× slower than LASQ (Table 10), while LASQ, trained on the same queries, stays within 47% of its time without the shift. Appendix C.3 gives the results on all datasets and query sizes, including 3D data (Tables 8 and 9, Figures 10–12), and the full workload shift (Table 10, Figure 13).

Weakness 2 and Q2 (wall-clock time). For this question, we added Appendix C.2, which reports the time per query and its 99th percentile; both include every intersection test, pointer traversal, and memory access:

GowallaOSM MichiganDeep forest
Cubes: skip quadtree / LASQ51.0 / 9.272.3 / 19.249.0 / 5.4
Time per query (µs): skip quadtree / LASQ0.526 / 0.1771.02 / 0.46011.5 / 1.76

The improvement holds up: 3.8–9.0× fewer cubes give a 2.2–6.5× speedup over the skip quadtree (Table 4), and LASQ's 99th percentile is lower as well. A plain quadtree has cheaper steps and is still comparable with LASQ on OSM Michigan, whose tree is shallow, while LASQ is faster on Gowalla and 10.7× faster on the deep forest. Appendix C.2 gives the full comparison, including the time per cube examined of each structure and the time of LASQ as its predictions degrade (Figure 7).

Weakness 2 and Q3 (workloads and dimension). For this question, we added the workloads you suggest to Appendix C.2 (Table 7), on all 44.1M points of OSM Michigan: centers uniform over space and Zipf exponents from 0.5 to 4, along with centers at 10 hotspots and log-uniform radii. LASQ is 1.95–2.6× faster than the skip quadtree on every one, and more skew helps it, as O(1+H(f,f^))O(1+H(f,\hat f)) suggests: its time drops from 2.2 µs at exponent 0.5 to 0.27 µs at 4. For higher dimensions, we added 3D data (Table 6): LASQ is 1.8× faster than the skip quadtree on a 20.1M-point LiDAR scan and 6.7× faster on the 3D deep forest. The guarantees hold for any fixed dd, but as with any quadtree, the constants grow exponentially with dd, so LASQ is aimed at low-dimensional, spatial data. Appendix C.1 defines each workload, and Appendix C.2 also varies the radius (Table 5) and ε\varepsilon (Figure 8).

Dear Reviewer,

As the discussion period is approaching its end, we wanted to kindly follow up and ask whether our rebuttal and the revised manuscript have adequately addressed your concerns.

In particular, we have added comparisons with learned indexes, wall-clock performance measurements, and experiments on more diverse workloads, including higher-dimensional datasets.

We would greatly appreciate it if you could revisit your evaluation in light of these additions. We would also be happy to clarify any remaining concerns.

Thank you again for your time and consideration.

Thanks for your feedback and additional experiments.

The claim that Flood, LISA, and Tsunami can answer only axis-aligned box queries is too strong. In particular, LISA supports kNN queries and explicitly combines box searches with Euclidean-ball filtering (see Section 4.2 and Algorithm 3). The same procedure, applied with a specified radius, can answer a ball range query exactly. More generally, box-based indexes can be adapted to answer ball queries by retrieving candidates from an enclosing box and filtering them by distance. This may introduce additional candidate-processing costs, but it does not make ball queries unsupported in principle. A comparison against these indexes, adapted via bounding-box retrieval and distance filtering, would help substantiate the claimed advantages.

Since my main concern remains unresolved, I will maintain my score.

Reviewer_B7dXOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes LASQ, a learning-augmented skip quadtree for approximate multidimensional range searching. The method exploits predicted frequencies of critical quadtree cubes to accelerate frequently encountered queries while preserving robustness to inaccurate workload predictions. The authors establish strong theoretical guarantees for the proposed method. The analysis also provides an O(\log n) expected cost guarantee for individual queries regardless of prediction accuracy. Experiments on real and synthetic spatial datasets demonstrate reductions in the number of quadtree cubes examined compared with conventional quadtrees and skip quadtrees.

Critical strengths

S1. The work proposes a novel and well-motivated learning-augmented data structure.

S2. The authors provide strong theoretical analysis. It establishes consistency and robustness guarantees while maintaining expected linear space and efficient construction.

S3. The experimental study demonstrates consistent reductions in examined cubes per query across real and synthetic data.

Critical weaknesses

W1. The experiments primarily measure the number of quadtree cubes visited rather than actual query latency or memory cost. However, LASQ introduces additional hierarchy levels, cross-level navigation, and prediction-dependent construction, which may affect wall-clock performance and memory consumption. In addition, the method is implemented in Python, but the Database community typically uses C/C++ to ensure efficiency in practice.

W2. The experiments only compare LASQ against a conventional quadtree and skip quadtree. However, the paper also motivates its contribution within learned multidimensional indexing, citing approaches such as Tsunami and LISA. It is suggested to provide comparisons with state-of-the-art learned spatial indexes to demonstrate performance.

W3. The size of the datasets used is not large enough (≤126k points). As a result, it is hard to judge the scalability or construction overheads for the proposed method. Larger datasets could be used for experimental study.

W4. The structure and guarantees are static. Could LASQ support dynamic updates (insert/delete points) while preserving robustness?

Questions for authors

Please refer to the weakness.

3 comments
AuthorsOpenReview ↗

Response to B7dX on performance and scalability

Thank you for the careful and encouraging review. We addressed all raised points in the revised paper:

W1 (latency and memory). We reimplemented LASQ and all other algorithms in C++ and added Appendix C.2, which reports the time per query and its 99th percentile, and Appendix C.4 (memory and build time). The extra levels do add a cost per step, but LASQ takes far fewer steps: on Gowalla, OSM Michigan, and the deep forest, it examines 3.8–9.0× fewer cubes than the skip quadtree and runs 2.2–6.5× faster, with a lower 99th percentile too (Table 4). Regarding memory, in LASQ, a cube moves up one more level within its class's layer with probability ρ\rho (Appendix C.1). The tuned values of ρ\rho (0.01–0.05) copy far fewer cubes into the upper levels compared to the skip quadtree, so LASQ needs 79–89 bytes per point on the 2D datasets, 21–24% less than the skip quadtree (Table 12). Appendix C.2 gives the full comparison, including the time per cube examined, and Appendix C.4 the build time and memory of every data structure (Tables 11 and 12, Figure 14).

W2 (learned spatial indexes). Flood, LISA, and Tsunami answer only one kind of query, namely axis-aligned boxes, while LASQ handles balls and, more generally, any convex range (Theorem 19). We have added Appendix C.3, which compares the mentioned algorithms with LASQ on axis-aligned boxes. Time per query is in µs (Tables 8 and 9):

SquaresFloodLISATsunamiLASQ
OSM Michigan, default size0.4104.830.1410.439
OSM Michigan, query size ×10,00037,14931,7301072.09
Deep forest, 10M points20,46417,87016.71.52

On default-size squares, Tsunami is the fastest and Flood is on par with LASQ. As the query size grows to 10,000 times the default, however, the time per query of Flood, LISA, and Tsunami grows by roughly three to five orders of magnitude, while that of LASQ remains below 5 µs at every size (Tables 8 and 9, Figure 11), consistent with its O(log⁡n)O(\log n) expected query time, which does not depend on the number of points in the range (Theorem 12). Finally, LASQ is robust to wrong predictions, while Tsunami is not: trained on queries with Zipf exponent 3 or 10 and tested at the default 1.5, Tsunami becomes up to 20.5× and 4,028× slower than LASQ (Table 10), while LASQ, trained on the same queries, stays within 47% of its time without the shift. Appendix C.3 gives the results on all datasets and query sizes, including 3D data (Tables 8 and 9, Figures 10–12), and the full workload shift (Table 10, Figure 13).

W3 (dataset size). We replaced the datasets with much larger ones: the full Gowalla set (1.26M points), all 44.1M OpenStreetMap nodes of Michigan, a 3D LiDAR scan of 20.1M points, and the deep forest up to 10M points (Table 3). The construction overhead is small: on OSM Michigan, LASQ builds in 11.4 s, including learning its predictions, compared with 11.2 s for the skip quadtree (Table 11). Query time is likewise stable as the dataset grows: on the deep forest, LASQ's time per square stays between 1.5 and 1.9 µs from 10K to 10M points (Table 8). Appendix C.1 describes every dataset (Table 3), and Appendix C.4 gives the build time and memory on each (Tables 11 and 12, Figure 14).

W4 (updates). LASQ targets point sets that change rarely and are queried mostly with range queries, such as map and survey snapshots, on which the index is rebuilt for each new snapshot. That said, we added Appendix B.2, which outlines how LASQ could support insertions and deletions. LASQ sorts the cubes of its base quadtree into classes by predicted frequency, assigns each class its own layer, and assigns a random depth to each cube within its layer. As in a skip quadtree, an insertion creates at most one new cube in the base quadtree. If it creates a cube, we link that cube into each level up to its promotion depth. Among existing cubes, only its parent’s frequency can change. The difficulty is that the top of each layer is the largest depth drawn in its class, so one new cube can move every cube of the more frequent classes to other levels. To address this, one option is to fix each layer’s width in advance using its class-size bound (Lemma 15) and cap each promotion draw at the top of its layer. A cube’s depth then depends only on its class and its own draw. After any sequence of updates, the resulting structure matches a fresh build on the current points using the same class assignments. Because the widths are set from the number of points nn at the last build, the structure is rebuilt from scratch whenever nn doubles or halves; a rebuild takes O(nlog⁡n)O(n\log n) expected time (Theorem 12) and follows at least n/2n/2 updates, so it adds only O(log⁡n)O(\log n) expected amortized time per update. This scheme is designed to preserve LASQ’s guarantees, including robustness to inaccurate predictions. Appendix B.2 outlines the approach, and we leave the full analysis to future work.

I think that the authors have addressed most of my comments. Especially, more experiments have been added for W1-W3. I would like to maintain my origial postive score.

Dear Reviewer,

Thank you for taking the time to review our rebuttal and revised manuscript. We are pleased that the additional experiments have addressed most of your concerns.

We appreciate your constructive feedback and your continued positive evaluation of our work.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response and summary of revisions

We thank all reviewers for their careful and constructive reviews. We have addressed the points raised in our individual replies and uploaded a revised manuscript to OpenReview. The main changes are:

  • Implementation and performance. The original evaluation used Python and measured how many cubes each query visited, a common measure of search work across the tree-based structures we compared. In the revised paper, we implemented LASQ and the quadtree baselines in C++ and now also report wall-clock query time, memory use, and construction time. On the default workloads, LASQ visits fewer cubes, answers queries faster, and has lower tail latency than the skip quadtree. LASQ also uses less memory than the skip quadtree on the real datasets we evaluated.

  • Dataset size and workloads. We expanded the evaluation from roughly 126,000 points to datasets with up to 44.1 million points. We added real and synthetic 3D data and tested more varied query locations, sizes, and levels of skew. The performance gains over the skip quadtree carry over to larger datasets and a wider range of query workloads.

  • Learned-index comparisons. We originally focused on quadtree baselines because they support the general convex queries studied in the paper and because cube visits provide a common measure of search work across these tree-based structures. In the revised C++ evaluation, we compare LASQ’s wall-clock performance with that of Flood, LISA, and Tsunami, which are designed for axis-aligned boxes. All four methods receive the same box queries. LASQ is generally competitive with the learned indexes we evaluated and performs particularly well on large-range queries. Moreover, after a workload shift, LASQ’s latency increases much less than Tsunami's does, illustrating LASQ’s robustness to prediction errors in practice. We also give worst-case examples in which the evaluated Flood and LISA query procedures must examine many candidates even when the query returns no points (Appendix C.3.1).

  • Presentation and updates. We added a roadmap showing how the definitions fit together and how they lead to the main theorem. We moved some technical material to the appendix and added a table that shows where each definition is introduced and used. We also outlined a scheme for insertions and deletions, with its full analysis left to future work.

Thank you again for your time and feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.