基于最近邻法的Skyline查询研究

Research on Skyline Queries Based on Nearest-Neighbor

Skyline查询就是要查找数据集中不被其他点支配的所有点。由于Skyline查询在涉及多维空间数据库的应用领域中起着非常重要的作用,因而Skyline的计算受到了很大关注,特别是无需访问所有的数据点就能很快的返回Skyline点的算法。论文研究一种基于最近邻法Skyline查询方法,并对其作了分析。算法采用了R-树及堆结构,通过对目标数据集进行索引,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得算法能高效计算出数据集的Skyline;同时,算法所采用的分枝界定法可以使所访问的空间数据点数目大大减少;再者,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性。

Skyline query aims to find the points that are not dominated by any other points in the dataset. It has been becoming a hot topic due to its potential applications in multi dimensions. In particular, the Skyline points can be rapidly obtained without reading the entire database. In this paper, we introduce an algorithm for skyline query based on nearest - neighbor search, which exploits R - tree and heap to order entry, so that only a subset of them needs to be examined for computing the skyline result. It adopts the branch - and - bound paradigm to prune those points who dominated by other. The algorithm scans the dataset and the points are only compared with those detected Skyline points, thus the algorithm satisfies progressiveness.