On Data Partitioning in Tree Structure Metric-Space Indexes
On Data Partitioning in Tree Structure Metric-Space Indexes
复制标题
DOI：
10.1007/978-3-319-05810-8_10
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
Rui Mao;Sheng Liu;Honglong Xu;Dian Zhang;Daniel P. Miranker
中科院分区：
文献类型：
--
作者：
Rui Mao;Sheng Liu;Honglong Xu;Dian Zhang;Daniel P. Miranker
树结构度量空间索引方法根据数据到一组选定参考点（也称为枢轴）的距离递归地划分数据。数据分区有两种基本形式：球分区和通用超平面（GH）分区。大多数现有工作仅在实验上证明了它们的优越性，而几乎没有找到理论证明。我们提出了一种统一现有数据分区方法并从理论上分析其性能的方法。首先，在理论上，我们通过证明彼此存在旋转来统一划分的两种基本形式。其次，我们展示了一些理论或实验结果，这些结果能够表明球分区优于 GH 分区。我们的工作在度量空间索引的理论研究上向前迈进了一步，并且能够为未来的索引设计提供指导。
Tree structure metric-space indexing methods recursively partition data according to their distances to a set of selected reference points (also called pivots). There are two basic forms of data partitioning: ball partition and General Hyper-plane (GH) partition. Most existing work only shows their superiority experimentally, and little theoretical proof is found. We propose an approach to unify existing data partitioning methods and analyze their performance theoretically. First, in theory, we unify the two basic forms of partitioning by proving that there are rotations of each other. Second, we show several theoretical or experimental results, which are able to indicate that ball partition outperforms GH partition. Our work takes a step forward in the theoretical study of metric-space indexing and is able to give a guideline of future index design.