Learning-Augmented Range Search

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 $(1+ϵ)$-approximate weighted range-sum queries with expected cost $O(1+H(f,\hat{f}))$, averaged over the query distribution. Here, $H(f,\hat{f})={\sum }_u{f}_u\log (1/{\hat{f}}_u)$ 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 $O(\log n)$ expected time regardless of prediction accuracy. The structure uses $O(n)$ expected space and requires $O(n\log n)$ 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.