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

Roger WeberHans-J. SchekStephen Blott

article1998VLDB1,859 citations

Proves that conventional tree-based indexing structures degenerate into linear scans beyond ten dimensions and introduces the Vector Approximation File to dramatically accelerate similarity search in high-dimensional vector spaces.

Listen

Modern data applications in multimedia retrieval, decision support, and data mining rely heavily on similarity search, which locates database records that closely match a given query feature vector. As the number of feature dimensions grows from a few dozen to hundreds, traditional indexing methods face severe performance degradation, a phenomenon known as the dimensional curse. Understanding the limits of these indexing structures is essential for designing scalable, high-performance database architectures.

The article evaluates the theoretical and practical performance limits of multidimensional partitioning and clustering index structures for nearest-neighbor searches in high-dimensional spaces. It aims to establish formal bounds on when conventional indexes fail and to demonstrate a faster alternative approach based on vector approximations.

The researchers conducted a quantitative mathematical analysis using geometric probability and cost modeling under standard assumptions of uniform and independent data distributions. To validate the theoretical models, they performed empirical experiments comparing multidimensional tree indexes against sequential scans and an approximation-based method across synthetic datasets and a real-world collection of over 50,000 image feature vectors.

The primary finding is that every space-partitioning, data-partitioning, or clustering method inevitably degenerates to linear complexity as dimensionality increases, ultimately requiring the search algorithm to inspect nearly every stored data block. When dimensionality exceeds approximately 10, a straightforward, well-tuned sequential scan routinely outperforms sophisticated tree structures because sequential disk access is significantly more efficient than random block reads. In response, the article introduces the vector approximation file, which compresses feature vectors into compact bit strings that are four to eight times smaller than raw vector data. In practical evaluations, this approximation method filtered out over 99.9% of candidate vectors, outperforming traditional tree structures and linear scans once dimensionality exceeded 6, while uniquely exhibiting improved filtering performance as dimensionality increased.

These findings indicate that database architects should avoid relying on complex hierarchical tree indexes for high-dimensional feature searches. Attempting to maintain spatial index trees above 10 dimensions incurs significant computational and input-output overhead without reducing the search space, increasing operational costs and query latencies. In contrast, flat approximation files simplify data management by eliminating intricate tree rebalancing, enabling easier concurrency control, straightforward data distribution, and native support for parallel processing.

Organizations managing high-dimensional similarity searches should adopt flat, approximation-based vector scanning architectures rather than hierarchical tree indexes whenever dimensionality exceeds 6 to 10. System architects should configure compact quantization grids, such as 4 to 8 bits per dimension, to maximize the initial filtering step before accessing raw vectors from storage. Before implementation, engineering teams should evaluate their specific data distributions, as the core theoretical proofs assume uniform feature distributions; however, empirical tests on real-world image datasets confirm that the practical advantages of approximation-based scanning hold robustly across correlated data.

Bell Laboratories ETH Zurich Institute of Information Systems approximation scheme high dimensional data high dimensionality similarity-search methods high-dimensional spaces nearest-neighbor search

Weber et al (1998).pdf

Paper: The R*-tree: an efficient and robust access method for points and rectangles, Norbert Beckmann et al. (1990). This paper introduces the R*-tree spatial indexing method, which serves as a primary benchmark and analytical baseline evaluated in the source paper's study on high-dimensional similarity search.
Paper: R-trees: a dynamic index structure for spatial searching, Antonin Guttman (1984). This foundational work establishes the original R-tree dynamic indexing structure upon which multidimensional tree-based access methods analyzed in the source paper are based.
Paper: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Paolo Ciaccia et al. (1997). This paper presents the M-tree index for metric similarity search, providing essential context on tree-based partitioning approaches that face performance degradation in high-dimensional spaces.

Paper: Similarity Search in High Dimensions via Hashing, A. Gionis et al. (1999). This seminal work introduces Locality-Sensitive Hashing (LSH), advancing sublinear approximate nearest-neighbor search to overcome the high-dimensional indexing limits formalized by the source paper.
Paper: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Alexandr Andoni et al. (2008). This paper extends theoretical and practical hashing algorithms for approximate nearest neighbor search to achieve provably sublinear query times in high-dimensional vector spaces.
Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Yu. A. Malkov et al. (2016). This paper develops Hierarchical Navigable Small World (HNSW) graphs, offering an alternative graph-based indexing paradigm that scales efficiently where classical space-partitioning trees fail.
Paper: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Suhas Jayaram Subramanya et al. (2019). DiskANN combines graph search with vector quantization to perform billion-scale similarity search on a single node, addressing high-dimensional nearest-neighbor retrieval at massive scale.
Paper: Accelerating Large-Scale Inference with Anisotropic Vector Quantization, Ruiqi Guo et al. (2020). This work develops anisotropic vector quantization to compress high-dimensional vectors and optimize inner product similarity search beyond uniform approximation schemes.
Paper: Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings, Leonardo Kuffo et al. (2026). This work explores clustering high-dimensional vector embeddings using dimensionality reduction and quantization, directly building on approximation principles for scalable similarity search.

Cover for A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces

Abstract

For similarity search in high-dimensional vector spaces (or ‘HDVSs’), researchers have proposed a number of new methods (or adaptations of existing methods) based, in the main, on data-space partitioning. However, the performance of these methods generally degrades as dimensionality increases. Although this phenomenon—known as the ‘dimensional curse’ is well known, little or no quantitative analysis of the phenomenon is available. In this paper, we provide a detailed analysis of partitioning and clustering techniques for similarity search in HDVSs. We show formally that these methods exhibit linear complexity at high dimensionality, and that existing methods are outperformed on average by a simple sequential scan if the number of dimensions exceeds around 10. Consequently, we come up with an alternative organization based on approximations to make the unavoidable sequential scan as fast as possible. We describe a simple vector approximation scheme, called VA-file, and report on an experimental evaluation of this and of two tree-based index methods (an R*-tree and an X-tree).

Topics

approximation scheme high dimensional data high dimensionality linear complexity curse of dimensionality high-dimensional feature space

Keywords

1 Introduction
Related Work
2 Basic Definitions and Simple Observations
2.1 Basic Assumptions and Notation
2.2 Probability and Volume Computations
2.3 The Difficulties of High Dimensionality
3 Analysis of Nearest-Neighbor Search
3.1 General Cost Model
3.2 Space-Partitioning Methods
3.3 Data-Partitioning Methods
3.3.1 Rectangular MBRs
3.3.2 Spherical MBRs
3.4 General Partitioning and Clustering Schemes
4 Object Approximations for Similarity Search
4.1 The VA-File
4.2 Performance Comparison
5 Conclusions
Acknowledgments
References

Knowls

Knowl 1 — General Degeneration of Partitioning and Clustering for High-Dimensional Nearest-Neighbor Search
theoretical result
For any spatial indexing, clustering, or space- or data-partitioning method operating in the $d$ -dimensional unit hypercube $\Omega = [0, 1]^d$ under the $L_2$ Euclidean metric where:
1. Each cluster or partition $C_i$ ( $i = 1, \dots, l$ ) is delimited by a convex Minimum Bounding Region $\text{mbr}(C_i)$ , and
2. Each cluster contains at least two data points ( $m \ge 2$ ),
the average probability $P_{visit}^{avg}$ that a cluster must be accessed during a 1-nearest-neighbor search is lower-bounded by the optimal line cluster connecting any point $A$ to a point $P(A)$ on the surface of its nearest-neighbor sphere $\text{surf}(nn^{sp}(A))$ :

$P_{visit}^{avg} \ge \frac{1}{\text{Vol}(\Omega)} \int_{A \in \Omega} \text{Vol}\left(\text{MSum}(\text{line}(A, P(A)), E[nn^{dist}]) \cap \Omega\right) dA$

where $\text{MSum}(X, r)$ denotes the Minkowski sum of region $X$ with an $L_2$ sphere of radius $r$ , and $E[nn^{dist}]$ is the expected nearest-neighbor distance across $\Omega$ .

As dimensionality $d \to \infty$ , $P_{visit}^{avg}$ monotonically increases and converges to 1. Consequently:
1. The search complexity of any partitioning and clustering scheme converges to $O(N)$ with increasing dimensionality.
2. For every partitioning or clustering method, there exists a threshold dimensionality $\hat{d}$ beyond which a simple sequential scan outperforms the index structure on average. In the theoretical limiting case of optimal line clusters for $N = 10^6$ points, the 20% block-visitation threshold is exceeded when $d \ge 610$ , whereas for practical index structures with larger bounding regions, this degradation threshold occurs at much lower dimensionalities (typically $d \le 20$ ).
Knowl 2 — Vector Approximation File Architecture
model/method
The Vector Approximation File (VA-File) is an approximation-based storage and index structure designed to accelerate similarity searches in high-dimensional vector spaces without hierarchical space or data partitioning.

The VA-File divides the $d$ -dimensional data space $\Omega = [0, 1]^d$ into $2^b$ rectangular cells, where $b = \sum_{i=1}^d b_i$ is the total bit budget and $b_i$ (typically between 4 and 8) is the number of bits allocated to dimension $i$ . Along each dimension $i$ , $2^{b_i}$ quantile slices are determined such that each slice contains an equal number of data points; these partition boundary points are kept constant after construction.

The structure consists of two physical files:
1. An approximation file, which is a compact, flat array containing the $b$ -bit representation of the cell coordinate for each of the $N$ data vectors.
2. The standard vector file, storing the full $d$ -dimensional coordinate representations of all $N$ data vectors sequentially on disk.
Because $b$ bits per vector represent a substantial reduction in size compared to uncompressed floating-point coordinates, the approximation file is 4 to 8 times smaller than the vector file, resulting in a storage overhead ratio of only 0.125 to 0.25.
Knowl 3 — Two-Phase Nearest-Neighbor Search Algorithm in the VA-File
algorithm
Nearest-neighbor search in the VA-File operates in two distinct phases: a filtering phase over compact geometric approximations, followed by a candidate verification phase accessing the actual vector data.
Input: Query vector $Q \in [0, 1]^d$ , number of neighbors $k$ , approximation file $A$ , vector file $V$ , dimension slice boundaries
Output: Set of $k$ nearest neighbors to $Q$
// Phase 1: Filter approximations
$\delta \leftarrow \infty$ // Smallest upper bound for the k-th NN candidate
Candidates $\leftarrow \emptyset$
for each approximation $a_j \in A$ (for $j = 1, \dots, N$ ) do
    Compute lower distance bound $l_j = \text{mindist}(Q, \text{cell}(a_j))$
    Compute upper distance bound $u_j = \text{maxdist}(Q, \text{cell}(a_j))$
    if $l_j \le \delta$ then
        Add $(j, l_j)$ to Candidates
        Update $\delta$ with $u_j$ such that $\delta$ is the $k$ -th smallest upper bound found so far
    end if
end for
// Phase 2: Access vectors
Candidates $\leftarrow$ filter out all $(j, l_j) \in \text{Candidates}$ where $l_j > \delta$
Sort Candidates in ascending order of lower bound $l_j$
$NN \leftarrow \emptyset$ // Priority queue of (vector, actual_distance) of size up to k
for each $(j, l_j) \in \text{Candidates}$ in sorted order do
    if $|NN| = k$ and $l_j > \max_{(v, dist) \in NN}(dist)$ then
        break // No remaining candidate can be closer than the current k-th NN
    end if
    Read vector $V[j]$ from disk
     $dist \leftarrow \|V[j] - Q\|_2$
    Update $NN$ with $(V[j], dist)$ to maintain the $k$ smallest actual distances
end for
return $NN$
$\text{mindist}(Q, \text{cell}(a_j))$ and $\text{maxdist}(Q, \text{cell}(a_j))$ denote the minimum and maximum Euclidean distances from $Q$ to any point within the hyper-rectangular cell encoded by bit-string $a_j$ .
Knowl 4 — Minkowski Sum Cost Model for Nearest-Neighbor Block Access
model/method
In a block-partitioned vector database where $N$ data objects are grouped into blocks containing an average of $m$ objects (yielding $N/m$ data blocks), the disk I/O cost of an optimal nearest-neighbor search is given by the expected number of blocks visited, $M_{visit}$ .

An optimal search visits exactly those blocks whose Minimum Bounding Region ( $\text{mbr}_i$ ) intersects the query's nearest-neighbor sphere $nn^{sp}(Q) = sp^d(Q, nn^{dist}(Q))$ . By transforming the spherical query into a point query via the Minkowski sum $\text{MSum}(\text{mbr}_i, E[nn^{dist}])$ (the region of all points within Euclidean distance $E[nn^{dist}]$ of the surface of $\text{mbr}_i$ ), the probability that the $i$ -th block must be visited is given by:

$P_{visit}[i] = \text{Vol}\left(\text{MSum}(\text{mbr}_i, E[nn^{dist}]) \cap \Omega\right)$

where $\Omega = [0, 1]^d$ is the data space and $E[nn^{dist}]$ is the expected nearest-neighbor distance across all query points in $\Omega$ .

The total expected number of visited blocks is:

$M_{visit} = \frac{N}{m} P_{visit}^{avg} = \sum_{i=1}^{N/m} P_{visit}[i]$

where $P_{visit}^{avg} = \frac{m}{N} \sum_{i=1}^{N/m} P_{visit}[i]$ is the average block access probability.
Knowl 5 — Analytical Degradation of Space-Partitioning Index Structures
theoretical result
For space-partitioning index structures (such as Grid Files, Quadtrees, and K-D-B-trees) in a $d$ -dimensional unit hypercube $\Omega = [0, 1]^d$ containing $N$ uniformly distributed points with $m$ points per block:

To avoid exponential directory overhead ( $B \cdot 2^d$ bytes for block size $B$ ), only $d' \le \lfloor \log_2(N/m) \rfloor$ dimensions can be split. Assuming each of the $d'$ dimensions is split once in the middle (at coordinate 0.5), each block's bounding region has $d'$ sides of length $1/2$ and $d - d'$ sides of length 1.

The maximum distance $l_{max}$ from any point inside a block to any point in the data space is:

$l_{max} = \frac{1}{2}\sqrt{d'} = \frac{1}{2}\sqrt{\lfloor \log_2(N/m) \rfloor}$

Because $l_{max}$ depends only on $N$ and $m$ and is independent of the data dimensionality $d$ , whereas the expected nearest-neighbor distance $E[nn^{dist}]$ monotonically increases with $d$ , there exists a dimensionality threshold beyond which $E[nn^{dist}] \ge l_{max}$ .

When $E[nn^{dist}] \ge l_{max}$ , the Minkowski sum of every block's bounding region with the NN-sphere covers the entire unit space $\Omega$ , yielding a block access probability of $P_{visit}[i] = 1$ for all blocks. For instance, with $m = 100$ , all blocks in the database must be visited for any dataset when dimensionality $d$ exceeds approximately 60, reducing the search to a sequential scan with random-access block overhead.
Knowl 6 — Analytical Performance Bounds for Data-Partitioning Trees with Rectangular and Spherical MBRs
theoretical result
For data-partitioning index trees in $d$ -dimensional space $\Omega = [0, 1]^d$ with $N$ uniformly distributed points and $m$ points per block:
1. Rectangular MBRs (e.g., R-tree, X-tree):* Splitting nodes at high dimensionality divides at most $d' \le \lfloor \log_2(N/m) \rfloor$ dimensions. The average block access probability during nearest-neighbor search exceeds the 20% efficiency threshold at moderate dimensionalities:
  - $d > 15$ for $N = 10^5$ ( $d' = 10$ )
  - $d > 18$ for $N = 10^6$ ( $d' = 14$ )
  - $d > 20$ for $N = 10^7$ ( $d' = 17$ )
2. Spherical MBRs (e.g., TV-tree, M-tree, SR-tree): If each block contains a center point $C$ and its $m-1$ nearest neighbors, the bounding sphere radius is $nn^{dist, m-1}(C) \ge E[nn^{dist}]$ . The probability of visiting block $i$ is lower-bounded by:
$P_{visit}^{sp}[i] \ge \text{Vol}\left(sp^d(C, 2 \cdot E[nn^{dist}]) \cap \Omega\right)$

Averaged over all centers $C \in \Omega$ :

$P_{visit}^{sp, avg} \ge \int_{C \in \Omega} \text{Vol}\left(sp^d(C, 2 \cdot E[nn^{dist}]) \cap \Omega\right) dC$

For $N = 10^6$ points, $P_{visit}^{sp, avg}$ exceeds the 20% efficiency threshold at $d = 26$ and reaches 100% (every block visited) at $d = 45$ .
Knowl 7 — Expected Nearest-Neighbor Distance in the Unit Hypercube
equation
In a $d$ -dimensional unit hypercube $\Omega = [0, 1]^d$ containing $N$ uniformly and independently distributed points, the expected Euclidean distance $E[nn^{dist}]$ from a query point $Q \in \Omega$ to its nearest neighbor is defined via the cumulative probability distribution function $P[Q, r]$ that the nearest neighbor lies within distance $r$ of $Q$ :

$P[Q, r] = 1 - \left(1 - \text{Vol}(sp^d(Q, r) \cap \Omega)\right)^N$

where $sp^d(Q, r)$ is the $d$ -dimensional Euclidean hypersphere of radius $r$ centered at $Q$ .

The expected nearest-neighbor distance for a specific query $Q$ is:

$E[Q, nn^{dist}] = \int_0^\infty r \frac{\partial P[Q, r]}{\partial r} dr$

The overall expected nearest-neighbor distance across all query points uniformly distributed in $\Omega$ is:

$E[nn^{dist}] = \int_{Q \in \Omega} E[Q, nn^{dist}] dQ$

As $d$ increases, $E[nn^{dist}]$ grows steadily and eventually exceeds the edge length of the data space ( $1.0$ ), while increasing $N$ reduces $E[nn^{dist}]$ only marginally beyond small datasets.
Knowl 8 — Collision Probability in High-Dimensional Vector Approximation
theoretical result
When a $d$ -dimensional space $\Omega = [0, 1]^d$ is partitioned into $2^b$ equal-volume cells ( $b = \sum_{i=1}^d b_i$ ), the probability that a uniformly distributed point falls into any specific cell is:

$P[\text{"in cell"}] = 2^{-b}$

For a database of $N$ data points, the probability that at least one other point shares the exact same $b$ -bit cell approximation with a given vector is:

$P[\text{share}] = 1 - \left(1 - 2^{-b}\right)^{N-1} \approx \frac{N}{2^b}$

Because the number of possible cells $2^b$ grows exponentially with dimensionality and bit allocation (e.g., for $b = 100$ and $N = 10^6 \approx 2^{20}$ , $P[\text{share}] \approx 2^{-80}$ ), the vast majority of cells are empty, and the probability of cell collisions between vectors is negligible even when using coarse approximations (4 to 8 bits per dimension).
Knowl 9 — Empirical Performance of VA-File Versus Tree Indexes and Sequential Scan
empirical result
In comparative experimental evaluations of 10-nearest-neighbor searches on synthetic uniform datasets and a 45-dimensional real image feature dataset (50,000 images, 8 bits/dimension):
1. Leaf Block Selectivity: The percentage of leaf blocks visited by the R*-tree and X-tree exceeds the 20% efficiency threshold when dimensionality $d > 10$ , reaching 100% of leaf blocks at high dimensions. In contrast, the VA-File visits fewer than 0.2% of actual vectors in the second phase at $d = 50$ , with vector file block selectivity continuing to shrink as dimensionality increases.
2. Wall-Clock Search Time: For low dimensions ( $d < 5$ ), the X-tree provides the fastest query execution. For $d \ge 6$ , the VA-File outperforms the X-tree, R*-tree, and standard sequential scan on both synthetic and real datasets, executing up to orders of magnitude faster than tree-based structures as dimensionality increases.
Knowl 10 — Assumptions on High-Dimensional Data Distribution and Index Viability Threshold
assumption
The theoretical cost analysis for nearest-neighbor similarity search is established under the following definitions and assumptions:
1. Uniformity and Independence: Data points and query points are independently and uniformly distributed within the $d$ -dimensional unit hypercube $\Omega = [0, 1]^d$ , with distance measured by the $L_2$ Euclidean metric.
2. Fractal Dimension Extension: For correlated real-world datasets, the analytical predictions derived under uniform assumptions are conjectured to apply to arbitrary higher-dimensional datasets having fractal dimension $d$ .
3. Sequential I/O Performance Advantage (20% Threshold): Sequential disk I/O provides a significant throughput speedup over random I/O (conservatively modeled as a factor of 5). Consequently, an indexing structure is defined to perform well only if it visits on average fewer than 20% of the database blocks; if an index visits more than 20% of blocks, a direct sequential scan over the entire dataset executes faster in wall-clock time.

Coverage note — No substantial contributed material was omitted. All analytical models, theoretical bounds, the VA-file structure, search algorithm, collision analysis, and experimental results are covered.

References

1.D. Barbara, W. DuMouchel, C. Faloutsos, P. J. Haas, J. Hellerstein, Y. Ioannidis, H. Jagadish, T. Johnson, R. Ng, V. Poosala, K. Ross, and K. C. Sevcik. The New Jersey data reduction report. Data Engineering, 20(4):3–45, 1997.
2.N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pages 322–331, Atlantic City, NJ, 23–25 May 1990.
3.J. Bentley and J. Friedman. Data structures for range searching. ACM Computing Surveys, 11(4):397–409, Decmeber 1979.
4.S. Berchtold, C. Böhm, B. Braunmüller, D. Keim, and H.-P. Kriegel. Fast parallel similarity search in multimedia databases. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 1–12, Tucson, USA, 1997.
5.S. Berchtold, C. Böhm, D. Keim, and H.-P. Kriegel. A cost model for nearest neighbour search. In Proc. of the ACM Symposium on Principles of Database Systems, pages 78–86, Tucson, USA, 1997.
6.S. Berchtold, C. Böhm, and H.-P. Kriegel. Improving the query performance of high-dimensional index structures by bulk load operations. In Proc. of the Int. Conf. on Extending Database Technology, volume 6, pages 216–230, Valencia, Spain, March 1998.
7.S. Berchtold, D. Keim, and H.-P. Kriegel. The X-tree: An index structure for high-dimensional data. In Proc. of the Int. Conference on Very Large Databases, pages 28–39, 1996.
8.T. Brinkhoff, H.-P. Kriegel, and R. Schneider. Comparison of approximations of complex objects used for approximation-based query processing in spatial database systems. In International Conference on Data Engineering, pages 40–49, Los Alamitos, Ca., USA, Apr. 1993.
9.T. Brinkhoff, H.-P. Kriegel, R. Schneider, and B. Seeger. Multi-step processing of spatial joins. SIGMOD Record (ACM Special Interest Group on Management of Data), 23(2):197–208, June 1994.
10.P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proc. of the Int. Conference on Very Large Databases, Athens, Greece, 1997.
11.J. Cleary. Analysis of an algorithm for finding nearest-neighbors in euclidean space. ACM Transactions on Mathematical Software, 5(2), 1979.
12.A. Csillaghy. Information extraction by local density analysis: A contribution to content-based management of scientific data. Ph.D. thesis, Institut für Informationssysteme, 1997.
13.A. Dimai. Differences of global features for region indexing. Technical Report 177, ETH Zürich, Feb. 1997.
14.C. Faloutsos. Access methods for text. ACM Computing Surveys, 17(1):49–74, Mar. 1985. Also published in/as: “Multiattribute Hashing Using Gray Codes”, ACM SIGMOD, 1986.
15.C. Faloutsos. Searching Multimedia Databases By Content. Kluwer Academic Press, 1996.
16.C. Faloutsos and S. Christodoulakis. Description and performance analysis of signature file methods for office filing. ACM Transactions on Office Information Systems, 5(3):237–257, July 1987.
17.C. Faloutsos and I. Kamel. Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension. In Proc. of the ACM Symposium on Principles of Database Systems, 1994.
18.R. Finkel and J. Bentley. Quad-trees: A data structure for retrieval on composite keys. ACTA Informatica, 4(1):1–9, 1974.
19.M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: The QBIC system. Computer, 28(9):23–32, Sept. 1995.
20.J. Friedman, J. Bentley, and R. Finkel. An algorithm for finding best-matches in logarithmic time. TOMS, 3(3), 1977.
21.A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 47–57, Boston, MA, June 1984.
22.J. Hellerstein, E. Koutsoupias, and C. Papadimitriou. On the analysis of indexing schemes. In Proc. of the ACM Symposium on Principles of Database Systems, 1997.
23.G. Hjaltason and H. Samet. Ranking in spatial databases. In Proceedings of the Fourth International Symposium on Advances in Spatial Database Systems (SSD95), number 951 in Lecture Notes in Computer Science, pages 83–95, Portland, Maine, Aug. 1995. Springer Verlag.
24.N. Katayama and S. Satoh. The SR-tree: An index structure for high-dimensional nearest neighbor queries. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 369–380, Tucson, Arizon USA, 1997.
25.K.-I. Lin, H. Jagadish, and C. Faloutsos. The TV-tree: An index structure for high-dimensional data. The VLDB Journal, 3(4):517–549, Oct. 1994.
26.D. Lomet. The hB-tree: A multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems, 15(4):625–658, December 1990.
27.J. Nievergelt, H. Hinterberger, and K. Sevcik. The grid file: An adaptable symmetric multikey file structure. ACM Transactions on Database Systems, 9(1):38–71, Mar. 1984.
28.J. Robinson. The k-d-b-tree: A search structure for large multidimensional dynamic indexes. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 10–18, 1981.
29.H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.
30.T. Sellis, N. Roussopoulos, and C. Faloustos. The R+-tree: A dynamic index for multi-dimensional objects. In Proc. of the Int. Conference on Very Large Databases, pages 507–518, Brighton, England, 1987.
31.R. Sproull. Refinements to nearest-neighbor search in k-dimensional trees. Algorithmica, 1991.
32.M. Stricker and M. Orengo. Similarity of color images. In Storage and Retrieval for Image and Video Databases, SPIE, San Jose, CA, 1995.
33.J. Ullman. Principles of Database and Knowledge-Base Systems, volume 1. Computer Science Press, 1988.
34.R. Weber and S. Blott. An approximation based data structure for similarity search. Technical Report 24, ESPRIT project HERMES (no. 9141), October 1997. Available at http://www-dbs.ethz.ch/~weber/paper/TR1997b.ps.

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — General Degeneration of Partitioning and Clustering for High-Dimensional Nearest-Neighbor Search

Knowl 2 — Vector Approximation File Architecture

Knowl 3 — Two-Phase Nearest-Neighbor Search Algorithm in the VA-File

Knowl 4 — Minkowski Sum Cost Model for Nearest-Neighbor Block Access

Knowl 5 — Analytical Degradation of Space-Partitioning Index Structures

Knowl 6 — Analytical Performance Bounds for Data-Partitioning Trees with Rectangular and Spherical MBRs

Knowl 7 — Expected Nearest-Neighbor Distance in the Unit Hypercube

Knowl 8 — Collision Probability in High-Dimensional Vector Approximation

Knowl 9 — Empirical Performance of VA-File Versus Tree Indexes and Sequential Scan

Knowl 10 — Assumptions on High-Dimensional Data Distribution and Index Viability Threshold

References

Access the Paper