道路網(wǎng)中針對多目標(biāo)決策的興趣點(diǎn)高效查詢算法

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

關(guān)鍵詞：道路網(wǎng)；Skyline查詢；多目標(biāo)決策；近似查詢；興趣點(diǎn)推薦

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：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

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

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

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

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

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

傳統(tǒng)的近似Skyline查詢通常直接對Skyline結(jié)果集或?qū)?shù)據(jù)集進(jìn)行近似處理，不能將擴(kuò)展的興趣點(diǎn)進(jìn)行整合，并且沒有從興趣點(diǎn)出發(fā)考慮興趣點(diǎn)之間的近似關(guān)系。此外，傳統(tǒng)控制Skyline結(jié)果集規(guī)模的查詢算法未考慮到在道路網(wǎng)環(huán)境下的距離維度，也未考慮到興趣點(diǎn)在道路網(wǎng)絡(luò)環(huán)境中的空間分布。因此，本文基于興趣點(diǎn)的空間分布以及興趣點(diǎn)之間的近似關(guān)系提出一種道路網(wǎng)廣義近似Skyline查詢算法。

1 基本定義

道路網(wǎng)廣義近似Skyline查詢是路網(wǎng)Skyline查詢的變體問題，

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

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

定義2 道路網(wǎng)支配 給定道路網(wǎng)環(huán)境下查詢點(diǎn)q以及興趣點(diǎn)p1和p2，用d（q， p1）表示q與p1之間的路網(wǎng)距離，若滿足2個(gè)條件其中1個(gè)時(shí)：

（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道路網(wǎng)支配p1，記作p2p1。

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

定義4 興趣點(diǎn)道路網(wǎng)近似 給定道路網(wǎng)環(huán)境下興趣點(diǎn)p1和p2，d（p1， p2）為p1和p2之間的路網(wǎng)距離，當(dāng)且僅當(dāng)滿足下面兩個(gè)條件時(shí)，稱p1和p2道路網(wǎng)近似，記作p1p2：

（1）興趣點(diǎn)p1和p2非空間相似，即p1p2；

（2）d（p1，p2）≤ε，興趣點(diǎn)p1和p2在道路網(wǎng)環(huán)中的路網(wǎng)距離小于等于距離閾值ε。

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

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

定義7 近似數(shù)據(jù)打分函數(shù)記作

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

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

式中：ψi為近似集內(nèi)第i個(gè)興趣點(diǎn)的歷史訪客數(shù)量；r為近似集中興趣點(diǎn)數(shù)量；r為近似集整體歷史訪客數(shù)量；k－1為非空間屬性數(shù)；pi（j）為第i個(gè)興趣點(diǎn)在第j個(gè)屬性上的取值；λj為非空間第j個(gè)屬性維度上的閾值；ζj為第j屬性的屬性優(yōu)劣值，當(dāng)?shù)趈屬性上取值越大優(yōu)勢越大時(shí)，ζj取值為1，反之ζj取值為－1；i為用戶評價(jià)指標(biāo)，近似集中分?jǐn)?shù)最高的點(diǎn)被稱為近似集的代表點(diǎn)。

定義8 廣義近似聚集支配 給定道路網(wǎng)中兩個(gè)數(shù)據(jù)對象o1和o2（數(shù)據(jù)對象可以是近似集或者獨(dú)立點(diǎn)），若o1廣義近似聚集支配o2，記作o1o2。

（1）給定興趣點(diǎn)1和2是數(shù)據(jù)集O中的兩個(gè)獨(dú)立點(diǎn)，若滿足12，則有12；反之若滿足21，則有21；

（2）給定獨(dú)立點(diǎn)和近似集C是數(shù)據(jù)集O中的兩個(gè)數(shù)據(jù)對象，興趣點(diǎn)pi是近似集C的代表點(diǎn)，若滿足p i ，則有C；反之，若滿足pi，則有C；

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

定義9 道路網(wǎng)廣義近似 Skyline 查詢 給定一個(gè)查詢點(diǎn)q和一個(gè)k維興趣點(diǎn)集P，以及道路網(wǎng)路段集合R。預(yù)先對興趣點(diǎn)集P進(jìn)行道路網(wǎng)近似計(jì)算形成包含近似集和獨(dú)立點(diǎn)的數(shù)據(jù)集O。道路網(wǎng)廣義近似 Skyline 查詢結(jié)果返回?cái)?shù)據(jù)集O的子集，其中所有獨(dú)立點(diǎn)或近似集不被數(shù)據(jù)集O中其他獨(dú)立點(diǎn)或近似集廣義近似聚集支配。這些獨(dú)立點(diǎn)或者近似集被稱為道路網(wǎng)廣義近似Skyline對象，記為GAA-SQ（q，O，R）， 道路網(wǎng)廣義近似Skyline查詢簡稱為GAA-SQ查詢。

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

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

2 道路網(wǎng)廣義近似Skyline查詢

本文主要分為2個(gè)主要過程：興趣點(diǎn)道路網(wǎng)近似計(jì)算預(yù)處理過程和道路網(wǎng)廣義近似Skyline查詢過程。首先對興趣點(diǎn)集 P 進(jìn)行道路網(wǎng)近似計(jì)算形成包含近似集和獨(dú)立點(diǎn)的數(shù)據(jù)集 O ，然后對數(shù)據(jù)集 O 進(jìn)行廣義近似聚集Skyline查詢。

2.1 道路網(wǎng)近似計(jì)算

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

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

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

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

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

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

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

證明 因?yàn)闈M足d（p， pj）lt;ε（pj∈C），由剪枝規(guī)則1的證明可知，興趣點(diǎn)p和近似集C可以視為在道路網(wǎng)中的同一位置，又因?yàn)榕d趣點(diǎn)p與近似集C構(gòu)成的新集合不為近似集，并且近似集C中存在興趣點(diǎn)pi非空間支配p即pik-1p，所以當(dāng)查詢點(diǎn)變化時(shí)，始終有Cp，所以興趣點(diǎn)p可被剪枝。

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

證明 同剪枝規(guī)則2證明，興趣點(diǎn)p和近似集C可以視為在道路網(wǎng)中的同一位置，又因?yàn)榕d趣點(diǎn)p與近似集C構(gòu)成的新集合不為近似集，并且pk-1pi，pi∈C，所以當(dāng)查詢點(diǎn)變化時(shí)，始終有pC，所以興趣點(diǎn)p可被剪枝。

基于定理1，以及剪枝規(guī)則1～3，本節(jié)進(jìn)一步給出道路網(wǎng)近似計(jì)算算法 O-RNAC ，構(gòu)造可以多樣化查詢結(jié)果的近似集，減少近似點(diǎn)之間的支配判斷，同時(shí)可以約減部分興趣點(diǎn)，如算法1所示。

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

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

輸出：道路網(wǎng)近似計(jì)算包含近似集C和獨(dú)立點(diǎn)的數(shù)據(jù)集O。

1. O←；

2. "for "興趣點(diǎn)集P未被訪問的興趣點(diǎn)p "do

3. "創(chuàng)建近似集C， 近似集C←p；

4. "候選集N←興趣點(diǎn)p的ε鄰域內(nèi)未被訪問過的興趣點(diǎn)；

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

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

7. ""C←C+ p′；

8. ""N←N+興趣點(diǎn)p′的ε鄰域內(nèi)未被訪問過的興趣點(diǎn)；

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

10. "興趣點(diǎn)p′被剪枝；

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

12. "候選集N←興趣點(diǎn)p′的ε鄰域內(nèi)未被訪問過的興趣點(diǎn)；

13. "近似集C←p′；

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

15. ""min （ max （d（p，pi）））， pi∈C， p≠pi計(jì)算近似集C的位置最佳點(diǎn)；

16. "通過近似數(shù)據(jù)打分函數(shù)對近似集C進(jìn)行排序，確定近似集代表點(diǎn)；

17. "O←O+C；

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

19. "標(biāo)記C中唯一點(diǎn)p為獨(dú)立點(diǎn)；

20. "O←O+；

21. C←；

22. "return "O；

道路網(wǎng)近似計(jì)算 O-RNAC 由算法1實(shí)現(xiàn)。訪問數(shù)據(jù)集中未被訪問過的興趣點(diǎn)，將該興趣點(diǎn)道路網(wǎng)距離閾值ε領(lǐng)域內(nèi)存在的其他未被訪問的興趣點(diǎn)加入候選集N。遍歷候選集N中興趣點(diǎn)，如果該興趣點(diǎn)與當(dāng)前近似集合并后仍為近似集，則將該興趣點(diǎn)加入當(dāng)前近似集，并將該興趣點(diǎn)ε領(lǐng)域內(nèi)存在的其他未被訪問的興趣點(diǎn)加入候選集N；如果該興趣點(diǎn)支配當(dāng)前近似集，并且該興趣點(diǎn)與當(dāng)前近似集構(gòu)成的集合不為近似集，則刪除該近似集，將候選集清空，從該興趣點(diǎn)開始重新創(chuàng)建近似集；如果近似集有且只有一個(gè)興趣點(diǎn)存在，則將該興趣點(diǎn)標(biāo)記為獨(dú)立點(diǎn)，加入結(jié)果集；如果近似集存在多于一個(gè)的興趣點(diǎn)，則將近似集加入結(jié)果集，并且選取近似集位置最佳點(diǎn)以及對近似集內(nèi)部興趣點(diǎn)進(jìn)行打分排序。最后返回包含近似集和獨(dú)立點(diǎn)的數(shù)據(jù)集O。

當(dāng)?shù)缆肪W(wǎng)數(shù)據(jù)集P數(shù)據(jù)點(diǎn)增加時(shí)，對預(yù)處理數(shù)據(jù)集O進(jìn)行更新操作。若此數(shù)據(jù)點(diǎn)p與ε鄰域內(nèi)的獨(dú)立點(diǎn)p′非空間相似，則將數(shù)據(jù)點(diǎn)p和數(shù)據(jù)點(diǎn)p′形成近似集加入數(shù)據(jù)集O；若此數(shù)據(jù)點(diǎn)p與近似集內(nèi)所有點(diǎn)非空間相似，且近似集內(nèi)存在點(diǎn)在數(shù)據(jù)點(diǎn)p的ε鄰域內(nèi)，則將數(shù)據(jù)點(diǎn)p加入該近似集，更新數(shù)據(jù)集O；若數(shù)據(jù)點(diǎn)p的ε鄰域內(nèi)不存在與之非空間相似的數(shù)據(jù)點(diǎn)，則將數(shù)據(jù)點(diǎn)p標(biāo)記為獨(dú)立點(diǎn)加入數(shù)據(jù)集O。更新數(shù)據(jù)集O。

2.2 AA-R*-Tree索引

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

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

2.3 道路網(wǎng)廣義近似Skyline查詢

本節(jié)通過2.1節(jié)計(jì)算得到的數(shù)據(jù)集O進(jìn)行廣義近似聚集支配計(jì)算，將每個(gè)近似集視為一個(gè)數(shù)據(jù)對象進(jìn)行道路網(wǎng)廣義近似Skyline查詢。本節(jié)以定理的形式給出廣義近似聚集支配中獨(dú)立點(diǎn)之間、近似集之間以及獨(dú)立點(diǎn)與近似集之間支配關(guān)系的近似簡化判斷算法，查詢返回滿足廣義近似聚集支配的Skyline結(jié)果集。

定理2 給定興趣點(diǎn)1和2是數(shù)據(jù)集O中的兩個(gè)獨(dú)立點(diǎn)，若滿足12，則有12；反之若滿足21，則有21。

證明 由廣義近似聚集支配定義可知，獨(dú)立點(diǎn)之間的支配判斷符合傳統(tǒng)道路網(wǎng)支配判斷，若滿足獨(dú)立點(diǎn)1道路網(wǎng)支配2，則一定滿足獨(dú)立點(diǎn)1廣義近似聚集支配2，記作12。

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

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

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

證明 同定理3的證明，代表點(diǎn)代表了所在的近似集，當(dāng)兩個(gè)代表點(diǎn)非空間相似時(shí)，代表兩個(gè)近似集非空間相似，距離查詢點(diǎn)越近的近似集占優(yōu)；當(dāng)兩個(gè)代表點(diǎn)不相似時(shí)，由定理3的證明同樣可以得出，若p1p2，則CC′，反之亦然。

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

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

輸入：查詢點(diǎn)q、包含近似集C和獨(dú)立點(diǎn)的數(shù)據(jù)集O、道路網(wǎng)路段集合R；

輸出：道路網(wǎng)廣義近似 Skyline 查詢的結(jié)果集S。

1. 以O(shè)中的獨(dú)立點(diǎn)、近似集、道路網(wǎng)路段創(chuàng)建 AA-R*-Tree 索引結(jié)構(gòu)；

2. S←；

3. 遍歷數(shù)據(jù)集O中的數(shù)據(jù)對象oi進(jìn)行廣義近似聚集 Skyline 支配判斷；

4. "if "oi∈O，oj∈O且oi與oj均為獨(dú)立點(diǎn) then

5. "獨(dú)立點(diǎn)間進(jìn)行道路網(wǎng)支配判斷；

6. "if "∈O，C∈O并且為獨(dú)立點(diǎn)，C為近似集 then

7. ""if 近似集C的代表點(diǎn)p與非空間相似 then

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

9. ""else

10. "代表點(diǎn)p與進(jìn)行道路網(wǎng)支配判斷；

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

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

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

14. ""else

15. "代表點(diǎn)p1與p2進(jìn)行道路網(wǎng)支配判斷；

16. 更新結(jié)果集S；

17. "return "S；

道路網(wǎng)廣義近似 Skyline 查詢通過算法2實(shí)現(xiàn)，算法2通過2.1節(jié)計(jì)算得到的數(shù)據(jù)集O進(jìn)行道路網(wǎng)廣義近似 Skyline 查詢。分別進(jìn)行獨(dú)立點(diǎn)之間、近似集之間以及獨(dú)立點(diǎn)與近似集之間支配關(guān)系的廣義近似支配簡化判斷算法，得到結(jié)果集S，結(jié)果集S中的數(shù)據(jù)對象均不被S中其他的數(shù)據(jù)對象廣義近似聚集支配，最終，結(jié)果集S就是道路網(wǎng)廣義近似 Skyline 查詢的結(jié)果集。

3 實(shí)驗(yàn)比較與分析

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

3.1 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境設(shè)置

本文實(shí)驗(yàn)采用真實(shí)道路網(wǎng)數(shù)據(jù)集，從加利福尼亞道路網(wǎng)數(shù)據(jù)集以及加利福尼亞的數(shù)據(jù)點(diǎn)（http：//www.cs.utah.edu/～lifeifei/SpatialDataset.htm）中一片區(qū)域抽取10000個(gè)節(jié)點(diǎn)對象和5000個(gè)線段對象（線段作為道路網(wǎng)線段）。查詢用戶采用隨機(jī)生成的方式。本文使用道路網(wǎng)近似計(jì)算處理數(shù)據(jù)集中近似興趣點(diǎn)，并使用AA-R*-Tree索引結(jié)構(gòu)組織處理后的數(shù)據(jù)集。

實(shí)驗(yàn)環(huán)境：8GB內(nèi)存、Core（TM） i7-12700H CPU@2.70GHz處理器、500GB硬盤，Windows11操作系統(tǒng)上用IntelliJ IDEA 2021.3.2開發(fā)平臺Java語言實(shí)現(xiàn)。實(shí)驗(yàn)需要驗(yàn)證4個(gè)算法的查詢性能，數(shù)據(jù)集最大維度為4。每個(gè)實(shí)驗(yàn)采取單一變量原則，其余變量為默認(rèn)值，實(shí)驗(yàn)結(jié)果取50次實(shí)驗(yàn)運(yùn)行的平均值。

3.2 算法對比

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

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

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

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

4 結(jié)束語

在路網(wǎng)興趣點(diǎn)查詢中引入多目標(biāo)決策技術(shù)可以更全面地優(yōu)化系統(tǒng)表現(xiàn)、提升個(gè)性化和用戶體驗(yàn)。隨著地圖導(dǎo)航和位置服務(wù)的發(fā)展，路網(wǎng)近似Skyline查詢具有更重要的價(jià)值。已有的Skyline查詢無法直接處理道路網(wǎng)環(huán)境下的近似Skyline查詢問題，針對已有的不足，本文提出了道路網(wǎng)廣義近似Skyline查詢算法。所提算法根據(jù)路網(wǎng)興趣點(diǎn)集的特征構(gòu)建近似集，整合數(shù)據(jù)集并提高查詢效率，提高Skyline查詢的可用性。本文的研究成果增強(qiáng)了興趣點(diǎn)查詢和基于位置服務(wù)的技術(shù)基礎(chǔ)，能有效支持路網(wǎng)下基于位置的興趣點(diǎn)查詢推薦。

今后的研究重點(diǎn)主要集中在近似集規(guī)模約減控制上，使得道路網(wǎng)環(huán)境下的近似Skyline查詢輸出結(jié)果動態(tài)可控。

參考文獻(xiàn)：

［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］郝晉瑤， 牛保寧， 康家興. 大規(guī)模路網(wǎng)圖下關(guān)鍵詞覆蓋最優(yōu)路徑查詢優(yōu)化 ［J］. 軟件學(xué)報(bào)， 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］朱睿， 宋栿堯， 王斌， 等. 高速流環(huán)境下近似連續(xù) k 代表輪廓查詢算法 ［J］. 軟件學(xué)報(bào)， 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］李松， 王冠群， 郝曉紅， 等. 面向推薦系統(tǒng)的多目標(biāo)決策優(yōu)化算法 ［J］. 西安交通大學(xué)學(xué)報(bào)， 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］白梅， 王習(xí)特， 李冠宇， 等. 基于最大覆蓋的代表Skyline問題的優(yōu)化算法研究 ［J］. 計(jì)算機(jī)學(xué)報(bào)， 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］李松， 竇雅男， 郝曉紅， 等. 道路網(wǎng)環(huán)境下 K -支配空間Skyline查詢方法 ［J］. 計(jì)算機(jī)研究與發(fā)展， 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］李松， 賓婷亮， 郝曉紅， 等. 道路網(wǎng)多用戶偏好Top- k 天際線查詢方法 ［J］. 計(jì)算機(jī)研究與發(fā)展， 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.

（編輯 劉楊 陶晴）