Proximity Matching Using Fixed-Queries Trees
Proximity Matching Using Fixed-Queries Trees
复制标题
DOI：
10.1007/3-540-58094-8_18
复制
发表时间：
1994-06
期刊：
影响因子：
--
通讯作者：
Ricardo Baeza-Yates;W. Cunto;U. Manber;Sun Wu
中科院分区：
文献类型：
--
作者：
Ricardo Baeza-Yates;W. Cunto;U. Manber;Sun Wu
我们提出了一种新的数据结构，称为固定查询树，用于寻找固定集合中在一定距离函数下与查询元素接近的所有元素。固定查询树可以用于任何距离函数，甚至不一定是度量，只要它满足三角不等。我们分析了固定查询树的几个性能参数，并给出了支持该分析的实验结果。固定查询树对于比较两个元素很昂贵的应用程序特别有效。
We present a new data structure, called the fixed-queries tree, for the problem of finding all elements of a fixed set that are close, under some distance function, to a query element. Fixed-queries trees can be used for any distance function, not necessarily even a metric, as long as it satisfies the triangle inequality. We give an analysis of several performance parameters of fixed-queries trees and experimental results that support the analysis. Fixed-queries trees are particularly efficient for applications in which comparing two elements is expensive.