情境相關的室內空間群組Top-k查詢

李敬雯 盧明許 劉彬彬

摘? ?要：在室內空間移動對象管理中，研究熱點之一是如何整合和支持更加靈活的查詢操作，如Top-k查詢等。針對室內空間群組Top-k查詢需要同時考慮室內空間結構的特殊性、室內空間中復雜而豐富的情境信息以及群組的整體情況的問題，提出了一個近似算法ICGTop-k（Indoor Context-dependent Group Top-k）來計算情境相關的室內群組Top-k查詢的結果集合，進行兩次Top-k查詢得到最終的查詢結果，并采用聚集優化方法對算法進行優化。通過實驗對ICGTop-k算法、KBest算法和GPM算法進行了對比分析。結果表明，ICGTop-k相比于KBest和GPM在查詢執行時間和查詢精度都有顯著提高。

關鍵詞：情境;室內空間;移動對象;群組查詢;Top-k查詢

Context-dependent Group Top-k Query for Indoor Space

LI Jing-wen LU Ming-xu，LIU Bin-bin

（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing，Jiangsu 210007，China）

Abstract：In the management of moving objects for indoor space，one of the research hotspots is how to integrate and support more flexible query operations，such as Top-k query. In view of context-dependent group Top-k query for indoor space，it is necessary to consider the particularity of the indoor space structure，the complex and rich contextual information in the indoor space and the overall situation of the group，an approximate algorithm ICGTop-k （Indoor Context-dependent Group Top-k） is proposed to calculate the result set of context-dependent group Top-k query for indoor space. Top-k query dose twice to get the final query results and the algorithm is optimized by clustering optimization. ICGTop-k ，KBest and GPM algorithms are compared and analyzed through experiments. The experimental results show that the query execution time and query precision of ICGTop-k are significantly improved compared with KBest and GPM.

Key words：context;indoor space;moving object;group query;Top-k query

在室內移動對象數據管理領域中，研究熱點之一是如何整合和支持更加靈活的查詢操作[1]，如

Top-k查詢等。面向室內空間的Top-k查詢不僅需要考慮通常移動對象本身具有的各類信息，還需要考慮室內空間結構的特殊性以及室內空間中復雜而豐富的情境信息[2]，因此使用特定的評分函數來檢索符合查詢要求的最佳匹配對象集合。而在現實生活中，當查詢發起者為團體中的領導者或代表時，通常需要考慮一組人的情況，又或者查詢發起者本身就是一組用戶，這時就要考慮這個群組的整體情況[3]。現在還沒有太多關于室內移動對象群組情境信息的研究。針對以上問題，提出了一個情境相關的室內群組Top-k查詢方法，著重解決在室內空間中帶有情境信息的群組查詢問題。

為了解決情境相關的室內群組Top-k查詢的問題，本文給出了群組內分組方法和室內情境評分函數的定義，基于不同的室內場景分析其通用性;提出了一個近似算法ICGTop-k來計算室內群組情境Top-k查詢的結果集合，通過兩次Top-k查詢得到最終的查詢結果，并采用聚集優化方法對ICGTop-k算法進行優化;進行對比實驗，從多個方面驗證ICGTop-k查詢算法的性能，實驗結果表明，所提出的算法是高效的并且在查詢精度上有所提高。

1? ?問題描述

近年來，基于情境感知的查詢是一個廣泛研究的課題[4]，它可以為正確的對象提供正確的結果，逐漸得到了學術界的認可。基于情境感知的查詢[5]的目的是讓用戶得到基于情境信息的合適的查詢結果，其結果應該滿足用戶在這種場景下的情境信息。一個典型的基于情境感知的查詢問題是，對于同一類型的書籍的選購，書籍的價格各不相同，可能在現實情況下用戶選擇了價格最高的那一本，選擇的理由是基于用戶個人對書籍內容的偏好，而并非通常考慮的價格因素。用戶個人的偏好信息就是屬于情境信息的一種。室內環境下的情境信息復雜而豐富[6]，當用戶處于室內環境中，提出帶有情境信息查詢的可能性更大。除此之外，在現實生活中，用戶提出一個查詢時可能不止考慮自身的要求，也許需要考慮一個群組的情況[7]。因此，如何使查詢結果盡可能滿足一個群組的要求，使群組內成員的不滿意度最小，是面向群組的查詢要解決的關鍵問題。由于群組內的成員規模可能很大，在查詢時按照某種標準對群組內的對象進行分組，然后對每個分組進行Top-k查詢，再對一次查詢結果集進行Top-k查詢，可以提高大規模查詢的效率。考慮到室內空間的特性，移動對象在室內環境下移動時會受室內空間元素的約束，為面向室內空間的情境相關群組查詢帶來更多挑戰。

根據室內環境下用戶的實際需求，下面給出兩種面向室內空間的情境相關群組查詢的實例。比如，在商場逛街的顧客和他的朋友們想要尋找適合休息的區域，顧客希望這樣的區域較安靜，而他的朋友有的希望休息區域的人流量較少，有的希望休息區域光線較弱。在查詢這樣的區域時，從經驗上首先會考慮休息區域的距離因素，考慮到室內空間的特性，以距離較近、最易到達的休息區域作為優先選擇[8]。而顧客和他的朋友們提出的條件中包含了大量的情境信息，所以除了距離因素外還要滿足這些情境要求。由于查詢的發起者是一組用戶，查詢希望能夠盡量得到滿足每個人要求的結果，此時對群組內成員分組，使群組內成員的不滿意度最小化。同時，在查詢之前根據查詢條件對區域進行篩選，可以過濾掉一些與查詢要求相差較大的區域，優化查詢過程，使查詢得到的結果集更接近顧客和他的朋友們的要求。又如，部門秘書在預定會議室時，需要考慮部門內每個人的需求，包括時間、會議室的位置以及其他一些附加情境需求。這些都是情境相關的室內群組Top-k查詢實例。

針對以上實例，提出了一個情境相關的室內群組Top-k查詢方法，重點考慮室內空間下群組的情境需求。首先，給出了群組內的分組標準，將相似度較大的成員歸為一組，并提出了室內情境評分函數，將室內特性和情境信息作為評分函數的主要關注點，對其進行量化，重點解決情境相關的室內Top-k查詢問題;然后給出了一個近似算法ICGTop-k計算室內群組情境Top-k查詢結果，通過兩次Top-k查詢得到最終的查詢結果，并采用聚集優化方法對ICGTop-k算法進行優化;最后，實驗結果表明，所提出的ICGTop-k算法改善了現有方法的查詢性能。

2? ?查詢基礎及相關定義

本節首先通過擴展SQL語句對以上提出的兩個室內場景進行描述，展示了情境相關的室內群組Top-k查詢的具體過程;然后，給出了查詢屬性集合和群組成員相似度的定義，利用群組成員相似度可以對群組內的成員分組;最后，給出室內情境評分函數的定義和計算公式，情境相關的室內群組Top-k查詢按室內情境評分函數得分排序返回前k個查詢對象。

2.1? ?擴展SQL語句描述

針對之前提出的兩個情境相關的室內群組Top-k查詢實例，利用擴展SQL語句進行描述。

根據上面的SQL語句，可以清楚的看到情境相關的室內群組Top-k的查詢過程。例如，對于商場場景下顧客查詢休息室對象時，從休息室集合中選擇對象，考慮身份為顧客的對象提出的查詢條件，然后根據情境評分函數來對對象進行排序，取排序在前k個的對象作為結果返回。

2.2? ?群組成員相似度

用戶提出一個查詢時可能不止考慮自身的要求，也許需要考慮一個群組的情況，或者查詢發起者本身就是一組用戶，這時就涉及群組查詢的問

題[9]。如果群組規模十分龐大，將會導致查詢效率的低下，因此考慮用分組的思想對整個群組進行劃分。由于群組內的成員對于查詢有著不同的要求，可以通過衡量成員間查詢要求的差異來對群組進行劃分，從而將相似性較大[10]的成員放在同一個組內。圖1給出了群組查詢分組的示意圖。

定義1（查詢屬性集合）設群組G = {m1，m2，…，mn}，其中群組中的每個成員mi對查詢有著不同的要求，將不同的查詢要求作為查詢的屬性，從而構成一個查詢屬性集合，即Attr = {Attr1，Attr2，…，Attrn}，其中每個成員的查詢屬性 是查詢屬性集合的子集。

定義2（群組成員相似度）設群組G是多維數據集合，給定元素s和元素t屬于群組G，則相似度函數sim（s，t）表示s和t的關于查詢屬性的相似程度。下面給出sim（s，t）的計算公式：

其中，s.Attr表示元素s中占有的查詢屬性集合，N（s.Attr）表示元素s中占有的查詢屬性個數，t.Attr表示元素t中占有的查詢屬性集合，N（t.Attr）表示元素t中占有的查詢屬性個數，s.Attr∩t.Attr示元素s和元素t共同占有的查詢屬性集合，N（s.Attr∩t.Attr）表示元素s和元素t共同占有的查詢屬性個數。

通過計算群組成員相似度，可以將規模較大的群組劃分成多個相似度較大的小集合SG[i][] = {m1，m2，…，mn}，，即群組相似集合。這些集合之間沒有交集，集合中也沒有重復元素，成員間相似度較大，進行Top-k查詢時得到的結果有更大可能滿足集合內所有成員的要求。在一次Top-k查詢之后將所有結果集合并，然后從中找到最終的前k個查詢結果即Top-k查詢結果。

2.3? ?室內情境評分函數

在室內空間中，由于存在墻、門以及其他障礙實體，導致對象的移動受到限制[11]。因此，在面向室內空間的Top-k查詢中，還需要考慮室內空間特點對查詢結果的影響。而情境信息是室內空間中的一個重要元素，面向室內空間的查詢大多都與情境相關，如何有效地將情境信息加入室內Top-k查詢是一個關鍵性問題[12]。對于室內信息，需要考慮室內空間距離、連通性等，而對于情境信息，需要考慮狀態（如休息室是否開放）、光線、溫度、濕度等。因此，可以對室內信息和情境信息進行量化，通過評分函數得到查詢對象的得分。

對于查詢對象集合Q = {o1，o2，…，oi}，中的一個查詢對象oi而言，它本身具有很多固有屬性，包括室內信息和情境信息。如果查詢對象本身的固有屬性與查詢屬性集合的重合度較高，則它就有更大的可能性出現在Top-k查詢結果集合中。因此，需要量化查詢對象oi與群組成員mj之間的查詢相似度。考慮使用向量空間模型[13]計算查詢相似度，分別構造 和 的向量表示，然后計算其查詢相似度，從而得到室內情境評分函數。

定義3（查詢相似度） oi的向量表示是一個包含N個元素的二元向量V oi，向量V oi中的對應 oi的固有屬性，即 oi.Attr[t]，如果oi.Attr[t]滿足oi的一個基本條件，V oi[t] = 1，否則V oi[t] = 0。mj同理。則給出一個查詢對象oi與群組成員mj查詢之間相似度的計算公式：

定義4（室內情境評分函數）對于查詢對象集合Q = {o1，o2，…，oi}和任一群組相似集合SG[i][] = {m1，m2，…，mi}，根據查詢相似度對情境信息等屬性進行量化，從而得到室內情境評分函數，其計算公式如下：

情境相關的室內群組Top-k查詢按評分函數得分排序返回前k個查詢對象。

3? ?室內群組情境Top-k查詢方法

基于上述對群組分組和室內情境評分函數的分析，本節提出一個室內群組情境Top-k查詢方法，描述了Top-k查詢過程，給出了一個近似算法ICGTop-k計算室內群組情境Top-k查詢結果，并采用聚集優化方法對ICGTop-k算法進行優化，針對群組內的情境信息差別較大的情況，k-means算法對群組成員進行聚類。

3.1? ?Top-k查詢過程

室內群組情境Top-k查詢過程分三個步驟，包括群組分組、群組內Top-1查詢和整體Top-k查詢。基于針對k個中心的Gonzalez貪婪算法[14]，提出了室內群組情境Top-k查詢的近似算法ICGTop-k。

首先給出群組分組算法，利用群組成員相似度將群組分成更小的集合，如算法1所示。在更小的群組相似集合中，成員間相似度較大，則對群組相似集合做Top-k查詢其結果有更大可能滿足集合內所有成員的要求，同時一次查詢后也可以去掉一部分不符合查詢要求的查詢對象，相當于對查詢對象做一次過濾。另外，在原始的群組中可能存在一個成員與其他成員的相似度都很低，則將這個成員單獨劃分為一組，以保證分組后群組相似集合對原始群組的還原度。

算法1給出了群組分組的過程。首先，利用群組成員相似度計算公式 ，從第一個成員開始計算它與之后每一個成員的相似度，如果群組成員相似度不小于給定的界限 ，則將它加入該群組相似集合（第1-5行）;然后，將該成員從原始群組集合中去除，不再將它加入其它群組相似集合中，目的是保證每個群組相似集合間沒有交集（第6-8行）;最后，返回二維數組SG[i][]={SG[1][]，SG[2][]，…，SG[l][]}，即根據群組成員相似度得到的多個群組相似集合（第9行）。

基于上述群組分組函數group，給出室內群組情境Top-k查詢的近似算法ICGTop-k，如算法2所示。算法2給出了室內群組情境Top-k查詢過程。首先，使用群組分組函數group（G）對群組進行分組，得到多個群組相似集合（第1行）;然后對于每一個群組相似集合，根據室內情境評分函數 選擇最合適的查詢對象，即做Top-1查詢（第2-10行）;接著，利用無向圖把選中的查詢對象 設置為圖的頂點，把其對應的室內情境評分函數得分 設置為邊的權重（第11-14行）;最后，從圖中任意頂點出發，利用Gonzalez貪婪算法，得到室內情境評分函數得分排名前k的頂點，即室內群組情境Top-k查詢的結果集合（第15-19行）。

3.2? ?聚集優化方法

當群組內的情境信息差別較大時，可能導致采用群組分組方法得到的每個群組相似集合都只能包含一個或者較少的成員，這時對所有群組相似集合進行Top-k查詢與對整個群組進行Top-k查詢幾乎一樣，失去了分組的意義。因此，在對群組內的情境信息差別較大的情況下，考慮采用聚集優化方法對ICGop-k算法中的群組分組方法進行優化。在聚集優化方法中，k-means算法是聚集效果和計算復雜度都比較適中的算法，相對于普通群組分組方法，其聚集形成的群組更加準確。因此，考慮采用k-means算法對規模較大的群組成員進行聚集，如算法3所示。

在算法3中，首先對聚集集合進行初始化（第1-3行），然后使用k-means算法根據群組成員的查詢屬性集合選取各聚集集合的質心，并根據待聚集節點到質心的距離進行分組（第4-14行）;最后從每個聚集集合中選擇一個代表元素 （第15-18行）。

聚集優化方法可以解決每個群組相似集合都只能包含一個或者較少的成員的問題，保證了室內群組情境Top-k查詢算法ICGTop-k在特殊情況下的查詢性能。因此，在ICGTop-k算法中，群組分組函數group（G）對群組進行分組得到多個群組相似集合后，需要判斷群組相似集合的個數是否過多，如果過多的話則需要采用聚集優化方法對群組進行分組。

4? ?實驗與結果分析

為了驗證情境相關的室內群組Top-k查詢算法的性能，采用C++語言在Windows環境下對ICGTop-k查詢算法和其他情境感知Top-k查詢算法KBest[15]以及GPM[16]進行了實現。實驗環境為：Intel（R） Core（TM） i3-2120 CPU 3.30GHz，4GB內存，64位操作系統。

4.1? ?實驗設置

實驗中的數據集通過數據生成器MWGen[80]模擬生成，模擬的室內空間包括10層樓，294扇門（其中包括14扇單向門），217個房間，18條走廊，1個樓梯。所有房間單元都是通過門與走廊、樓梯連通，移動對象可以在房間內部移動，也可以從房間內移動到走廊、樓梯等區域。實驗模擬2K～10K個移動對象在室內空間的運動情況，并根據情境本體中概念集合 給出的情境類別對查詢對象添加情境屬性，生成查詢所需的模擬數據集。實驗參數設置如表2所示。

4.2? ?結果分析

實驗結果均是200次查詢的平均性能，查詢參數都是基于隨機選取原則。

室內群組情境Top-k查詢處理的性能與很多因素相關，主要影響因素包括：k值的大小、移動對象的個數和群組成員的個數。k值越大，說明查詢需要返回的結果集規模越大;移動對象的個數越多，說明查詢所要處理的對象個數越多;群組成員的個數越多，說明群組分組的規模越大以及查詢所要滿足的情境信息越多，它們與算法的時間復雜度成正比。對ICGTop-k查詢算法進行測試時，可以通過兩個指標來衡量其查詢處理效率：查詢執行時間和查詢精度。查詢執行時間反映了在上述實驗環境下的查詢響應時間，查詢精度反映了算法得到的結果與最佳結果之間的差距，它們與算法的具體實現方案相關。其中，查詢精度通過近似算法得到的結果和最佳結果的交集與k值的比率來計算。

[5]? ? QUAN H，WANG B，ZHANG Y，et al. Efficient and secure Top-k queries with top order-preserving encryption[J]. IEEE Access，2018，6.

[6]? ?AFYOUNI I， RAY C，CLARAMUNT C. Spatial models for context-aware indoor navigation systems：a survey[J]. Journal of Spatial Information Science，2012，4（4）：85—123.

[7]? ? 萬靜，唐貝貝，何云斌，等. 一種障礙空間中移動對象的連續k最近鄰查詢方法[J]. 哈爾濱理工大學學報，2018（3）.

[8]? ? LYARDET F，SZETO D W，AITENBICHLER E. Context-aware indoor navigation[C]// Ambient Intelligence，European Conference，AmI 2008，Nuremberg，Germany，November 19—22，2008. Proceedings. 2008：290—307.

[9]? ? 張一楨，金澈清，胡顥繼，等. BFSQ：處理空間成員查詢的方法[C]// NDBC2010中國數據庫學術會議. 2010：692—699.

[10]? 李淼，谷峪，陳默，等. 一種針對反向空間偏好top-k查詢的高效處理方法[J]. 軟件學報，2017，28（2）：310—325.

[11]? 金培權，汪娜，張曉翔，等. 面向室內空間的移動對象數據管理[J]. 計算機學報，2015（9）：1777—1795.

[12]? AFYOUNI I，RAY C，ILARRI S，et al. Algorithms for continuous location-dependent and context-aware queries in indoor environments[C]// International Conference on Advances in Geographic Information Systems. 2012：329—338.

[13]? LIU H，JIN C，YANG B，et al. Finding Top-k shortest paths with diversity[J]. IEEE Transactions on Knowledge & Data Engineering，2018，PP（99）：1—1.

[14]? WANG S，BAO Z，CULPEPPER J S，et al. Answering Top-k exemplar trajectory queries[C]. IEEE，International Conference on Data Engineering. IEEE，2017：597—608.

[15]? PETIT L，AMO S D，RONCANCIO C，et al. Top-k context-aware queries on streams[M]. Database and Expert Systems Applications. Springer Berlin Heidelberg，2012：397—411.

[16]? LIU G，SHI Q，ZHENG K，et al. Context-aware graph pattern based Top-k designated nodes finding in social graphs[J]. World Wide Web-internet & Web Information Systems，2018（5）：1—20.