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

李松; 杨晓龙; 靳海鹏; 张丽平

doi:10.7652/xjtuxb202504014

您当前的位置：

首页 >

文章列表页 >

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

—————————————————————— | 更新时间：2026-01-06

- 道路网中针对多目标决策的兴趣点高效查询算法
- Efficient Query Algorithm of Points of Interest for Multi-Objective Decision-Making in Road Network
- 西安交通大学学报 2025年59卷第4期页码：148-157
- 作者机构：
  
  哈尔滨理工大学计算机科学与技术学院， 150080，哈尔滨
- 作者简介：
  
  李松（1977—），男，教授；
  张丽平（通信作者），女，教授。
- 基金信息：
  
  国家自然科学基金资助项目(62072136);黑龙江省自然科学基金资助项目(LH2023F031)
- DOI：10.7652/xjtuxb202504014
  中图分类号： TP311
- 收稿：2024-11-21，
  
  网络首发：2025-01-21，
  
  纸质出版：2025-04-10
- 稿件说明：
移动端阅览
李松, 杨晓龙, 靳海鹏, 等. 道路网中针对多目标决策的兴趣点高效查询算法[J]. 西安交通大学学报, 2025,59(4):148-157.

LI Song, YANG Xiaolong, JIN Haipeng, et al. Efficient Query Algorithm of Points of Interest for Multi-Objective Decision-Making in Road Network[J]. Journal of Xi’an Jiaotong University, 2025, 59(4): 148-157.
李松, 杨晓龙, 靳海鹏, 等. 道路网中针对多目标决策的兴趣点高效查询算法[J]. 西安交通大学学报, 2025,59(4):148-157. DOI： 10.7652/xjtuxb202504014.

LI Song, YANG Xiaolong, JIN Haipeng, et al. Efficient Query Algorithm of Points of Interest for Multi-Objective Decision-Making in Road Network[J]. Journal of Xi’an Jiaotong University, 2025, 59(4): 148-157. DOI： 10.7652/xjtuxb202504014.

摘要

为了解决道路网中利用多目标决策技术进行兴趣点推荐和高效位置查询的问题，针对由于数据规模增加产生大量近似数据，导致传统多目标决策技术在道路网环境下查询效率和可用性方面较低的问题，提出了一种道路网广义近似Skyline查询算法。首先基于兴趣点的维度相似性和道路网近似性构建近似集和独立点，并根据兴趣点特性设计相应的剪枝策略；随后，通过近似集和独立点重构数据集，根据剪枝策略过滤掉当查询位置移动时对查询结果无影响的兴趣点，并构建AA-R*-Tree索引以提升查询效率；最后，根据兴趣点的近似性提出一种广义近似聚集支配算法，通过选取代表点代替近似集进行Skyline计算，减少冗余运算并优化查询结果，最终得到满足兴趣点近似整合有序的Skyline结果集。实验结果表明：所提近似查询算法在大规模数据集和大量相似数据条件下表现出较好的效率与可行性；与Higher-Gsky、MG-EGsky和GSSK-A算法相比，所提算法在数据规模、查询范围及路段数增加时的平均效率提升约14%，能够为道路网用户提供更快速有效的决策支持。

Abstract

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

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.

关键词

Keywords

references

WU Dingming , ZHANG Zhaofen , JENSEN C S , et al . Efficient skyline keyword-based tree retrieval on attributed graphs [J ] . IEEE Transactions on Knowledge and Data Engineering , 2024 , 36 ( 11 ): 6056 - 6070 .

DENG Ke , ZHOU Xiaofang , SHEN Hengtao . Multi-source skyline query processing in road networks [C ] // 2007 IEEE 23rd International Conference on Data Engineering . Piscataway, NJ, USA : IEEE , 2007 : 796 - 805 .

BAI Mei , WANG Qibo , CHANG Shihan , et al . Location-based skyline query processing technology in road networks [J ] . The Journal of Supercomputing , 2024 , 80 ( 3 ): 3183 - 3211 .

CAI Zhi , CUI Xuerui , SU Xing , et al . Speed and direction aware skyline query for moving objects [J ] . IEEE Transactions on Intelligent Transportation Systems , 2022 , 23 ( 4 ): 3000 - 3011 .

LI Qiyan , ZHU Yuanyuan , YE Junhao , et al . Skyline group queries in large road-social networks revisited [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 35 ( 3 ): 3115 - 3129 .

ATTIQUE M , AFZAL M , ALI F , et al . Geo-social top- k and skyline keyword queries on road networks [J ] . Sensors , 2020 , 20 ( 3 ): 798 .

LIU Ziyi , LI Lei , ZHANG Mengxuan , et al . FHL-cube: multi-constraint shortest path querying with flexible combination of constraints [J ] . Proceedings of the VLDB Endowment , 2022 , 15 ( 11 ): 3112 - 3125 .

郝晋瑶 , 牛保宁 , 康家兴 . 大规模路网图下关键词覆盖最优路径查询优化 [J ] . 软件学报 , 2020 , 31 ( 8 ): 2543 - 2556 .

HAO Jinyao , NIU Baoning , KANG Jiaxing . Optimization of keyword-aware optimal route query on large-scale road networks [J ] . Journal of Software , 2020 , 31 ( 8 ): 2543 - 2556 .

朱睿 , 宋栿尧 , 王斌 , 等 . 高速流环境下近似连续 k 代表轮廓查询算法 [J ] . 软件学报 , 2023 , 34 ( 3 ): 1425 - 1450 .

ZHU Rui , SONG Fuyao , WANG Bin , et al . Approximate continuous k representative skyline query algorithm over high-speed streaming data environment [J ] . Journal of Software , 2023 , 34 ( 3 ): 1425 - 1450 .

YUAN Dengke , ZHANG Liping , LI Song , et al . Skyline query under multidimensional incomplete data based on classification tree [J ] . Journal of Big Data , 2024 , 11 ( 1 ): 72 .

BAI Mei , HAN Yuxue , YIN Peng , et al . S_IDS: an efficient skyline query algorithm over incomplete data streams [J ] . Data & Knowledge Engineering , 2024 , 149 : 102258 .

李松 , 王冠群 , 郝晓红 , 等 . 面向推荐系统的多目标决策优化算法 [J ] . 西安交通大学学报 , 2022 , 56 ( 8 ): 104 - 112 .

LI Song , WANG Guanqun , HAO Xiaohong , et al . A multi-objective decision optimization algorithm for recommendation system [J ] . Journal of Xi'an Jiaotong University , 2022 , 56 ( 8 ): 104 - 112 .

LIU Ziyi , LI Lei , ZHANG Mengxuan , et al . Approximate skyline index for constrained shortest pathfinding with theoretical guarantee [C ] // 2024 IEEE 40th International Conference on Data Engineering (ICDE) . Piscataway, NJ, USA : IEEE , 2024 : 4222 - 4235 .

WANG Zuan , DING Xiaofeng , JIN Hai , et al . Efficient secure and verifiable location-based skyline queries over encrypted data [J ] . Proceedings of the VLDB Endowment , 2022 , 15 ( 9 ): 1822 - 1834 .

ZHANG Guopeng , CHEN Xuebin , JIA Yuanli , et al . Support personalized weighted local differential privacy skyline query [J ] . Security and Communication Networks , 2022 , 2022 ( 1 ): 9075470 .

WANG Zuan , DING Xiaofeng , LU Junfeng , et al . Efficient location-based skyline queries with secure R-tree over encrypted data [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 35 ( 10 ): 10436 - 10450 .

白梅 , 王习特 , 李冠宇 , 等 . 基于最大覆盖的代表Skyline问题的优化算法研究 [J ] . 计算机学报 , 2020 , 43 ( 12 ): 2276 - 2297 .

BAI Mei , WANG Xite , LI Guanyu , et al . Research on optimization algorithms of k-maximum coverage skyline queries [J ] . Chinese Journal of Computers , 2020 , 43 ( 12 ): 2276 - 2297 .

李松 , 窦雅男 , 郝晓红 , 等 . 道路网环境下 K -支配空间Skyline查询方法 [J ] . 计算机研究与发展 , 2020 , 57 ( 1 ): 227 - 239 .

LI Song , DOU Yanan , HAO Xiaohong , et al . The method of the K -dominant space skyline query in road network [J ] . Journal of Computer Research and Development , 2020 , 57 ( 1 ): 227 - 239 .

李松 , 宾婷亮 , 郝晓红 , 等 . 道路网多用户偏好Top- k 天际线查询方法 [J ] . 计算机研究与发展 , 2023 , 60 ( 10 ): 2348 - 2358 .

LI Song , BIN Tingliang , HAO Xiaohong , et al . Multi-User preference top- k skyline query method based on road network [J ] . Journal of Computer Research and Development , 2023 , 60 ( 10 ): 2348 - 2358 .

WANG Kangao , HAN Xixian , WAN Xiaolong , et al . Efficient computation of top- k G-skyline groups on large-scale database [J ] . Information Sciences , 2024 , 670 : 120614 .

NADOURI S , HADJALI A , SAHNOUN Z . RG-SKY: a fuzzy group skyline relaxation for combinatorial decision making [J ] . Computer Science and Information Systems , 2022 , 19 ( 2 ): 887 - 912 .

VLACHOU A , DOULKERIDIS C , ROCHA-JUNIOR J B , et al . Decisive skyline queries for truly balancing multiple criteria [J ] . Data & Knowledge Engineering , 2023 , 147 : 102206 .

XIA Tian , ZHANG Donghui , TAO Yufei . On skylining with flexible dominance relation [C ] // 2008 IEEE 24th International Conference on Data Engineering . Piscataway, NJ, USA : IEEE , 2008 : 1397 - 1399 .

YIN Bo , WEI Xuetao , LIU Yonghe . Finding the informative and concise set through approximate skyline queries [J ] . Expert Systems with Applications , 2019 , 119 : 289 - 310 .

AWASTHI A , BHATTACHARYA A , GUPTA S , et al . K-dominant skyline join queries: extending the join paradigm to K-dominant skylines [C ] // 2017 IEEE 33rd International Conference on Data Engineering (ICDE) . Piscataway, NJ, USA : IEEE , 2017 : 99 - 102 .

SALTOS R , WEBER R . Generalized black hole clustering algorithm [J ] . Pattern Recognition Letters , 2023 , 176 : 196 - 201 .

HUANG Xiaogang , MA Tiefeng , LIU C , et al . GriT-DBSCAN: a spatial clustering algorithm for very large databases [J ] . Pattern Recognition , 2023 , 142 : 109658 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

隧道内燃料电池汽车氢气泄漏扩散特性及影响因素

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析

超临界水异常区域热力学特性研究

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

冷库水平空气幕热湿阻隔性能数值模拟研究