Pivot selection: Dimension reduction for distance-based indexing
Pivot selection: Dimension reduction for distance-based indexing
复制标题
DOI：
10.1016/j.jda.2011.10.004
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Rui Mao;W. Miranker;Daniel P. Miranker
中科院分区：
文献类型：
--
作者：
Rui Mao;W. Miranker;Daniel P. Miranker
基于距离的索引仅利用三角不等式来回答度量空间中的相似性查询。由于缺乏坐标结构，Rn中的数学工具只能间接应用，使得度量空间索引的理论研究变得困难。为了解决这个问题，一个常见的算法步骤是选择少量的特殊点（称为枢轴），并将数据对象映射到低维空间，每个枢轴对应一个维度，其中每个维度表示枢轴到数据对象的距离。我们形式化了一个“枢轴空间模型”，其中所有数据对象都用作枢轴，使得数据从度量空间映射到 Rn，保留 L∞ 下的所有成对距离。通过该模型，可以证明度量空间中的索引问题可以在Rn中等效地研究。此外，我们证明了对 Rn 进行降维的必要性，并且降维的唯一有效形式是选择现有维度，即枢轴选择。 Rn的坐标结构使得许多数学工具的应用成为可能。特别是，主成分分析 (PCA) 被纳入用于枢轴选择的启发式方法中，并被证明在大范围的工作负载上是有效的。我们还表明，PCA 可用于可靠地测量度量空间的内在维度。
Distance-based indexing exploits only the triangle inequality to answer similarity queries in metric spaces. Lacking coordinate structure, mathematical tools in Rncan only be applied indirectly, making it difficult to theoretically study metric-space indexing. Toward solving this problem, a common algorithmic step is to select a small number of special points, called pivots, and map the data objects to a low-dimensional space, one dimension for each pivot, where each dimension represents the distances of a pivot to the data objects. We formalize a “pivot space model” where all the data objects are used as pivots such that data is mapped from metric space to Rn, preserving all the pairwise distances under L∞. With this model, it can be shown that the indexing problem in metric space can be equivalently studied in Rn. Further, we show the necessity of dimension reduction for Rnand that the only effective form of dimension reduction is to select existing dimensions, i.e. pivot selection. The coordinate structure of Rnmakes the application of many mathematical tools possible. In particular, Principle Component Analysis (PCA) is incorporated into a heuristic method for pivot selection and shown to be effective over a large range of workloads. We also show that PCA can be used to reliably measure the intrinsic dimension of a metric space.