摘要： 基于位置的路网Skyline查询可根据用户的需求及用户所处的位置，从大量数据中快速返回给用户期望的数据，但已有的道路网络技术需要计算大量的路网距离及数据点间支配关系的运算，导致查询效率较低。提出一种基于路网数据点的倒排索引查询算法DSR。通过计算少量数据点的路网距离求得最终结果，减小路网距离计算的代价，从而加快数据点间支配关系的判定，提升查询效率。在此基础上，在数据点更新情况下给出算法的动态维护，仅通过维护少量数据，DSR即可以快速地计算出Skyline集合。实验结果表明，与SSI、BSS等算法相比，该算法具有较高的查询效率，且时间性能明显提升。

关键词: Skyline查询, 路网, 数据点更新, 倒排索引, 查询处理

Abstract: Location-based skyline queries can quickly return the expected information from massive data according to the user's needs and the user's location.However, the existing road network technologies require enormous calculations of road network distance and dominant relations between data points, which reduces the query efficiency.To solve the problem, an algorithm named DSR for inverted index query is proposed based on road network data points.The algorithm can get the final result by calculating the road network distance of a small number of data points, which greatly reduces the cost of calculating road network distance.The determination of the dominant relations between data points is also accelerated, and the query efficiency is improved.On this basis, the dynamic maintenance of the algorithm in the case of data point update is given.DSR can quickly calculate Skyline set only by maintaining a small amount of data.The experimental results show that compared with SSI, BSS and other algorithms, this algorithm displays higher query efficiency, and its performance grows with the data size.

Key words: Skyline query, road network, data point update, inverted index, query processing

中图分类号: 

• TP391