協同空間關鍵詞Top-k查詢

郭 帥，劉 亮，秦小麟

(南京航空航天大學 計算機科學與技術學院，南京 210016)

1 引 言

隨著定位技術的廣泛應用，文本數據融入了地理標簽.例如，照片共享社交網站(如Flickr)包含具有地理位置和文本描述標簽的照片；基于簽到或評論的社交網絡(如Foursquare)積累了大量具有文本描述和空間位置信息的興趣點.空間關鍵詞查詢處理技術[1-4]用于高效的過濾和篩選這些空間文本對象數據，找出與查詢空間距離、文本相關度兩個維度均相似的結果.近年來，空間關鍵詞查詢受到了研究人員的廣泛關注.

現有空間關鍵詞查詢處理技術主要針對單用戶，即以一個查詢位置和一組查詢關鍵詞作為參數輸入，返回數據集中距離查詢位置近、文本與查詢關鍵詞相關度高的對象.但在現實生活中，存在大量多個用戶協同查詢一個空間文本對象的需求和應用場景.例如，在不同公司工作的用戶聚餐，每個用戶都會以自己的公司位置發出一個位置查詢，查詢離自己公司近的餐館，且每個用戶通常會給出查詢關鍵詞查詢特定類型的餐館.此類查詢被定義為協同空間關鍵詞Top-k查詢.相對于傳統的空間關鍵詞查詢，協同空間關鍵詞Top-k查詢提出了新的挑戰：

1)多個用戶提出的查詢關鍵詞中存在相同關鍵詞或者近義關鍵詞.傳統空間關鍵詞查詢由一個用戶提出，不存在關鍵詞重復或近義的現象，其關鍵詞相關度計算公式沒有考慮查詢關鍵詞權重的問題.

2)查詢關鍵詞與對象關鍵詞存在語義相近的情況.例如，兩個用戶給出的查詢關鍵詞中分別有“露天”和“戶外”，兩者意思皆為查詢戶外餐館，如果僅僅將不同用戶的查詢關鍵詞聯合作為總的查詢關鍵詞，針對一個含“露天”關鍵詞的對象，利用傳統空間關鍵詞查詢算法查詢時，只能匹配一個查詢關鍵詞.識別查詢關鍵詞和對象關鍵詞中的近義關鍵詞并且準確匹配是一大挑戰.

3)如何高效的在數據集中快速找出滿足協同空間關鍵詞Top-k查詢的對象？傳統的空間關鍵詞查詢只給出一個查詢位置，但協同空間關鍵詞查詢會給出多個位置.快速找出距離多個查詢點位置近，并且文本跟查詢關鍵詞相關度高的Top-k對象是協同空間關鍵詞查詢的另一大挑戰.

針對上述協同空間關鍵詞Top-k查詢以及帶來的挑戰，本文提出了一種高效的協同空間關鍵詞Top-k查詢處理技術，主要貢獻如下：

1)考慮不同用戶提出相同關鍵詞或者近義關鍵詞的問題，設計基于查詢關鍵詞權重的相關度計算公式.

2)針對協同空間關鍵詞Top-k查詢，以及查詢中的關鍵詞近義問題，提出了支持協同空間關鍵詞查詢高效剪枝的索引SKNIR-tree(Synonymous Keywords Normalization IR-tree).

3)基于SKNIR-tree索引，提出一種高效的協同空間關鍵詞Top-k查詢處理算法TKCSK.通過維護一個優先隊列以及計算每個節點與查詢的最小空間文本相關度來達到剪枝目的，快速識別結果對象.

為了評估SKNIR-tree索引和TKCSK算法的性能，從查詢時間和IO兩個方面進行了大量的實驗，實驗結果表明，TKCSK算法較參照算法的性能平均提高3倍.

2 相關工作

現有空間關鍵詞查詢大多針對單用戶[5-8]，不涉及協同問題.其主要是對地理文本數據建立混合索引[9-11]，并設計相應算法達到快速查詢的目的.R*-IF索引[9]用R樹索引位置信息，每個R樹的葉子節點關聯一個倒排文件來索引文本信息，查詢時根據R樹找到近鄰的葉子節點，再在每個葉子節點下，根據文本相關度對對象進行排序.IR-tree[2]則是給R樹的每個節點關聯一個倒排文件，利用優先隊列查詢出文本相關度和距離接近度最大的k個對象.bR-tree[10]將R樹的每個節點關聯位圖來索引文本信息，查詢時根據位圖中是否包含所有查詢關鍵詞對R樹節點進行剪枝，最后根據距離接近度對對象進行排序.文獻[11]建立PMR-quad樹和3個內存表的數據結構來處理路網中空間關鍵詞連續k近鄰查詢.上面的研究都是由一個用戶提出的查詢，與此相反地，我們的目標是解決多個用戶提出的空間關鍵詞查詢，查詢出來的對象滿足多個用戶的需求.

現有空間關鍵詞查詢方面已有一些協同研究，ALI[12]等人研究了k-BEST-SUBGROUPS-NN查詢，查詢由多個用戶指定，目的在于找出滿足任意子用戶組的需求，文獻提出了一種以數據為中心的方法，逐步訪問數據對象，并在每次訪問中識別最佳子組.其關鍵思想是通過從查詢點的質心以徑向方向前進形成關于現有數據對象的最佳子組，從而無需枚舉所有可能的子組.但此文僅考慮了空間方面的協同，不涉及關鍵詞的研究.Zhang[13]等人研究了TkCoS查詢，其綜合考慮了空間和關鍵詞的協同查詢，設計了STR-tree索引結構，通過計算每個節點集的上邊界和下邊界排序分來達到剪枝的目的.TkCoS查詢由多個用戶提出，查詢Top-k對象集來滿足用戶的需求.但其研究的查詢所得結果為Top-k對象集.面向集合的空間關鍵詞查詢[14-16]由一個用戶提出，旨在找出Top-k對象集，每一個對象集的關鍵詞包含查詢關鍵詞，對象集的位置距離查詢位置近.我們的TKCSKQ不同于上述研究，查詢由多個用戶提出，并考慮了多個用戶提出的查詢關鍵詞間存在的近義問題，以及查詢關鍵詞與對象關鍵詞的近義問題，匹配最優Top-k對象.

3 協同空間關鍵詞Top-k查詢

3.1 問題描述

地理文本對象.o=<ρ,φ>，其中，ρ代表對象位置經緯度，φ代表對象關鍵詞集合.

協同空間關鍵詞Top-k查詢.Q={，…，}，其中，qi,ρ代表第i個用戶提出的查詢位置，qi.φ代表第i個用戶提出的查詢關鍵詞.TKCSKQ目的在于找出Top-k地理文本對象，這k個對象的位置距所有用戶的位置近，并且其關鍵詞與查詢關鍵詞有高的相關度.

為了從地理文本對象數據集中查找出最好的Top-k對象，我們提出了排序函數來測量一個對象對TKCSKQ的滿足程度，如公式1所示.函數綜合考慮了距離接近度和關鍵詞相關度，公式1中，α∈[0,1]表示用戶對空間和文本的偏好程度，D(Q,o)代表了對象位置與多個查詢用戶位置的距離接近度，通過o的位置與qi位置距離最大值的最小值計算所得(公式2所示)，maxD代表數據集中兩個對象的最遠距離.TRel(Q.φ,o.φ)代表關鍵詞相關度，在傳統空間關鍵詞.

(1)

(2)

(ti∈Q.φ＾ti∈o.φ)

(3)

查詢中，查詢關鍵詞由一個用戶提出，不存在重復的關鍵詞，不用考慮單個查詢關鍵詞的權重問題，但對于TKCSKQ，多個用戶可能提出相同的關鍵詞或近義關鍵詞，查詢中的關鍵詞有了不同的權重，因而我們提出了基于權重的關鍵詞相關度計算公式(公式(3)所示)，ti表示既出現在查詢關鍵詞，又出現在對象關鍵詞的關鍵詞，wi表示ti在查詢關鍵詞中出現的次數，num(Q.φ)表示總的查詢關鍵詞的個數.通過公式1計算出的值越小，表明對象更滿足查詢條件.

在定義1中形式化的描述了由TKCSKQ得出的結果所滿足的條件.

定義1. (滿足TKCSKQ的結果)給定一個空間文本對象數據集以及一個TKCSKQ，針對查詢所得結果{o1,o2，…，ok}，在數據集中不存在ο′，ο′?{o1，o2,…,ok}且Ssk(Q,o′)

3.2 SKNIR-tree索引

圖1是8個空間文本對象實例.左邊展示了對象的地理位置，右邊展示了對象的關鍵詞信息.其中，關鍵詞t2與t5語義同義.

為了處理TKCSKQ，本文對IR-tree做了擴展，提出了混合索引SKNIR-tree，如圖2所示.

SKNIR-tree通過維護一張關系表(圖2左下所示)，將對象以及查詢中的關鍵詞規范化，并用整數數字標識.由于TKCSKQ處理的場景(例如不同公司用戶定餐館或合租等)所涉及到的關鍵詞都是諸如快餐、露天餐館等標簽式關鍵詞，這類標簽式關鍵詞具有規范化后數字標識數量固定的特點.

圖1 空間文本對象Fig.1 Spatial textual objects

因而規范化后的數字標識可提前確定，更容易對關系表動態添加，只需要將不規范的關鍵詞對應到具體的數字標識即可.為了加快關鍵詞在關系表中的查詢速度，使用字典樹(圖2左上所示)來索引關鍵詞.字典樹利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較.在字典樹中，除了根節點不存儲數據外，每個節點存儲一個英文字母，從根節點到葉子節點的一條路徑組成了一個關鍵詞.葉子節點的存儲結構為(key，p)，其中，key表示關鍵詞，p表示指向關系表中相應關鍵詞的指針.查詢時，從字典樹根節點出發，在根節點子節點中通過哈希來查詢關鍵詞第一個字母所在的節點位置，然后在此節點的子節點中尋找下一個字母，直到尋找到最后一個字母.字典樹采用哈希來存儲和查詢節點所在位置，查詢效率高.例如，如圖中所示，對于ba這個關鍵詞，在第一層中通過哈希迅速定位到b所在節點，并在其葉子節點下通過哈希迅速定位到a所在節點，從而快速得到ba關鍵詞在關系表中的位置.

圖2 SKNIR-treeFig.2 SKNIR-tree

SKNIR-tree對傳統IR-tree部分做了適當的改造(圖2右所示)以適應TKCSKQ，在倒排文件中，NKI(Normalized Keyword Identification)替換了原先的對象關鍵詞.每一個葉子結點以(op,o.r,IFp)表示，其中op為指向對象o的指針，o.r為對象o的邊界矩形，IFp為指向倒排文件的指針.倒排文件包含兩個主要成分：第一，對象關鍵詞轉換后的所有NKI；第二，每一個NKI對應一個倒排列表，列表中存放所有關鍵詞轉換后含有此NKI的對象標識.每一個非葉子節點以(nps,r,IFp)表示，其中nps為指向子節點的指針，r為最小邊界矩形，IFp為指向倒排文件的指針.

圖2給出了圖1中對象被SKNIR-tree索引的例子.在關系表中，對象關鍵詞都被規范化為數字標識，由于t2與t5近義，所以都被規范化為3.并根據對象的位置建立了R樹，且為每個節點構建NKI倒排文件.

下面闡述SKNIR-tree的構建過程.索引建立過程如算法1所示.首先構建關系表，由于標簽式關鍵詞規范化后數字標識數量固定的特點，預先制定相應的規范化標識，然后將數據集中出現的關鍵詞對應相應的標識(1-5行).將規范化過程中的(關鍵詞，規范化關鍵詞標識)插入到關系表中(7行)，并將關鍵詞及其在關系表中的位置插入到字典樹中(8行).最后調用IR-tree[2]中的接口Insert將對象插入，值得注意的是，SKNIR-tree插入參數是對象的最小邊界矩形以及對象關鍵詞規范化后的標識集(10行).

算法1. 索引建立 IndexBuilding

輸入：所有對象

1. for each o

2. for each keyword t in o

3. identifying t with NKI

4. end for

5. end for

6. for each nonredundant t

7. insert (t，NKI) to relational table

8. insert t to trie

9. end for

10. Insert(MBR，NKIs)

3.3 協同空間關鍵詞Top-k查詢算法

在本小節中，首先提出了Baseline算法.然后在上述SKNIR-tree索引的基礎上，提出了高效處理TKCSKQ的算法.

傳統的空間關鍵詞查詢由單用戶提出，返回距離一個位置近、文本與一組查詢關鍵詞相關度高的對象.TKCSKQ由多個用戶提出，包含多個查詢位置和多組查詢關鍵詞，并且查詢關鍵詞中存在重復和近義現象，返回距離多個位置近、文本與多組查詢關鍵詞相關度高的對象.最直觀的方法是用已有處理單用戶空間關鍵詞Top-k查詢的技術[2]分別處理每個用戶提出的查詢，最后再將各個查詢得到的結果融合，通過上述公式計算空間文本相關度得到Top-k結果.但這將導致巨大的處理代價：第一，每個用戶的查詢都將訪問一次索引，這將增加處理代價；第二，每個查詢需要維護遠大于k的結果，以保證結果融合后包含Top-k.本文將上述算法作為Baseline算法.

(4)

下面我們提出了高效的TKCSK算法.查詢過程中，維護一個查詢Q與SKNIR-tree節點最小空間文本相關度的優先隊列，其最小文本相關度計算函數如公式(4)所示.公式表示查詢Q與此節點的最小邊界矩形包含的對象的最小空間文本相關度，在此節點的最小邊界矩形包含下的對象與查詢Q的空間文本相關度皆大于此空間文本相關度，定理1給出定論并證明.優先隊列按照空間文本相關度從小到大排列，迭代從隊首取出節點，并計算其子節點的minSsk(Q,N)，并放入優先隊列中，若取出的節點為對象，那么此對象即為Top-k結果集中的一個，直到Top-k對象都求出，優先隊列中的其它節點和對象則不需要訪問和計算，達到快速剪枝的目的，提高查詢效率.

定理1. 給定一個查詢Q和SKNIR-tree的一個節點N，并且節點N的最小邊界矩形包含了對象集os，那么?o∈os(minSsk(Q，N)≤Ssk(Q，o))

算法2.協同空間關鍵詞查詢TKCSK

輸入：協同空間關鍵詞范圍查詢Q={,…,

輸出：滿足查詢條件的Top-k對象

1. Result←?

2. for eachqi. φ

3. for each keyword t

4. Q.NKIs.add(t->NKI)

5. end for

6. end for

7. sort(Q.NKIs)

8. Q.NKI.w←count(Q.NKI)

9. U←EmptyPriorityQueue

10. U.push(root，0)

11. while U is not empty and Result.length

12. E←U.pop()

13. if E is an object

14. result.add(E)

15. else if E is a leaf node

16. for each object o in leaf node

17. U.push(o，Ssk(Q，o))

18. end for

19. else

20. for each node n in E

21. U.push(n，minSsk(Q,N))

22. end for

23. end if

24. end while

下面具體闡述算法過程，如算法2所示.

首先將多個用戶提出的查詢關鍵詞轉化為NKI，并將NKIs排序(2-7行).計算每個NKI出現的次數作為NKI的權重(8行).然后維護一個優先隊列U，優先隊列根據Ssk由小到大排列，并將SKNIR-tree的根節點存入U中(9-10行).在U不為空并且結果集Result對象數量小于k(11行)，執行以下算法：獲取U的第一個元素E，若E是一個對象，將此對象加入到Result中；若E是一個葉子結點，計算葉子結點包含對象的Ssk(Q，o)并放入U中；若E是一個非葉子結點，計算節點下包含的子節點的minSsk(Q,N)并放入U中(12-23行).最后Result中的結果就是求得的Top-k結果.

4 實驗結果與分析

4.1 實驗環境設置

實驗在ThinkPad T450上進行，配置如下：CPU：Inter(R)

Core(TM)i5-5200UCPU @2.20GHZ，內存：6G，硬盤：500G，操作系統：Windows 10.實驗所有算法均采用Java實現，集成開發環境為IntelliJ IDEA Community Edition 14.0.2.

實驗數據使用yelp網站提供的yelp_academic_dataset_business數據集*http:www.yelp.ca/dataset_challenge/dataset.該數據集收集了yelp網站上4個國家11個城市的85，901個餐館信息.數據集內每一行記錄了一個餐館信息，餐館信息包括商戶標識、地址、經緯度、分類等31項信息.實驗使用經緯度作為位置信息，分類作為關鍵詞信息.實驗還根據原有數據集通過隨機采樣生成的方法對原有數據集進行了擴充.由于數據集中關鍵詞不存在近義關鍵詞，實驗過程中隨機選取多組2-4個關鍵詞作為近義關鍵詞.現有空間關鍵詞查詢的研究不能處理協同空間關鍵詞Top-k查詢，實驗對3.3節提出的Baseline算法與TKCSK算法進行比較.

4.2 實驗結果

實驗在查詢效率和IO代價兩個方面對Baseline算法和TKCSK算法進行了比較，IO代價通過訪問的對象數進行衡量.在下述中，n表示用戶數量，k為結果數量，為用戶對空間和關鍵詞的偏好程度.

4.2.1 用戶數量變化下的查詢性能比較

圖3展示了當固定k為10、每個用戶提出的查詢關鍵詞數量為3、為0.5時，不同用戶數量對查詢時間和IO代價的影響.由于Baseline算法中每個子查詢都將訪問一次索引，而且每個子查詢需要維護遠大于k的結果，以保證結果融合后包含Top-k，所以Baseline算法的查詢時間和IO代價都大于TKCSK算法.隨著n的增大，Baseline算法需要多執行一次查詢，所以如圖中所示，查詢時間和IO代價也隨之增大.而n的增大并不會影響TKCSK算法的剪枝率，所以如圖所示，隨著n的增大TKCSK算法的查詢時間和IO代價基本不變.

圖3 用戶數量的影響Fig.3 Effect of n

圖4 k的影響Fig.4 Effect of k

4.2.2 結果數量變化下的查詢性能比較

圖4展示了當固定n為3、每個用戶提出的查詢關鍵詞數量為3、α為0.5時，不同結果數量對查詢時間和IO代價的影響.明確地，在不同k值下，TKCSK算法相對于Baseline算法，查詢時間短，IO代價小.隨著k的增大，由于需要的結果數增多，剪枝量會相應減少，所以如圖中所示，查詢時間和IO代價隨著k值的增大而增大.并且由于Baseline算法要維護比k更大的值(實驗設置為2倍)，其增長幅度要大于TKCSK算法的增長幅度.

4.2.3 查詢關鍵詞數量變化下的查詢性能比較

圖5展示了當固定k為10、n為3、為0.5時，不同查詢關鍵詞數量對查詢時間和IO代價的影響.明確地，在不同查詢關鍵詞數量下，TKCSK算法相對于Baseline算法，查詢時間短，IO代價小.從圖中看出，查詢時間和IO代價隨著查詢關鍵詞數量的增加基本保持不變，因為查詢關鍵詞數量的變化不會影響TKCSK算法的剪枝率.

圖5 查詢關鍵詞數量的影響Fig.5 Effect of keywords

4.2.4 用戶對空間和關鍵詞的偏好程度變化下的查詢性能比較

圖6展示了當固定k為10、n為3、每個用戶提出的查詢關鍵詞數量為3時，不同偏好對查詢時間和IO代價的影響.

明確地，在不同下，TKCSK算法相對于Baseline算法，查詢時間短，IO代價小.正如第3節提到的，用來調整用戶對空間和文本的偏好程度，值越大代表用戶越看重于查詢結果的位置，值越小代表用戶越看重于查詢結果的文本.從圖中看出，查詢時間和IO代價隨著值的增大而增大，這是因為空間接近度區分度小，利用空間接近度剪枝率小.

5 結束語

傳統空間關鍵詞查詢主要由單用戶提出，返回距離一個位置近、文本與一組查詢關鍵詞相關度高的對象.協同空間關鍵詞Top-k查詢旨在滿足多個用戶的協同查詢需求，包含多個查詢位置和多組查詢關鍵詞，返回距離多個位置近、文本與多組查詢關鍵詞相關度高的對象.本文針對多組查詢關鍵詞中的重復和近義關鍵詞現象，設計基于查詢關鍵詞權重的文本相關度計算公式.為了快速處理協同空間關鍵詞查詢，擴展了IR-tree，提出SKNIR-tree索引.在此基礎上，提出了一種高效的協同空間關鍵詞Top-k查詢處理算法TKCSK，通過維護一個優先隊列以及計算每個節點的最小空間文本相關度分來達到剪枝目的.實驗結果表明TKCSK優于Baseline算法.下一步將擴展本文提出的索引和查詢處理算法，將其應用于連續協同空間關鍵詞查詢，另外，由于空間文本數據通常數據量巨大，下一步將對本文提出索引進行并行化.