[發明專利]基于帶序興趣區域的軌跡查詢的啟發式擴張搜索擴展算法

在審

• 申請號: 201710659340.9
• 申請日: 2017-08-04
• 公開（公告）號: CN107480231A
• 公開（公告）日: 2017-12-15
• 發明（設計）人: 毛睿;李榮華;陸敏華;王毅;羅秋明;商爍;劉剛
• 申請（專利權）人: 深圳大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海宏京知識產權代理事務所(普通合伙)31297
• 代理人: 王函

技術領域

本發明屬于計算機空間數據領域基于位置的服務，尤其涉及一種基于帶序興趣區域的軌跡查詢的啟發式擴張搜索擴展算法。

背景技術

一般將現有的軌跡搜索查詢分為三類。在點對點軌跡查詢類別中，查詢參數是單個空間點，并且查詢尋找空間上靠近查詢點的軌跡。鄭等人[K.Zheng,B.Zheng,J.Xu,G.Liu,A.Liu,and Z.Li.Popularityaware spatial keyword search on activity trajectories.World Wide Web,19(6):1–25,online first,2016.]將此查詢擴展到覆蓋空間和文本域，并提出TkSK查詢來檢索在空間上靠近查詢點的軌跡，以滿足查詢定義的語義要求。在點到軌跡查詢類別中，查詢需要一組地點(如觀光場所)作為參數，返回一條連接或根據某種標準接近查詢位置的軌跡?；谖恢玫能壽E搜索的概念(TSL)首先由Chen等提出[Z.Chen,H.T.Shen,X.Zhou,Y.Zheng,and X.Xie.Searching trajectories by locations:an efficiency study.In SIGMOD,pages 255–266,2010.]。這個研究僅考慮空間域(歐幾里德空間)。尚等[S.Shang,R.Ding,B.Yuan,K.Xie,K.Zheng,and P.Kalnis.User oriented trajectory search for trip recommendation.In EDBT,pages156–167,2012.]觀察到由于用戶的特定偏好，空間相似性沒有充分捕捉查詢位置與軌跡之間的關系。然后他們提出以用戶為導向的軌跡搜索并擴展查詢覆蓋空間和文本域。直觀地，如果軌跡接近指定的查詢位置(空間域)，其文本屬性值與用戶的文字偏好(文字域)類似，將會被推薦給用戶。在軌跡到軌跡類別中，查詢檢索與查詢軌跡最相似的軌跡。例如，PTM查詢[S.Shang,R.Ding,K.Zheng,C.S.Jensen,P.Kalnis,and X.Zhou.Personalized trajectory matching in spatial networks.VLDB J.,23(3):449–468,2014.]考慮時空相似性，ATSQ查詢[K.Zheng,S.Shang,N.J.Yuan,and Y.Yang.Towards efficient search for activity trajectories.In ICDE,pages 230–241,2013.]考慮空間-文本相似性。

在大多數現有的研究軌跡搜索中，查詢參數是一組或一系列的位置。然而，在某些情況下，一個地方可能不是一個點的位置，但可能是包含幾個空間對象的感興趣區域。此外，特別是當規劃一個在陌生城市的旅行時，用戶可能無法準確指定預期地點，而使用預期區域代替。這兩個常見的案例正是現有軌跡搜索方法存在的問題或缺陷。

與現有研究不同，本發明研究按地區進行軌跡搜索的興趣(TSR)查詢，它旨在找到一個與查詢區域的空間密度相關性最高的軌跡。現有的TSL解決方案對TSR查詢無效，有兩個原因。首先，TSL只考慮空間，而TSR考慮到空間距離和空間物體密度。二是TSL只在歐氏空間中進行，空間索引(例如，R-tree[A.Guttman.R-trees:a dynamic index structure for spatial searching.In SIGMOD,pages 47–57,1984.])用于提高查詢效率。但在我們的工作中，運動被限制到空間網絡。當網絡中的邊的權重是對旅行的許多方面(例如，燃料消耗和旅行時間)建模，網絡的下限距離可能不是相應的歐幾里德距離；因此，諸如R-tree等空間指標是無效的。這是我們使用網絡擴展的主要原因(即，Dijkstra的擴展)。