情境相关的室内空间群组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.