关键词: 通用Skyline查询, R树索引, 非空间属性, 最近邻

Abstract: As one of the important methods for multi-criteria decision making problems, the Skyline query processing technologies have been widely studied in many applications. This paper proposes the general Skyline query processing technology combining with non-spatial attributes while R tree is adopted to index the facility set and the dataset. Two algorithms are provided to compute the Skyline results. The first algorithm is the extension of Skyline query algorithm based on all nearest neighbor method, which cuts off part of the dataset by computing the static Skyline results. The second algorithm is based on incremental nearest neighbor method, which utilizes the facility oriented searching method. The algorithm calculates the farthest distances between the static Skyline results and each type of facilities. The distances are set to bound thresholds so as to cut off data points which are farther than them. For the left points, data oriented search method is used to compute the nearest facilities of all types. After that, the distances between the data points and the facilities are mapped to the multi-dimensional distance space so as to compute the Skyline result combining with non-spatial attributes. The experimental results show that for the second algorithm the number of I/Os and CPU time are greatly reduced thus improves the computational efficiency.

Key words: general Skyline queries, R-tree index, non-spatial attributes, nearest neighbor