道路網中針對多目標決策的興趣點高效查詢算法

摘要：為了解決道路網中利用多目標決策技術進行興趣點推薦和高效位置查詢的問題，針對由于數據規模增加產生大量近似數據，導致傳統多目標決策技術在道路網環境下查詢效率和可用性方面較低的問題，提出了一種道路網廣義近似Skyline查詢算法。首先基于興趣點的維度相似性和道路網近似性構建近似集和獨立點，并根據興趣點特性設計相應的剪枝策略；隨后，通過近似集和獨立點重構數據集，根據剪枝策略過濾掉當查詢位置移動時對查詢結果無影響的興趣點，并構建AA-R*-Tree索引以提升查詢效率；最后，根據興趣點的近似性提出一種廣義近似聚集支配算法，通過選取代表點代替近似集進行Skyline計算，減少冗余運算并優化查詢結果，最終得到滿足興趣點近似整合有序的Skyline結果集。實驗結果表明：所提近似查詢算法在大規模數據集和大量相似數據條件下表現出較好的效率與可行性；與Higher-Gsky、MG-EGsky和GSSK-A算法相比，所提算法在數據規模、查詢范圍及路段數增加時的平均效率提升約14%，能夠為道路網用戶提供更快速有效的決策支持。

關鍵詞：道路網；Skyline查詢；多目標決策；近似查詢；興趣點推薦

中圖分類號：TP311 文獻標志碼：A

DOI：10.7652/xjtuxb202504014 文章編號：0253-987X（2025）04-0148-10

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

LI Song， YANG Xiaolong， JIN Haipeng， ZHANG Liping

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

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：road network; Skyline query; multi-objective decision; approximate query; point of interest recommendation

在道路網信息處理系統中，興趣點查詢是實現地圖導航和位置服務的重要基礎，其主要目標是通過精準高效的查詢機制，幫助用戶快速找到與需求相關的地點，例如餐館、加油站、醫院、景點等，為用戶提供便捷的出行和生活服務。然而，由于不同人群的自身情況各異，需求的差異性多樣性不斷增大，多目標決策技術在興趣點查詢中的重要性也不斷提升。在興趣點查詢中引入多目標決策技術可以更全面地優化系統表現、提升個性化和用戶體驗，使得興趣點查詢不僅能提供更精準的查詢結果，還能在多維度上更好地服務用戶。Skyline查詢^［1］作為多目標決策中的重要技術有助于提高多目標決策的效率。例如，在路網興趣點查詢中，用戶不僅關心位置的相關性，還會考慮其他因素（如距離、價格、評分等）。Skyline查詢用于獲取數據集合中在不同維度上的最優點，廣泛應用于決策支持、興趣點選取、推薦系統等領域。

近些年，道路網環境下的Skyline查詢是熱點問題之一，Deng等^［2］首次將Skyline查詢引入到道路網環境中。Bai等^［3］提出一種改進的基于位置的道路網Skyline查詢，指在快速計算路網下的Skyline查詢。Cai等^［4］提出了一種速度和方向感知的Skyline查詢方法，通過考慮用戶的移動速度和方向來為用戶提供Skyline查詢區域。Li等^［5］致力于找到一組天際線凝聚群，其中每個群體在社會凝聚力和空間凝聚力方面都不能被任何其他群體支配。Attique等^［6］基于空間、文本和社會相關性對數據對象進行排序，在道路網Skyline查詢問題中引入了地理社交。Liu等^［7］提出了一種基于Skyline Cube的FHL索引，利用從低維路徑推導高維路徑的方法，高效解決了靈活多約束最短路徑場景中的查詢問題。郝晉瑤等人^［8］提出一種大規模路網圖下關鍵詞覆蓋最優路徑查詢算法KORL，通過路網圖劃分、近似支配剪枝等策略高效地搜索近似最優解。

隨著Skyline查詢的不斷發展，衍生出許多致力于適配用戶需求的變種問題，朱睿等^［9］提出高速流環境下近似連續 k 代表Skyline查詢算法，給定滑動窗口和連續查詢監聽窗口中的數據，查詢返回窗口中組合支配面積最大的 k 個對象。Yuan等^［10］和Bai等^［11］解決了不完整數據下的Skyline查詢問題，在多維不完全數據中高效和準確的返回結果。李松等^［12］提出了一種基于范圍的障礙空間連續Skyline查詢算法，用于解決由于查詢者位置的移動和空間障礙物的位置變化導致傳統多目標決策技術的查詢效率較低的問題。Liu等^［13］介紹了a-FHL方法，旨在避免昂貴的天際線路徑搜索并加快天際線路徑索引的計算。Wang等^［14］和Zhang等^［15］針對Skyline查詢中存在的隱私泄露問題，提出了保護用戶位置隱私和查詢結果集隱私的方法。Wang等^［16］進一步提出了一種基于位置的高效 Skyline 查詢SecSky，目的是在保護數據集隱私的同時降低計算開銷。

現實中隨著物聯網與互聯網協調發展，Skyline查詢結果集規模缺乏有效控制，難以提供有效決策支持，因此控制Skyline結果集規模也是值得注意的問題。白梅等^［17］提出一種基于最大覆蓋的代表Skyline查詢，選取 k 個最具代表性的Skyline查詢元組，并通過貪心算法提高效率，但是沒有考慮路網空間環境。李松等^［18-19］融合道路網和 K 支配的概念提出了路網 K 支配 Skyline查詢，從用戶角度出發精煉Skyline結果集并且提高查詢效率，但是沒有考慮數據點間的關系以及數據點的路網分布。Wang等^［20］提出了一種名為TGPE的有效算法，用以快速計算大規模數據庫的前 k 個G-Skyline組。Nadouri等^［21］提出通過使群體Skyline支配更為嚴格，使得一些群體保持不可比性，從而擴展群體Skyline，但是擴展后的結果集很難符合用戶期望。Vlachou等^［22］提出一種真正平衡多個標準的決定性Skyline查詢，尋找Skyline結果集中盡可能好的數據對象，但是存在效率低的問題。Xia等^［23］提出一種 ε -Skyline查詢方法對Skyline結果集進行增大或減小并反映用戶偏好，當 ε 為正或為負時， ε -Skyline 可以小于或大于傳統Skyline。當 ε =0時， ε -Skyline即是傳統Skyline，該方法沒有考慮路網環境且全部數據進行運算存在效率問題。Yin等^［24］通過選擇一個對象代表附近相似的對象，避免用戶重復掃描相似對象。該對象可以來自數據集或結果集，但是數據集的方法存在效率問題，而結果集的方法可用性相對較低。

隨著數據規模的增長，傳統路網Skyline查詢的效率和可用性顯著降低。一方面，數據量的增加導致大量路網距離運算，降低了查詢效率；另一方面，大量近似數據使得結果集難以支持多準則決策，用戶難以從大量數據中快速選擇，同時還可能遺漏與Skyline點僅有微小差異但符合用戶興趣的數據點?，F有路網Skyline查詢較少關注興趣點的空間分布及維度相似性。例如，路網上的興趣點在價格、評分等方面可能差異極小，但傳統算法容易忽略這些細微但重要的差異。用戶在到達某個興趣點后，通常會便利地訪問周邊興趣點，因此，通過近似興趣點的查詢，可以幫助用戶快速切換選擇，更好地滿足需求，同時提高結果集的可解釋性和實用性。

傳統的近似Skyline查詢通常直接對Skyline結果集或對數據集進行近似處理，不能將擴展的興趣點進行整合，并且沒有從興趣點出發考慮興趣點之間的近似關系。此外，傳統控制Skyline結果集規模的查詢算法未考慮到在道路網環境下的距離維度，也未考慮到興趣點在道路網絡環境中的空間分布。因此，本文基于興趣點的空間分布以及興趣點之間的近似關系提出一種道路網廣義近似Skyline查詢算法。

1 基本定義

道路網廣義近似Skyline查詢是路網Skyline查詢的變體問題，

涉及興趣點集P、道路網、路網近似范圍和屬性近似范圍。本文設定數據集P具有k個維度，其中第k維為路網空間屬性維度，假定一組k－1個非空間屬性閾值Λ={λ1， λ2，…， λk－1}。其中λi（1≤i≤k－1）為數據點集P的第i個非空間屬性閾值，假定ε為第k維路網空間屬性維度閾值其相關的主要定義如下。

定義1 非空間屬性支配^［25］ 設p1，p2為數據集P中的兩個興趣點，對于任意的i，1≤i≤k－1使得p1（i）≤p2（i）且滿足p1（j）lt;p2（j）（j， 1≤j≤k－1）則稱p2非空間支配p1，記作p2k－1p1。

定義2 道路網支配 給定道路網環境下查詢點q以及興趣點p1和p2，用d（q， p1）表示q與p1之間的路網距離，若滿足2個條件其中1個時：

（1）p2k－1p1，且滿足d（q， p1）≤d（q， p2）；

（2）p1（i）=p2（i）（i， 1≤i≤k-1），且d（q， p1）lt;d（q， p2）；

則稱p2道路網支配p1，記作p2p1。

定義3 興趣點非空間相似給定興趣點p1和p2以及設定的一組非空間屬性閾值Λ={λ1， λ2，…， λk－1}，若滿足|p1（i）－p2（i）| ≤λi（i， 1≤i≤k-1）則稱興趣點p1和p2非空間相似，記作p1p2。

定義4 興趣點道路網近似 給定道路網環境下興趣點p1和p2，d（p1， p2）為p1和p2之間的路網距離，當且僅當滿足下面兩個條件時，稱p1和p2道路網近似，記作p1p2：

（1）興趣點p1和p2非空間相似，即p1p2；

（2）d（p1，p2）≤ε，興趣點p1和p2在道路網環中的路網距離小于等于距離閾值ε。

定義5 近似集與獨立點 近似集由彼此非空間相似的點組成，并且對于p∈C，p′∈C，存在p1p2，近似集視作一個整體數據對象不可分割；那些不存在于任何近似集的興趣點稱為獨立點，記作。

定義6 位置最佳點存在p∈C，位置最佳點p滿足 min （ max （d（p，pi））），pi∈C，p≠pi，pi為近似集C中任意與p不相同的點，位置最佳點是近似集中距離最遠興趣點最近的興趣點。近似集中興趣點共享同一距離維度值，該距離維度值由位置最佳點的路網維度值確定。

定義7 近似數據打分函數記作

F（pi）=ψi∑rj=1ψji∏k－1j=1（pi（j）/λj）^ζj

pi（j）≠0; λj≠0（1）

式中：ψi為近似集內第i個興趣點的歷史訪客數量；r為近似集中興趣點數量；r為近似集整體歷史訪客數量；k－1為非空間屬性數；pi（j）為第i個興趣點在第j個屬性上的取值；λj為非空間第j個屬性維度上的閾值；ζj為第j屬性的屬性優劣值，當第j屬性上取值越大優勢越大時，ζj取值為1，反之ζj取值為－1；i為用戶評價指標，近似集中分數最高的點被稱為近似集的代表點。

定義8 廣義近似聚集支配 給定道路網中兩個數據對象o1和o2（數據對象可以是近似集或者獨立點），若o1廣義近似聚集支配o2，記作o1o2。

（1）給定興趣點1和2是數據集O中的兩個獨立點，若滿足12，則有12；反之若滿足21，則有21；

（2）給定獨立點和近似集C是數據集O中的兩個數據對象，興趣點pi是近似集C的代表點，若滿足p i ，則有C；反之，若滿足pi，則有C；

（3）給定近似集C和近似集C′是數據集O中的兩個數據對象，興趣點pi和pj分別是近似集C和近似集C′的代表點，若滿足pipj，則有CC′；反之，若滿足pjpi，則有C′C。

定義9 道路網廣義近似 Skyline 查詢 給定一個查詢點q和一個k維興趣點集P，以及道路網路段集合R。預先對興趣點集P進行道路網近似計算形成包含近似集和獨立點的數據集O。道路網廣義近似 Skyline 查詢結果返回數據集O的子集，其中所有獨立點或近似集不被數據集O中其他獨立點或近似集廣義近似聚集支配。這些獨立點或者近似集被稱為道路網廣義近似Skyline對象，記為GAA-SQ（q，O，R）， 道路網廣義近似Skyline查詢簡稱為GAA-SQ查詢。

道路網廣義近似Skyline查詢首先對道路網環境中存在的大量鄰近相似的興趣點進行聚集，形成近似集和獨立點，然后對近似集的獨立點進行道路網廣義近似聚集支配判斷，得到結果集，下面給出具體示例。給定一個查詢點q，表1表示道路網中賓館數據對象的屬性表。其包括賓館的非空間屬性以及與查詢點q的路網距離屬性。表1中，給定三維屬性興趣點p1、p2、p3、p4、p5、p6、p7、p8的屬性值，分別對應價格和舒適度，第3維則為興趣點到查詢點q的路網距離屬性，表示為d（q， p）。

首先進行道路網近似計算，給定非空間閾值Λ={20，1}，價格閾值為20元，舒適度閾值為1，路網距離閾值ε=50。圖1展示了表1中8個賓館之間的相鄰情況，其中興趣點p4、p5、p6組成一個近似集C1，而興趣點p7、p8構成了另一個近似集C2。獨立點則為p1、p2、p3。雖然興趣點p1與興趣點p4、p5、p6非空間相似，但由于它們之間的道路網距離大于距離閾值，所以p1不屬于近似集C1。同樣，雖然p2、p3之間的道路網距離小于距離閾值，但因為它們不滿足興趣點的非空間相似，所以也無法形成近似集。在對道路網近似計算得到的獨立點和近似集進行道路網廣義近似 Skyline 查詢時，p2、p3被{p4，p5，p6}廣義近似聚集支配，而p1廣義近似聚集支配{p7，p8}。因此，道路網廣義近似 Skyline 查詢的結果為{p1，{p4，p5，p6}}。

2 道路網廣義近似Skyline查詢

本文主要分為2個主要過程：興趣點道路網近似計算預處理過程和道路網廣義近似Skyline查詢過程。首先對興趣點集 P 進行道路網近似計算形成包含近似集和獨立點的數據集 O ，然后對數據集 O 進行廣義近似聚集Skyline查詢。

2.1 道路網近似計算

本節首先對數據集進行道路網近似計算，將路網中相鄰且相似的興趣點聚集成近似集，并提出了三種剪枝規則，以提前過濾部分興趣點。通過選取近似集中位置最佳的興趣點，并結合近似數據評分函數對其進行排序，實現了Skyline查詢結果集的多樣化。此舉有效減少了大量近似點之間的支配判斷，從而提升了查詢效率。

道路網近似計算主要通過聚集道路網中近鄰且相似的興趣點形成近似集，運用DBSCAN算法^［26-27］聚集那些滿足道路網近似的興趣點，并進一步進行非空間相似性判斷，篩選出符合條件的興趣點構建近似集。近似集的構建不僅多樣化了查詢結果集，還減少了近似點間的冗余支配判斷，同時有效約減了部分興趣點。

定理1 已知存在興趣點p屬于近似集C，如果興趣點p的ε路網距離內存在其他興趣點p′，興趣點p′滿足與近似集C中任意興趣點非空間相似，則將興趣點p′加入近似集C。

證明 已知存在興趣點p屬于近似集C，興趣點p為近似集C中一點，p′滿足與近似集C中任意興趣點非空間相似，并且興趣點p′與興趣點p之間的路網距離小于距離閾值ε，所以興趣點p′與興趣點p之間滿足興趣點道路網近似，所以可以將興趣點p′加入近似集C，使得新的集合C仍然為近似集。

剪枝規則1 設興趣點p1和p2屬于興趣點集P，且興趣點p2不屬于任何近似集，若滿足d（p1， p2）lt;ε，| p1（i）-p2（i）| gt;λi（i， 1≤i≤k－1），并且存在p2非空間支配p1即p2k-1p1，則將興趣點p1剪枝。

證明 設興趣點集P中存在兩個興趣點p1和p2，p2不屬于任何近似集，滿足d（p1， p2）lt;ε，路網距離閾值ε相對于d（p1， p2）可忽略，因此，p1和p2可以視為位于路網中的同一位置，因為| p1（i）－p2（i）| gt;λi（i， 1≤i≤k－1），p1和p2不在同一個近似集中。所以當查詢點變化時，始終有p2p1，興趣點p1可被剪枝。

剪枝規則2 設興趣點p和近似集C，興趣點p和近似集C中興趣點均屬于興趣點集P，若滿足d（p， pj）lt;ε（pj∈C），興趣點p與近似集C構成的新集合不為近似集，并且近似集C中存在興趣點pi非空間支配p即pik-1p，則將興趣點p剪枝。

證明 因為滿足d（p， pj）lt;ε（pj∈C），由剪枝規則1的證明可知，興趣點p和近似集C可以視為在道路網中的同一位置，又因為興趣點p與近似集C構成的新集合不為近似集，并且近似集C中存在興趣點pi非空間支配p即pik-1p，所以當查詢點變化時，始終有Cp，所以興趣點p可被剪枝。

剪枝規則3 設興趣點p和近似集C中興趣點均屬于興趣點集P，若滿足d（p， pj）lt;ε（pj∈C），興趣點p與近似集C構成的新集合不為近似集，并且pk-1pi，pi∈C， 則將近似集C剪枝。

證明 同剪枝規則2證明，興趣點p和近似集C可以視為在道路網中的同一位置，又因為興趣點p與近似集C構成的新集合不為近似集，并且pk-1pi，pi∈C，所以當查詢點變化時，始終有pC，所以興趣點p可被剪枝。

基于定理1，以及剪枝規則1～3，本節進一步給出道路網近似計算算法 O-RNAC ，構造可以多樣化查詢結果的近似集，減少近似點之間的支配判斷，同時可以約減部分興趣點，如算法1所示。

算法1 "O-RNAC （P， Λ， ε， R）

輸入：興趣點集P、非空間閾值Λ={λ1， λ2，…， λk－1}、路網距離閾值ε、道路網路段集合R；

輸出：道路網近似計算包含近似集C和獨立點的數據集O。

1. O←；

2. "for "興趣點集P未被訪問的興趣點p "do

3. "創建近似集C， 近似集C←p；

4. "候選集N←興趣點p的ε鄰域內未被訪問過的興趣點；

5. ""for every point "p′∈N "do

6. ""if "p′pi， pi∈C "then

7. ""C←C+ p′；

8. ""N←N+興趣點p′的ε鄰域內未被訪問過的興趣點；

9. ""else if "pik-1p′，pi∈C "then

10. "興趣點p′被剪枝；

11. "else if "p′k-1pi， pi∈C "then

12. "候選集N←興趣點p′的ε鄰域內未被訪問過的興趣點；

13. "近似集C←p′；

14. "if "C. "length gt;1 "then

15. ""min （ max （d（p，pi）））， pi∈C， p≠pi計算近似集C的位置最佳點；

16. "通過近似數據打分函數對近似集C進行排序，確定近似集代表點；

17. "O←O+C；

18. "else if "C. "length=1 then

19. "標記C中唯一點p為獨立點；

20. "O←O+；

21. C←；

22. "return "O；

道路網近似計算 O-RNAC 由算法1實現。訪問數據集中未被訪問過的興趣點，將該興趣點道路網距離閾值ε領域內存在的其他未被訪問的興趣點加入候選集N。遍歷候選集N中興趣點，如果該興趣點與當前近似集合并后仍為近似集，則將該興趣點加入當前近似集，并將該興趣點ε領域內存在的其他未被訪問的興趣點加入候選集N；如果該興趣點支配當前近似集，并且該興趣點與當前近似集構成的集合不為近似集，則刪除該近似集，將候選集清空，從該興趣點開始重新創建近似集；如果近似集有且只有一個興趣點存在，則將該興趣點標記為獨立點，加入結果集；如果近似集存在多于一個的興趣點，則將近似集加入結果集，并且選取近似集位置最佳點以及對近似集內部興趣點進行打分排序。最后返回包含近似集和獨立點的數據集O。

當道路網數據集P數據點增加時，對預處理數據集O進行更新操作。若此數據點p與ε鄰域內的獨立點p′非空間相似，則將數據點p和數據點p′形成近似集加入數據集O；若此數據點p與近似集內所有點非空間相似，且近似集內存在點在數據點p的ε鄰域內，則將數據點p加入該近似集，更新數據集O；若數據點p的ε鄰域內不存在與之非空間相似的數據點，則將數據點p標記為獨立點加入數據集O。更新數據集O。

2.2 AA-R*-Tree索引

傳統的R*-Tree無法有效存儲路網中存在的大量近似集，且近似集內興趣點的重復計算也增加了計算開銷。為了更高效地存儲這些近似集并減少計算開銷，本文提出了AA-R*-Tree索引結構。利用近似集位置最佳點替代近似集進行索引構建，可以有效存儲近似集結構以及進一步減少計算開銷。圖2展示了所提AA-R*-Tree索引結構的示例。將道路網中的近似集視為一個數據對象，在近似集中選取位置最佳點。用位置最佳點的路網距離維度代替整個近似集中所有其他點的路網維度屬性，以近似集位置最佳點代替該近似集進行R*-Tree索引的構建。

AA-R*-Tree索引結構的示例如圖2所示，其中興趣點p5、p7、p13分別是其所在近似集的位置最佳點。在AA-R*-Tree的葉子節點中構建三元組，第1位存儲興趣點，第2位存儲該興趣點的類型，0表示該興趣點為獨立點，1表示該興趣點為近似集的位置最佳點，第3位則存儲該點代表的近似集，1表示空集。在近似集內，興趣點按評分順序存儲，剪枝操作時將近似集視為一個整體進行處理。同一個近似集中的數據對象的道路網距離屬性相同，由近似集位置最佳點的路網屬性確定。

2.3 道路網廣義近似Skyline查詢

本節通過2.1節計算得到的數據集O進行廣義近似聚集支配計算，將每個近似集視為一個數據對象進行道路網廣義近似Skyline查詢。本節以定理的形式給出廣義近似聚集支配中獨立點之間、近似集之間以及獨立點與近似集之間支配關系的近似簡化判斷算法，查詢返回滿足廣義近似聚集支配的Skyline結果集。

定理2 給定興趣點1和2是數據集O中的兩個獨立點，若滿足12，則有12；反之若滿足21，則有21。

證明 由廣義近似聚集支配定義可知，獨立點之間的支配判斷符合傳統道路網支配判斷，若滿足獨立點1道路網支配2，則一定滿足獨立點1廣義近似聚集支配2，記作12。

定理3 給定獨立點和近似集C是數據集O中的兩個數據對象，興趣點p是近似集C的代表點，如果p，若d（q， ）lt;d（q， p），則C，其中q為查詢點，反之若d（q， p） lt; d（q， ），則C；如果和p不滿足非空間相似，若p，則有C，反正若p，則有C。

證明 如果p，則和p在非空間屬性下相似相等的，而d（q，）lt;d（q， p），的距離維度占優，所以p進而C，同理當d（q， p） lt; d（q，），有C；如果和p不滿足非空間相似，若p，通過廣義近似聚集支配定義可得p，p為近似集C的代表點，所以可以得出C，同理若p，則有C。

定理4 給定近似集C和近似集C′是數據集O中的兩個數據對象，興趣點p1是近似集C的代表點，興趣點p2是近似集C′的代表點，如果p1p2，當d（q，p1）lt;d（q， p2），則CC′，若d（q， p2）lt;d（q， p1），則C′C；當p1與p2不滿足非空間相似時，若p1p2，則可以得出p1p2，進而得出CC′，反之若p2p1則可以得出C′C。

證明 同定理3的證明，代表點代表了所在的近似集，當兩個代表點非空間相似時，代表兩個近似集非空間相似，距離查詢點越近的近似集占優；當兩個代表點不相似時，由定理3的證明同樣可以得出，若p1p2，則CC′，反之亦然。

考慮道路網環境下興趣點空間分布情況以及維度相似性的情況下進行 Skyline 查詢，基于定理2～4以及 AA-R*-Tree 索引結構，將近似集視作一個整體數據對象，對算法1計算得到的數據集O進行道路網廣義近似聚集支配近似查詢計算，快速得到滿足數據近似整合有序的 Skyline 結果集，進一步給出 GAA-SQ 查詢算法，如算法2所示。

算法2 "GAA-SQ "（q， O， R）

輸入：查詢點q、包含近似集C和獨立點的數據集O、道路網路段集合R；

輸出：道路網廣義近似 Skyline 查詢的結果集S。

1. 以O中的獨立點、近似集、道路網路段創建 AA-R*-Tree 索引結構；

2. S←；

3. 遍歷數據集O中的數據對象oi進行廣義近似聚集 Skyline 支配判斷；

4. "if "oi∈O，oj∈O且oi與oj均為獨立點 then

5. "獨立點間進行道路網支配判斷；

6. "if "∈O，C∈O并且為獨立點，C為近似集 then

7. ""if 近似集C的代表點p與非空間相似 then

8. ""判斷d（q， ）與d（q， p）的大??；

9. ""else

10. "代表點p與進行道路網支配判斷；

11. "if "C∈O，C′∈O且C與C′均為近似集 then

12. ""if 近似集C的代表點p1與近似集C′的代表點p2非空間相似 then

13. "判斷d（q， p1）與d（q， p2）的大??；

14. ""else

15. "代表點p1與p2進行道路網支配判斷；

16. 更新結果集S；

17. "return "S；

道路網廣義近似 Skyline 查詢通過算法2實現，算法2通過2.1節計算得到的數據集O進行道路網廣義近似 Skyline 查詢。分別進行獨立點之間、近似集之間以及獨立點與近似集之間支配關系的廣義近似支配簡化判斷算法，得到結果集S，結果集S中的數據對象均不被S中其他的數據對象廣義近似聚集支配，最終，結果集S就是道路網廣義近似 Skyline 查詢的結果集。

3 實驗比較與分析

本節對本文所提出的GAA-SQ算法進行了實驗與性能評估。由于道路網廣義近似Skyline查詢是本文研究的一個新問題，現有的研究成果無法直接應用，因此為了構造對比算法，本文對文獻［24］中的兩個算法進行了適當修改，使其適用于道路網環境，并針對給定查詢問題，通過反復調用和尋找相近的數據集進行調整。修改后的算法分別命名為Higher-Gsky算法和MG-EGsky算法；此外，本文還對文獻［6］中的GSSK-A算法進行了適當修改，引入近似集的概念，從而形成與本文提出的GAA-SQ算法的對比算法。

3.1 數據集及實驗環境設置

本文實驗采用真實道路網數據集，從加利福尼亞道路網數據集以及加利福尼亞的數據點（http：//www.cs.utah.edu/～lifeifei/SpatialDataset.htm）中一片區域抽取10000個節點對象和5000個線段對象（線段作為道路網線段）。查詢用戶采用隨機生成的方式。本文使用道路網近似計算處理數據集中近似興趣點，并使用AA-R*-Tree索引結構組織處理后的數據集。

實驗環境：8GB內存、Core（TM） i7-12700H CPU@2.70GHz處理器、500GB硬盤，Windows11操作系統上用IntelliJ IDEA 2021.3.2開發平臺Java語言實現。實驗需要驗證4個算法的查詢性能，數據集最大維度為4。每個實驗采取單一變量原則，其余變量為默認值，實驗結果取50次實驗運行的平均值。

3.2 算法對比

圖3給出了4種算法在不同數據規模下CPU運行時間的變化對比情況。CPU運行時間隨著數據規模的增大而不斷增加，本文GAA-SQ算法的增長趨勢比其他3個算法小，主要是因為數據規模增大，數據集中近似集的數量和規模也會增大，利用近似集和代表點可以減少大量近似點之間的比較判斷，AA-R*-Tree索引結構可以減少大量近似點間重復的道路網距離計算開銷。Higher-Gsky算法和MG-EGsky算法計算得到結果集之后需要不斷計算尋找最優替代點，時間消耗較大。

圖4展示了不同距離閾值 ε 下各算法的性能分析。隨著 ε 的增大，GAA-SQ和GSSK-A算法的CPU運行時間逐漸減少，其中GSSK-A算法的減少幅度較為緩慢。Higher-Gsky和MG-EGsky算法的CPU運行時間則隨著 ε 的增大而增加，且MG-EGsky算法的增長幅度較為緩慢。這是因為， ε 的增大使得近似集規模擴大，從而減少了大量近似點之間的比較判斷。然而，隨著 ε 的增加，MG-EGsky算法在計算最優替代點時的計算量顯著增加，導致時間消耗逐步上升。相比之下，Higher-Gsky算法從結果集中直接選取最優替代點，由于距離閾值 ε 的增加對候選集規模的影響較小，因此其時間消耗呈現出緩慢增長的趨勢。

圖5展示了4種不同算法在不同道路網路段數的條件下CPU運行時間的變化。從圖中可見，隨著道路網數量的不斷增加，4個算法的CPU運行時間都有不同程度的增加。其中，GAA-SQ算法通過近似集和AA-R*-Tree索引結構可以減少大量近似集中興趣點的道路網距離計算，使得在道路網路段數不斷增加時，CPU運行時間可以緩慢增加。GSSK-A算法引入了近似集的概念，也可以一定程度上減慢CPU運行時間的增加幅度，Higher-Gsky算法和MG-EGsky算法隨著道路網路段數的增加，計算結果集與結果集最優替代點的開銷會不斷加大。

如圖6所示，分析算法用于推薦系統的準確率與距離閾值 ε 之間的關系，可以更好地說明算法的有效性。GSSK-A算法引入近似集的概念，其結果與本文算法類似，因此在此不作進一步討論。從圖6可以發現，本文所提GAA-SQ算法在推薦準確率上相較于Higher-Gsky算法和MG-EGsky算法具有顯著優勢，當距離閾值 ε ∈［10，20］時推薦效果較好，這表明距離閾值 ε 并非越大越好，也說明近似集的范圍并非越大越好。隨著近似集范圍的擴大，距離維度的影響變得難以忽略，從而導致算法準確率下降。

4 結束語

在路網興趣點查詢中引入多目標決策技術可以更全面地優化系統表現、提升個性化和用戶體驗。隨著地圖導航和位置服務的發展，路網近似Skyline查詢具有更重要的價值。已有的Skyline查詢無法直接處理道路網環境下的近似Skyline查詢問題，針對已有的不足，本文提出了道路網廣義近似Skyline查詢算法。所提算法根據路網興趣點集的特征構建近似集，整合數據集并提高查詢效率，提高Skyline查詢的可用性。本文的研究成果增強了興趣點查詢和基于位置服務的技術基礎，能有效支持路網下基于位置的興趣點查詢推薦。

今后的研究重點主要集中在近似集規模約減控制上，使得道路網環境下的近似Skyline查詢輸出結果動態可控。

參考文獻：

［1］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.

［2］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.

［3］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.

［4］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.

［5］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.

［6］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.

［7］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.

［8］郝晉瑤， 牛保寧， 康家興. 大規模路網圖下關鍵詞覆蓋最優路徑查詢優化 ［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.

［9］朱睿， 宋栿堯， 王斌， 等. 高速流環境下近似連續 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.

［10］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.

［11］BAI Mei， HAN Yuxue， YIN Peng， et al. S_IDS： an efficient skyline query algorithm over incomplete data streams ［J］. Data amp; Knowledge Engineering， 2024， 149： 102258.

［12］李松， 王冠群， 郝曉紅， 等. 面向推薦系統的多目標決策優化算法 ［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.

［13］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.

［14］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.

［15］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.

［16］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.

［17］白梅， 王習特， 李冠宇， 等. 基于最大覆蓋的代表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.

［18］李松， 竇雅男， 郝曉紅， 等. 道路網環境下 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.

［19］李松， 賓婷亮， 郝曉紅， 等. 道路網多用戶偏好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.

［20］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.

［21］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.

［22］VLACHOU A， DOULKERIDIS C， ROCHA-JUNIOR J B， et al. Decisive skyline queries for truly balancing multiple criteria ［J］. Data amp; Knowledge Engineering， 2023， 147： 102206.

［23］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.

［24］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.

［25］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.

［26］SALTOS R， WEBER R. Generalized black hole clustering algorithm ［J］. Pattern Recognition Letters， 2023， 176： 196-201.

［27］HUANG Xiaogang， MA Tiefeng， LIU C， et al. GriT-DBSCAN： a spatial clustering algorithm for very large databases ［J］. Pattern Recognition， 2023， 142： 109658.

（編輯 劉楊 陶晴）