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
复制标题
DOI：
--
复制
发表时间：
1998-08
期刊：
影响因子：
--
通讯作者：
R. Weber;H. Schek;Stephen Blott
中科院分区：
文献类型：
--
作者：
R. Weber;H. Schek;Stephen Blott
对于高维向量空间（或“HDVS”）中的相似性搜索，研究人员提出了许多新方法（或现有方法的改编），主要基于数据空间划分。然而，这些方法的性能通常随着维数的增加而降低。虽然这种现象被称为“维度诅咒”，是众所周知的，很少或没有定量分析的现象。在本文中，我们提供了一个详细的分析分区和聚类技术的相似性搜索HDVS。我们正式表明，这些方法表现出线性复杂性在高维度，现有的方法优于平均一个简单的顺序扫描，如果维度的数量超过10左右。因此，我们提出了一种基于近似的替代组织，以尽可能快地进行不可避免的顺序扫描。我们描述了一个简单的向量近似方案，称为VA文件，并报告的实验评估这两个基于树的索引方法（R* 树和X树）。
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 a.nalysis 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).