Spatial and multidimensional indexing: a local query is cheap only while it stays local

Unit five showed that every balanced tree buys a logarithmic read with work spread over updates, so the read-to-write ratio decides the winner. A spatial index makes a different bet: it answers a question about a region rather than about one key, and earns its cost only when queries select a small part of the space. A query that widens degenerates it to a scan, and the index becomes pure overhead.

The query comes before the structure

An index is a bet about the question that will be asked of it. Bentley and Friedman (1979) treat range searching as a query model rather than a structure, defining the query types including the orthogonal range query and comparing candidate structures by the bounds each achieves. What an index is for is settled before any structure is chosen.

The saving is selectivity. A range query is local when the region it names contains a small fraction of the objects, so most of the index can be discarded unread; selectivity belongs to the query, not to the data alone.

The region is the device that makes pruning possible

Finkel and Bentley (1974) gave the first widely used spatial hierarchy: in a quad tree each node covers a region of a two-dimensional key space and splits into four children, and region retrieval descends only the nodes that can contain the answer, with average insertion logarithmic in tree size. Guttman (1984) generalised the idea to objects of non-zero size: an R-tree groups nearby objects under bounding rectangles, so a search descends only the branches whose rectangle overlaps the query.

Both prune by discarding a node whose region cannot intersect the query, and that test is the whole saving: if the query region overlaps almost every node, the traversal becomes the scan it was meant to replace.

A map viewport makes the mechanism concrete. The viewport is a rectangle, the map is a set of points, and each node carries the smallest box containing everything beneath it. The search descends only where that box overlaps the viewport, so a node whose box lies entirely outside it is never read. The saving is the count of pages that pass the box test, and it falls to nothing as the viewport grows to cover the map. Over a metered connection that page count is a bill as well as a time.

The margin is engineered, and high dimension undoes the engineering

Beckmann, Kriegel, Schneider and Seeger (1990) observed that the R-tree optimises only the area of each enclosing rectangle, and redesigned the insertion and split rules to optimise area, margin and overlap together and to force the reinsertion of entries that had drifted. Across an exhaustive comparison under highly varying data and queries, the R*-tree clearly outperformed Guttman's linear and quadratic R-trees and Greene's variant: Reducing overlap keeps the query local to fewer branches, so the gain is a measured increase in selectivity.

Everything so far assumes the query stays local, and the assumption fails in high dimension. Bentley (1975) had shown how the guarantee weakens when he generalised the ordered search tree to k dimensions: in a k-d tree insertion takes average logarithmic time, deletion of the root takes O(n^((k-1)/k)), and a partial match specifying t of the k keys takes O(n^((k-t)/k)), rising with the number of unspecified keys.

Berchtold, Keim and Kriegel (1996) located the mechanism. They analysed bounding boxes in the directory of an R-tree as dimension grew and found the overlap between them increases with dimension, rising to about 90 per cent by dimension five, arguing this is general to indexing high-dimensional data rather than peculiar to the R-tree. Their X-tree minimises overlap and uses supernodes, and they report it outperforms the R*-tree and the TV-tree by up to two orders of magnitude at high dimension.

Weber, Schek and Blott (1998) supply the threshold, under stated assumptions of uniformity and independence: partitioning and clustering methods have linear complexity at high dimensionality, and a sequential scan outperforms existing methods once the number of dimensions exceeds around ten.

Extensibility does not buy selectivity

Hellerstein, Naughton and Pfeffer (1995) show that the framework problem and the selectivity problem are separate. Their generalised search tree supports an extensible set of queries and data types, unifies B+-trees and R-trees in one code base, and adapts to a new type by registering six methods, with about 500 lines of C per method against roughly 3000 for the existing packages. Yet they ask whether any dataset indexed with a GiST gives efficient lookup, and answer no: being indexable is not the same as being cheaply queryable.

Beyond geometry the index follows the distance, and relaxing the query buys the locality back

The query model can widen past geometry without changing the thesis. Ciaccia, Patella and Zezula (1997) give the M-tree for a metric space, in which proximity is defined only by a distance function satisfying positivity, symmetry and the triangle inequality, and report that it stays balanced and scales with growing files. Beygelzimer, Kakade and Langford (2006) make the condition explicit: their cover tree needs linear space whatever the metric, and answers queries in logarithmic time only under a bounded expansion constant, a measure of intrinsic dimensionality governing how fast the number of neighbours grows with distance. The query time is O(c^12 log n).

The index follows the query and holds only under an assumption: the metric axioms for the M-tree and a bounded expansion constant for the cover tree. A dataset with a large expansion constant is one on which the index stops paying.

Indyk and Motwani (1998) removed the curse of dimensionality for the approximate problem rather than the exact one. For points in d dimensions their two algorithms use space polynomial in the number of points and the dimension, with query time sub-linear in the number of points and polynomial in the dimension. They introduce locality-sensitive hashing, and Andoni and Indyk (2006) then gave simpler hash families whose query time almost matches the lower bound for hashing-based algorithms. The price is stated: the answer is an approximate nearest neighbour.

Contested question: has the index failed, or was it built for the wrong query?

The literature agrees that exact spatial indexes stop paying at high dimension and disagrees about the remedy. One position treats the degeneration as inherent. Weber and colleagues (1998) prove a threshold above which no partitioning or clustering organisation avoids a sequential scan. Berchtold and colleagues (1996) supply the mechanism, with directory overlap rising to about 90 per cent by dimension five. The opposing position holds that the failure belongs to a design and can be engineered down. Berchtold and colleagues (1996) report the X-tree restoring up to two orders of magnitude against the R*-tree and the TV-tree. Beckmann and colleagues (1990) reduce overlap by optimising margin and overlap together and by forced reinsertion.

A third position denies that the question is about exactness. Indyk and Motwani (1998) and Andoni and Indyk (2006) recover sublinear query time in high dimension once the answer may be approximate, so degenerating to a scan describes exact query answering rather than spatial search as such. A study would settle the disagreement: report distance computations and page input and output operations, or query latency, as a function of intrinsic dimension and query selectivity on data whose distribution is stated, and compare an exact index, a scan and an approximate index at matched recall. No source here reports the crossing point on a distribution chosen to defeat the index.

Weigh the cases by kind. Weber and colleagues (1998) prove a threshold, but only under assumptions of uniformity and independence. Berchtold and colleagues (1996) measure overlap growing with dimension and Beckmann and colleagues (1990) a gain from reducing it, so the remedy side is a measured improvement on chosen data. The strongest objection is that the proof of degeneration assumes uniformity, so a clustered index may keep pruning long past the stated dimension. While the dispute is open, a designer fixes whether the answer must be exact, sets a recall target if it need not, and measures pruning on the real distribution.

Where the argument is heading

The named work points away from exact geometric region queries and towards approximate similarity search, where the index is judged by recall at a given latency rather than by whether it prunes. Malkov and Yashunin (2020) give the current practice. Hierarchical navigable small world graphs are fully graph-based, a hierarchy of proximity graphs with links separated by distance scale, and are reported to give logarithmic complexity scaling and state-of-the-art recall and speed across several datasets. A second line predicts rather than prunes. Liu, Li, Zeng, Shen and Chen (2025) evaluate published multi-dimensional learned indexes under one benchmark and report index sizes up to three orders of magnitude smaller than R-tree and k-d tree variants and range queries up to 2.19 times faster. Such an index answers from a fitted model rather than a bounding box, so its selectivity depends on how well the model captures the distribution. The locality assumption has not been removed; it has been moved into the model.

The sources this unit rests on

• Andoni, A. and Indyk, P. (2006). Near-Optimal Hashing Algorithms for Approximate Nearest Neighbour in High Dimensions. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). doi:10.1109/focs.2006.49 Andoni and Indyk give simpler locality-sensitive hash families for approximate nearest-neighbour search whose query time and space almost match the hashing lower bound, showing the approximation parameter is tunable.
• Beckmann, N., Kriegel, H. P., Schneider, R. and Seeger, B. (1990). The R*-tree: an efficient and robust access method for points and rectangles. ACM SIGMOD Record. doi:10.1145/93605.98741 Beckmann, Kriegel, Schneider and Seeger redesign the R-tree's insertion and split rules, optimising area, margin and overlap together and forcing reinsertion of drifted entries, and report the R*-tree outperforms Guttman's R-trees. It is an empirical improvement in a controlled testbed.
• Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM. doi:10.1145/361002.361007 Bentley develops the k-d tree for associative searching, giving logarithmic average insertion, root deletion in O(n^((k-1)/k)) and partial match with t keys specified in O(n^((k-t)/k)). The ordered-search idea generalises to several dimensions but weakens as dimension rises.
• Bentley, J. L. and Friedman, J. H. (1979). Data Structures for Range Searching. ACM Computing Surveys. doi:10.1145/356789.356797 Bentley and Friedman define the range query, including the orthogonal range query, and compare candidate structures by the bounds each achieves. It is a survey, but it fixes the query model an index is built to answer.
• Berchtold, S., Keim, D. A. and Kriegel, H. P. (1996). The X-tree: an index structure for high-dimensional data. VLDB. https://www.vldb.org/conf/1996/P028.PDF Berchtold, Keim and Kriegel show that directory overlap in R-tree-based indexes rises with dimension, reaching about 90 per cent by dimension five, and give the X-tree, reported to outperform the R*-tree by up to two orders of magnitude. It names the failure mode.
• Beygelzimer, A., Kakade, S. and Langford, J. (2006). Cover trees for nearest neighbour. Proceedings of the 23rd international conference on Machine learning - ICML '06. doi:10.1145/1143844.1143857 Beygelzimer, Kakade and Langford give the cover tree, which uses linear space whatever the metric and answers queries in logarithmic time under a bounded expansion constant. It names the assumption a metric index needs in order to beat a scan.
• Ciaccia, P., Patella, M. and Zezula, P. (1997). M-tree: an efficient access method for similarity search in metric spaces. VLDB. https://www.vldb.org/conf/1997/P426.PDF Ciaccia, Patella and Zezula give the M-tree, which indexes a generic metric space where proximity is defined only by a distance function satisfying positivity, symmetry and the triangle inequality. It widens the query model from rectangles to any distance.
• Finkel, R. A. and Bentley, J. L. (1974). Quad trees a data structure for retrieval on composite keys. Acta Informatica. doi:10.1007/bf00288933 Finkel and Bentley give the quad tree, in which each node covers a region and splits into four children, with average insertion logarithmic in tree size and deletion and merging noted as inherently difficult. It is the origin of the region-as-key idea.
• Guttman, A. (1984). R-trees: a dynamic index structure for spatial searching. ACM SIGMOD Record. doi:10.1145/971697.602266 Guttman introduces the R-tree, which groups nearby objects under bounding rectangles so a search descends only the branches that overlap the query, motivated by computer-aided design and geo-data. It makes a map viewport a query rather than a scan.
• Hellerstein, J. M., Naughton, J. F. and Pfeffer, A. (1995). Generalised search trees for database systems. VLDB. https://www.vldb.org/conf/1995/P562.PDF Hellerstein, Naughton and Pfeffer give the generalised search tree, an extensible indexing framework in which a new index type is defined by six registered methods over an abstract key and query type. They answer no to whether any indexed dataset gives efficient lookup.
• Indyk, P. and Motwani, R. (1998). Approximate nearest neighbours: towards removing the curse of dimensionality. Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98. doi:10.1145/276698.276876 Indyk and Motwani give a locality-sensitive hashing scheme for approximate nearest-neighbour search using space polynomial in the number of points and the dimension, with sublinear query time. It shows exactness is the cost of dimensionality, not sublinearity.
• Liu, Q., Li, M., Zeng, Y., Shen, Y. and Chen, L. (2025). How good are multi-dimensional learned indexes? An experimental survey. The VLDB Journal. doi:10.1007/s00778-024-00893-6 Liu, Li, Zeng, Shen and Chen evaluate published multi-dimensional learned indexes under one benchmark, finding index sizes up to three orders of magnitude smaller than R-tree and k-d tree variants with range queries up to 2.19 times faster. It is a learned model in place of a pruning structure.
• Malkov, Y. A. and Yashunin, D. A. (2020). Efficient and Robust Approximate Nearest Neighbour Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. doi:10.1109/tpami.2018.2889473 Malkov and Yashunin present hierarchical navigable small world graphs, an approximate nearest-neighbour index built from a hierarchy of proximity graphs, and report logarithmic complexity scaling and state-of-the-art recall across several datasets. It is the current practice.
• Weber, R., Schek, H. J. and Blott, S. (1998). A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. VLDB. https://www.vldb.org/conf/1998/p194.pdf Weber, Schek and Blott show, under assumptions of uniformity and independence, that partitioning and clustering methods have linear complexity at high dimensionality and that a sequential scan wins beyond around ten dimensions.