道路网中针对多目标决策的兴趣点高效查询算法  

Efficient Query Algorithm of Points of Interest for Multi-Objective Decision-Making in Road Network

作　　者：李松[1] 杨晓龙 靳海鹏 张丽平[1] LI Song;YANG Xiaolong;JIN Haipeng;ZHANG Liping(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,150080哈尔滨

出　　处：《西安交通大学学报》2025年第4期148-157,共10页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(62072136);黑龙江省自然科学基金资助项目(LH2023F031)。

摘　　要：为了解决道路网中利用多目标决策技术进行兴趣点推荐和高效位置查询的问题,针对由于数据规模增加产生大量近似数据,导致传统多目标决策技术在道路网环境下查询效率和可用性方面较低的问题,提出了一种道路网广义近似Skyline查询算法。首先基于兴趣点的维度相似性和道路网近似性构建近似集和独立点,并根据兴趣点特性设计相应的剪枝策略;随后,通过近似集和独立点重构数据集,根据剪枝策略过滤掉当查询位置移动时对查询结果无影响的兴趣点,并构建AA-R*-Tree索引以提升查询效率;最后,根据兴趣点的近似性提出一种广义近似聚集支配算法,通过选取代表点代替近似集进行Skyline计算,减少冗余运算并优化查询结果,最终得到满足兴趣点近似整合有序的Skyline结果集。实验结果表明:所提近似查询算法在大规模数据集和大量相似数据条件下表现出较好的效率与可行性;与Higher-Gsky、MG-EGsky和GSSK-A算法相比,所提算法在数据规模、查询范围及路段数增加时的平均效率提升约14%,能够为道路网用户提供更快速有效的决策支持。To address the issue of point-of-interest(POI)recommendation and efficient location queries in road networks using multi-objective decision-making techniques,and to overcome the problem of low query efficiency and usability of traditional multi-objective decision-making techniques in road network environments due to the large amount of approximate data generated by increasing data scales,a generalized approximate skyline query(GAA-SQ)algorithm for road networks is proposed.Approximate sets and independent points are constructed based on POI dimensional similarity and road network proximity,and pruning strategies tailored to POI characteristics are designed.The dataset is then reconstructed using approximate sets and independent points.Based on pruning strategies,POIs that do not affect query results when the query location changes are filtered out,and an AA-R*-Tree index is built to enhance query efficiency.Finally,a generalized approximate aggregation domination algorithm is proposed based on the similarity of POI.By selecting representative points to substitute for the approximate set in Skyline computation,redundant calculations are reduced and query results are optimized.Ultimately,a Skyline result set is obtained that satisfies the approximate and integrated ordering of POI.Theoretical analysis and experimental results indicate that high efficiency and feasibility are exhibited by the proposed algorithm for large-scale datasets with substantially similar data.Compared with the Higher-Gsky,[JP3]MG-EGsky,and GSSK-A algorithms,the proposed algorithm achieves an average efficiency improvement of approximately 14%as data size,query range,and road segments increase,providing faster and more effective decision support for road network users.

关 键 词：道路网 SKYLINE查询 多目标决策 近似查询 兴趣点推荐 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]