论文标题
最佳度量搜索等同于最低统治设置问题
Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem
论文作者
论文摘要
在度量搜索中，最坏情况分析几乎没有价值，因为搜索总是退化为无行为数据的线性扫描。因此，在更细微的描述上，已经花费了很多努力，即实际上可以实现哪些绩效，包括诸如AESA家族之类的启发式基准以及统计代理，例如内在维度。本文以任何给定的数据集和查询实际上可以实现的最佳性能的精确表征达到了问题的核心。具体而言，在最佳度量搜索和最小主导设置问题之间的两个方向上都建立了线性时间目标保护降低，其贪婪的近似成为基于甲骨文的AESA等同的等同，并反复选择消除最多剩余点的枢轴。作为例证，AESA启发式措施适合淡化以前消除的点的作用，对原始及其年轻的相对Iaesa2产生了一些适度的性能改进。
In metric search, worst-case analysis is of little value, as the search invariably degenerates to a linear scan for ill-behaved data. Consequently, much effort has been expended on more nuanced descriptions of what performance might in fact be attainable, including heuristic baselines like the AESA family, as well as statistical proxies such as intrinsic dimensionality. This paper gets to the heart of the matter with an exact characterization of the best performance actually achievable for any given data set and query. Specifically, linear-time objective-preserving reductions are established in both directions between optimal metric search and the minimum dominating set problem, whose greedy approximation becomes the equivalent of an oracle-based AESA, repeatedly selecting the pivot that eliminates the most of the remaining points. As an illustration, the AESA heuristic is adapted to downplay the role of previously eliminated points, yielding some modest performance improvements over the original, as well as its younger relative iAESA2.
