A cost model for similarity queries in metric spaces
A cost model for similarity queries in metric spaces
复制标题
DOI：
10.1145/275487.275495
复制
发表时间：
1998-05
期刊：
影响因子：
--
通讯作者：
P. Ciaccia;M. Patella;P. Zezula
中科院分区：
文献类型：
--
作者：
P. Ciaccia;M. Patella;P. Zezula
我们考虑的问题估计CPU（距离计算）和I/O成本处理范围和k-最近邻查询度量空间。与向量空间的特定情况不同，其中数据分布信息已被利用来导出用于预测多维访问方法的性能的成本模型，在通用度量空间中不存在这种可能性，这使得问题非常不同，并且需要新的方法。我们坚持认为，对象的距离分布可以有效地用于解决这个问题，并因此为M树访问方法[10]开发了一个具体的成本模型。我们的研究结果依赖于这样的假设，即索引数据集来自一个度量空间，该度量空间足够“均匀”（在概率意义上），即使相对于特定查询对象的距离分布是未知的，也可以进行可靠的成本估计。我们通过实验验证了该模型在真实的和合成数据集，并展示了如何使用该模型来调整M树，以尽量减少CPU和I/O成本的组合。最后，我们概述了如何应用相同的方法来导出vp-tree索引结构的成本模型[8]。
We consider the problem of estimating CPU (distance computations) and I/O costs for processing range and k-nearest neighbors queries over metric spaces. Unlike the specific case of vector spaces, where information on data distribution has been exploited to derive cost models for predicting the performance of multi-dimensional access methods, in a generic metric space there is no such a possibility, which makes the problem quite different and requires a novel approach. We insist that the distance distribution of objects can be profitably used to solve the problem, and consequently develop a concrete cost model for the M-tree access method [10]. Our results rely on the assumption that the indexed dataset comes from a metric space which is “homogeneous” enough (in a probabilistic sense) to allow reliable cost estimations even if the distance distribution with respect to a specific query object is unknown. We experimentally validate the model over both real and synthetic datasets, and show how the model can be used to tune the M-tree in order to minimize a combination of CPU and I/O costs. Finally, we sketch how the same approach can be applied to derive a cost model for the vp-tree index structure [8].