摘要
基于位置的路网Skyline查询可根据用户的需求及用户所处的位置,从大量数据中快速返回给用户期望的数据,但已有的道路网络技术需要计算大量的路网距离及数据点间支配关系的运算,导致查询效率较低。提出一种基于路网数据点的倒排索引查询算法DSR。通过计算少量数据点的路网距离求得最终结果,减小路网距离计算的代价,从而加快数据点间支配关系的判定,提升查询效率。在此基础上,在数据点更新情况下给出算法的动态维护,仅通过维护少量数据,DSR即可以快速地计算出Skyline集合。实验结果表明,与SSI、BSS等算法相比,该算法具有较高的查询效率,且时间性能明显提升。
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.
作者
白梅
苌仕涵
王习特
BAI Mei;CHANG Shihan;WANG Xite(School of Information Science and Technology,Dalian Maritime University,Dalian,Liaoning 116000,China)
出处
《计算机工程》
CAS
CSCD
北大核心
2022年第1期127-134,共8页
Computer Engineering
基金
国家自然科学基金(61602076,61702072,61976032)
中国博士后科学基金面上项目(2017M611211,2017M621122,2019M661077)
辽宁省自然科学基金(20180540003)
赛尔网络下一代互联网技术创新项目(NGII20190902)。
