李敬雯 盧明許 劉彬彬

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

關(guān)鍵詞：情境;室內(nèi)空間;移動對象;群組查詢;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

在室內(nèi)移動對象數(shù)據(jù)管理領(lǐng)域中，研究熱點(diǎn)之一是如何整合和支持更加靈活的查詢操作[1]，如

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

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

1? ?問題描述

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

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

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

2? ?查詢基礎(chǔ)及相關(guān)定義

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

2.1? ?擴(kuò)展SQL語句描述

針對之前提出的兩個情境相關(guān)的室內(nèi)群組Top-k查詢實(shí)例，利用擴(kuò)展SQL語句進(jìn)行描述。

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

2.2? ?群組成員相似度

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

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

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

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

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

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

2.3? ?室內(nèi)情境評分函數(shù)

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

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

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

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

情境相關(guān)的室內(nèi)群組Top-k查詢按評分函數(shù)得分排序返回前k個查詢對象。

3? ?室內(nèi)群組情境Top-k查詢方法

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

3.1? ?Top-k查詢過程

室內(nèi)群組情境Top-k查詢過程分三個步驟，包括群組分組、群組內(nèi)Top-1查詢和整體Top-k查詢?；卺槍個中心的Gonzalez貪婪算法[14]，提出了室內(nèi)群組情境Top-k查詢的近似算法ICGTop-k。

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

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

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

3.2? ?聚集優(yōu)化方法

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

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

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

4? ?實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證情境相關(guān)的室內(nèi)群組Top-k查詢算法的性能，采用C++語言在Windows環(huán)境下對ICGTop-k查詢算法和其他情境感知Top-k查詢算法KBest[15]以及GPM[16]進(jìn)行了實(shí)現(xiàn)。實(shí)驗(yàn)環(huán)境為：Intel（R） Core（TM） i3-2120 CPU 3.30GHz，4GB內(nèi)存，64位操作系統(tǒng)。

4.1? ?實(shí)驗(yàn)設(shè)置

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

4.2? ?結(jié)果分析

實(shí)驗(yàn)結(jié)果均是200次查詢的平均性能，查詢參數(shù)都是基于隨機(jī)選取原則。

室內(nèi)群組情境Top-k查詢處理的性能與很多因素相關(guān)，主要影響因素包括：k值的大小、移動對象的個數(shù)和群組成員的個數(shù)。k值越大，說明查詢需要返回的結(jié)果集規(guī)模越大;移動對象的個數(shù)越多，說明查詢所要處理的對象個數(shù)越多;群組成員的個數(shù)越多，說明群組分組的規(guī)模越大以及查詢所要滿足的情境信息越多，它們與算法的時間復(fù)雜度成正比。對ICGTop-k查詢算法進(jìn)行測試時，可以通過兩個指標(biāo)來衡量其查詢處理效率：查詢執(zhí)行時間和查詢精度。查詢執(zhí)行時間反映了在上述實(shí)驗(yàn)環(huán)境下的查詢響應(yīng)時間，查詢精度反映了算法得到的結(jié)果與最佳結(jié)果之間的差距，它們與算法的具體實(shí)現(xiàn)方案相關(guān)。其中，查詢精度通過近似算法得到的結(jié)果和最佳結(jié)果的交集與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]? ? 萬靜，唐貝貝，何云斌，等. 一種障礙空間中移動對象的連續(xù)k最近鄰查詢方法[J]. 哈爾濱理工大學(xué)學(xué)報，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中國數(shù)據(jù)庫學(xué)術(shù)會議. 2010：692—699.

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

[11]? 金培權(quán)，汪娜，張曉翔，等. 面向室內(nèi)空間的移動對象數(shù)據(jù)管理[J]. 計算機(jī)學(xué)報，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.