Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

multidimensional index

A multidimensional index is a specialized data structure used in database systems to organize, store, and efficiently query data defined across multiple attributes, coordinates, or feature dimensions. While traditional one-dimensional indices arrange records along a single linear key, multidimensional indices structure multi-attribute data to accelerate complex retrieval operations, including range queries, spatial intersection searches, and nearest-neighbor similarity searches. These structures typically operate by partitioning space, clustering related data points, or using hierarchical bounding volumes to narrow down the search space, with common implementations including k-d trees, quadtrees, and R-tree variants. In high-dimensional environments, such as those found in multimedia retrieval, computer vision, and scientific data analysis, multidimensional indices facilitate efficient similarity search, though very high dimensionalities often require specialized indexing structures or vector approximations to mitigate search performance degradation.

1 item

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

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

Roger Weber, Hans-J. Schek, Stephen Blott

OrganizationsBell LaboratoriesETH ZurichInstitute of Information Systems

Why you should read this

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.

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).

Added

2026-09-18