A compact space decomposition for effective metric indexing
A compact space decomposition for effective metric indexing
复制标题
DOI：
10.1016/j.patrec.2004.11.014
复制
发表时间：
2005-07
期刊：
影响因子：
--
通讯作者：
Edgar Chávez;G. Navarro
中科院分区：
文献类型：
--
作者：
Edgar Chávez;G. Navarro
度量空间模型抽象了许多邻近搜索问题，从最近邻分类器到文本和多媒体信息检索。在这种情况下，索引是一种加速邻近查询的数据结构。然而，随着内在数据维度的增加，索引会失去效率。在本文中，我们提出了一个称为簇列表（LC）的简单索引，它基于数据集的紧凑分区。 LC 被证明需要很少的空间，适合主存储器和辅助存储器的实现，最重要的是，它对数据集的固有维度具有很强的抵抗力。在这方面我们的结构是不败的。最后我们讨论了度量空间搜索中不平衡的作用，以及它如何允许用内存空间换取构造时间。
The metric space model abstracts many proximity search problems, from nearest-neighbor classifiers to textual and multimedia information retrieval. In this context, an index is a data structure that speeds up proximity queries. However, indexes lose their efficiency as the intrinsic data dimensionality increases. In this paper we present a simple index called list of clusters (LC), which is based on a compact partitioning of the data set. The LC is shown to require little space, to be suitable both for main and secondary memory implementations, and most importantly, to be very resistant to the intrinsic dimensionality of the data set. In this aspect our structure is unbeaten. We finish with a discussion of the role of unbalancing in metric space searching, and how it permits trading memory space for construction time.