Efficient skyline computation in metric space
Efficient skyline computation in metric space
复制标题
DOI：
10.1145/1516360.1516479
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
David Fuhry;R. Jin;Donghui Zhang
中科院分区：
文献类型：
--
作者：
David Fuhry;R. Jin;Donghui Zhang
给定一组n查询点，在一般度量空间中，一个度量空间天际线（MSS）查询询问数据库中所有这些查询点的最接近点是什么。在这里，考虑到任何点P，如果数据库中没有其他点的点较小或相等的距离，则P将P表示为最接近查询点的点之一。这个问题是对最近提出的空间基金线查询问题的直接概括，其中所有点位于两个或三维欧几里得空间中。它也与最近的邻居（NN）查询，范围查询和常见的天际线查询问题密切相关。在本文中，我们开发了新的算法来从搜索空间中积极修剪非基金点。我们还贡献了两种新的优化技术，以减少距离计算的数量和优势测试的数量。我们的实验评估显示了我们方法的有效性和效率。
Given a set of n query points in a general metric space, a metric-space skyline (MSS) query asks what are the closest points to all these query points in the database. Here, consider for any point p, if there are no other points in the database which have less or equal distance to all the query points, then p is denoted as one of the closest points to the query points. This problem is a direct generalization of the recently proposed spatial-skyline query problem, where all the points are located in two or three dimensional Euclidean space. It is also closely related with the nearest neighbor (NN) query, the range query and the common skyline query problem. In this paper, we have developed new algorithms to aggressively prune non-skyline points from the search space. We also contribute two new optimization techniques to reduce the number of distance computations and dominance tests. Our experimental evaluation has shown the effectiveness and efficiency of our approach.