- 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
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.
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):
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(logn) 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 Qi 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) 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.