nucleation

LIT-1107: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the VLDB Endowment's open copy of the proceedings paper (www.vldb.org/conf/1998/p194.pdf, pp. 194–205, a scan with an OCR text layer, fetched with a browser User-Agent header). Worth reading as the standard average-case analysis of why partitioned indexes for nearest-neighbour search lose to a sequential scan as dimension grows, and as the source of the VA-file. Under uniform, independent data in the unit cube with Euclidean distance, an assumed five-fold sequential advantage and a 20% line, the fraction of blocks an optimal search reads crosses that line at about 15–20 dimensions for rectangular bounding regions, 26 for spherical ones, and below a crude 610 for any partition into convex clusters of two or more points. The "around 10" usually cited is the measured crossover for an R*-tree and an X-tree on 50,000 uniform points and 45-dimensional image features. The bounds substitute the expected nearest-neighbour distance for each query's own, and they are evaluated by Monte Carlo. Data of low intrinsic dimension are outside the analysis except by an untested fractal-dimension conjecture. For QUESTION-114 it shows a regime where organizing into bins does not pay even with building free, and where the remedy is a scanned file of compact per-item approximations, not a better partition. For CLAIM-310 it marks where arrangement stops doing work: similarity over many coordinates the query does not name, unlike LEGO bins, where queries name a few discrete attributes. It has no bearing on CLAIM-309.
Tagsdatabases, information-retrieval
Cited as “paper” byNOTE-919 — Weber, Schek & Blott — Similarity search in high-dimensional spaces: when partitioning loses to a scan
Cited as “source” byTHEORY-369 — Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance and a fixed number of points, an optimal nearest-neighbour search over any index that partitions points into blocks or convex clusters of at least two points must read a fraction of blocks that grows toward all of them as dimension rises; with a five-fold sequential advantage for scanning, estimates put the crossover at about 15–26 dimensions for rectangular and spherical bounding regions, and two tree indexes measured on 50,000 points lost to a scan beyond about 10

Graph View

Weber, R., Schek, H.-J. and Blott, S. (1998). A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proc. VLDB 1998, pp. 194–205.

Key takeaways

Read in full (NOTE-919). Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance, the paper estimates the average fraction of blocks that an optimal nearest-neighbour search must read in a partitioned or clustered index. That fraction reaches the 20% at which a sequential scan wins, given an assumed five-fold sequential advantage, at about 15–20 dimensions for rectangular regions, 26 for spherical ones, and below a crude 610 for any partitioning into convex clusters of two or more points. The “around 10” in the abstract is the measured crossover for an R*-tree and an X-tree on 50,000 uniform points and on 45-dimensional image features. As an alternative it proposes the VA-file, a scanned file of compact per-vector approximations that filters out all but a few vectors. The analysis says nothing about data with low intrinsic dimension; that the results carry over by fractal dimension is a conjecture.

Why this is here

QUESTION-114 and CLAIM-310: under uniform independent data, partitioning and clustering indexes for similarity read nearly every block past some dimension, between about 15 and 60 by the analysis, even with building free. The often-quoted “about 10” is the measured crossover for two tree indexes, not the analytical threshold.

Backlinks