随着地理标签信息的广泛使用，越来越多的Web信息系统可通过位置查询为用户提供其感兴趣的搜索结果.这类位置查询主要局限于简单空间查询，例如搜索给定区域内的对象^[1].然而，随着用户需求不断扩展，空间偏好查询成为面向位置服务的搜索应用中重要的查询类型.传统空间查询主要根据对象的空间位置进行查询处理，而空间偏好查询除考虑目标对象的空间位置之外，还要根据目标对象周围的特征对象属性对该对象进行评分，进而搜索满足用户需求的前k个目标对象.

已有的空间偏好查询主要基于两类空间约束对目标对象进行评分^{[2, 3]}，分别是范围约束和最近邻约束.其中，基于范围约束的空间偏好查询根据给定区域内特征对象的属性对目标对象评分；而基于最近邻约束的空间偏好查询则根据作为最近邻的特征对象属性进行评分.例如，用户在选择旅馆时，同等条件下会将旅馆周围的配套坏境也作为参考，有的用户希望旅馆周围有较好的景点和商场(基于范围约束)，有的用户则要求景点和商场距离所选旅馆较近(基于最近邻约束).文献^{[4, 5]}将文献^{[2, 3]}中问题定义里的单个特征对象集扩展到多个特征对象集，同时定义了三种空间函数：范围关系、最近邻关系及影响区域关系，并以R树^[6]作为索引基础提出了SP等算法.文献^[7]在这些工作的基础上,提出一种基于距离-分值空间映射策略的高效查询处理技术，将目标对象和特征对象组成的对象对从二维笛卡尔坐标空间映射到距离-分值空间.以上这些查询都基于单查询点的空间查询语义，没有考虑另一类面向多查询点的空间关系——组近邻关系^{[8, 9]}，不能满足面向组用户偏好的应用需求，需重新设计高效的查询处理方法.因此，本文提出基于λ子集组近邻的Top-k空间偏好查询.

1 问题定义

本文提出的查询主要针对组用户的偏好查询应用.例如，由于旅游旺季剩余客房很少，同去某地旅游的一组用户不能入住同一旅馆，需预定几个旅馆.如图 1所示，O={o₁,…,o₆}表示候选旅馆，商场和景点分别表示为特征对象集F₁和特征对象集F₂，用户从集合O中选择λ个旅馆(λ≤|O|)，且要求距离这组旅馆较近的地方有评价较高的景点和商场.当k=1，λ=3时，特征对象集合F₁中的f_1,3以及特征对象集合F₂中的f_2,2到{o₂,o₃,o₄}的距离和较近且评分较高，则结果集为{o₂,o₃,o₄}.从上述例子可看出，当空间约束从单查询点扩展到多查询点时，查询语义及查询条件与以往的空间偏好查询有很大不同，查询处理过程更为复杂.

定义1 (Top-k空间偏好查询). 给定目标对象集O以及m个特征对象集F₁,…,F_m，Top-k空间偏好查询返回前k个评分最高的目标对象，其中，目标对象的评分取决于与该对象满足给定空间约束的特征对象的评分函数.

定义2 (λ子集). 给定目标对象集O，其λ子集O^λ={o₁,…,o_λ}(o_i∈O),即包含任意λ个目标对象的集合.

定义3 (λ子集组近邻). 给定n个λ子集O₁^λ,…, O_n^λ以及特征对象f(f ∈F)，前k (k<n)个λ子集O₁^λ,…, O_k^λ满足如下不等式时，O₁^λ,…, O_k^λ定义为f的λ子集组近邻：

式中，Gdist(,)表示O^λ中的每个点到f的距离和，称之为组距离，即

其中，dist(,)为两个对象之间的欧式距离.

定义4 (面向组近邻的Top-k空间偏好查询,TSPG). 给定目标对象集O，m个特征对象集F₁,…,F_m以及参数λ，基于组近邻的Top-k空间偏好查询返回SC(O^λ)最高的前k个λ子集，其中评分函数SC(O^λ)的定义为

式中，agg为单调聚集操作，例如求和，求最小值，求最大值等，本文以下所有示例都以求和为例.SC_i(O^λ)表示O^λ为F_i中某特征对象f的λ子集组近邻时的评分函数，即SC_i(O^λ)=r(f )，r(f )为对象f的评价分值，该分值可由已有的评分数据提供商给出.例如f为某一餐馆,其评价分值可通过大众点评网等第三方消费点评网站的数据获取.为方便计算，假定r(f)的数值在^{[0, 1]}内.对于任意O^λ,其评分上限SC_{_u}(O^λ)的定义为

针对上述两类对象集，采用不同的索引结构，对目标对象集采用R树索引，同时，为便于剪枝，对特征对象集采用基于最大值的扩展式R树索引(AR树)，即在R树的每个索引项e中添加统计信息max_er(f)，表示e为根节点的子树中所有索引项的r(f)最大值.

2 Top-k空间偏好查询算法

算法1给出了TSPG处理过程的伪代码.初始化阶段(第1~2行),设置O的R树根节点的索引项集合U，存储top-k结果的最小堆R_k以及R_k中最小的评分值SC^k(即当前第k个最高评分).从R树根节点开始，用函数CSS(U,λ)构建包含U的λ子集的集合，即U^#={ U₁^λ,U₂^λ,…,U_n^λ}(第3行) (注:由于CSS函数的实现较简单,略去细节).如果U^#中的子集U^λ是非叶节点，对U^λ继续计算其λ子集，并将U^#更新为CSS(U^λ,λ)的结果，并重复执行λ子集的计算过程(第4~7行).如果U^λ是叶子节点(此时U^λ等同于O^λ，为方便理解以下所有算法的描述都采用U^λ)，用SNG(U^λ,F_i)计算每个U^λ在F_i上满足λ子集组近邻条件时的评分值SC_i(U^λ) (第8~14行).其中，首次对目标对象进行评分直接调用SNG(U^λ,F_i)，而在以后的评分过程中，需先根据式(4)和上一次评分值计算当前的评分上限，第13和14行给出增量优化策略，当评分上限SC_{_u}(U^λ)小于当前第k个最高评分SC^k，则不必再计算SC_i(U^λ).如果最终计算得到的SC_i(U^λ)大于SC^k，更新R_k及SC^k (第15~16行)，当R树叶子节点被遍历后，返回R_k (第17行).

算法1 TSPQ-G(O,F₁,…,F_m,λ,k) 输入：目标集O,特征集F₁,…,F_m,参数λ,k 输出：最优的k个查询结果
1.    将集合U初始化为O的R树根节点的索引项集合;
2.    R_k←Φ; SC^k←0;
3.    U^#←CSS(U,λ); //构建包含U的λ子集的集合
4.    for U^#中的每个子集U^λ do
5.        if U^λ是非叶节点then
6.            U^#←CSS(U^λ,λ);
7.             跳转到行4;
8.        else
9.            if i:=1 then
10.                    SC_i(U^λ) ← SNG(U^λ,F_i);
11.            for i:=2 to m do
12.                    根据式(4)及SC_i-1(U^λ)计算
                    SC_{_u}(U^λ);
13.                if SC_{_u}(U^λ) >SC^k then //优化
14.                SC_i(U^λ) ← SNG(U^λ,F_i);
15.            if SC_i(U^λ) > SC^k then
16.                    更新R_k及SC^k;
17.            返回R_k;

SNG(U^λ,F_i)初始化全局阈值T_g，该阈值用来表示所有目标对象当前的近邻距离，即 dist(f_j,u_h)，设置当前访问过的所有对象点的组近邻距离最小值Bdist以及F_i中f的λ子集组近邻λGNN.为使连续的λ子集组近邻搜索过程尽量在特征集索引树上的遍历路径相似,首先对U^λ中的对象进行Hilbert排序，即以各个u为顶点做多边形(边数为λ)，找到其质心c_λ，按照这些质心的Hilbert值进行排序.对于U^λ中的每个u_h以及F_i中的对象f_j，初始化其欧式距离dist().当T_g<Bdist时，对每个u_h计算其下一最近邻，并计算其到最近邻的距离，同时更新T_g.当u_h的组距离小于Bdist时，该点是当前的组近邻点，对全局变量进行更新.最后将λ子集组近邻的评分值返回，由于篇幅所限，该算法伪代码略去.

算法1需计算所有目标对象的评分函数值，当目标对象集较大时，该算法计算代价较大，因此,提出基于剪枝策略的处理算法TSPQ-G^*.初始化阶段及U的λ子集计算过程同算法1.对于U^#中的叶子节点λ子集U^λ，算法1是为每个目标对象依次计算评分，为了减少I/O代价，TSPQ-G^*将所有U^λ放入集合W，每次访问特殊目标集时，可通过一次遍历AR树，同时将W中所有元素的评分值计算出来，即调用BNG(W,F_i)计算每个U^λ的SC_i(U^λ)值.当SC_i(U^λ)值小于当前第k个最高评分SC^k时，处理策略同算法1，最后返回结果集.

算法2给出了TSPQ-G^*中的BNG的处理过程.初始化Bdist,λGNN并且设置N为F_i的索引树根节点(第1行).对于W中每个U^λ的u_h，计算Gmdist (U^λ,N)并初始化列表L_u(第2~3行).如果N指向的是非叶结点，按Gmdist(u_h,e)的值由小到大更新L_u，即依据Gmdist(u_h,e)的值由小到大将e插入L_u，从L_u依次取出e并判断是否满足剪枝策略，如果不满足，则继续对列表中的其他元素进行处理，直到满足剪枝策略或者列表为空(第4~12行).如果N指向的是叶子结点，同样依据Gmdist(u_h,f)的值由小到大插入L_u，从L_u依次取出f，如果不满足剪枝条件，则计算λ子集组近邻，直到满足剪枝策略或者列表为空(第13~21行).根据λ子集组近邻结果更新对应的分值,并返回结果(第22~23行)

算法2 BNG(W,F_i)

输入：集合W,特征集F_i
输出：SC_i(U^λ)
1.    初始化Bdist←∞; λGNN ←null; N←F_i.root;
2.    for W中每个U^λ的u_h do
3.    L_u←{N};
4.    for N指向的所有子节点e do
5.    if e是非叶节点then
6.    按Gmdist (u_h,e)的值由小到大更新L_u;
7.    repeat
8.    从L_u取下一个e;
9.    if ∑_h=1^|Uλ|Gmdist(u_h,e) <Bdist then
10.    N←e;
11.    跳转到行4;
12.    until ∑_h=1^|Uλ|Gmdist(u_h,e)≥Bdist 或L_u为空
13.    else
14.    按Gmdist (u_h,f)的值由小到大更新L_u;
15.    repeat
16.    从L_u依次取出f;
17.    if ∑_h=1^|Uλ|Gmdist(u_h,f)<Bdist then
18.    if Gdist(f,U^λ) < Bdist then
19.    λGNN←f;
20.    Bdist←Gdist(f,U^λ);
21.     until∑_h=1^|Uλ|Gmdist(u_h,f)≥Bdist 或 L_u为空
22.    SC_i(U^λ)←r(λGNN);
23.    返回SC_i(U^λ). 3 实验结果与分析

本文采用多个数据集对所提算法效率进行评测.实验配置为Intel Core i3 3.30GHz 处理器，2GB内存.数据集LA streets(LA)及Germany utility(GU)来自R-tree Portal网站¹.其中所有点坐标都归一化到2D空间[1,10000]×[1,10000].由于真实数据集中的特征对象没有已知评分值，采用如下方法生成评分函数r(f)：在地图上随机产生1个锚点a^*，假设距离锚点较近的点其评分值较大，因此，对任意特征对象集F_i，设置mind表示其离a^*最近的距离，maxd表示其离a^*最远的距离，则评分函数r(f)为
r(f)=((mind－dist(f,a^*))/(maxd－mind))^σ . 其中，参数σ控制分布偏度.

通过在不同的数据集中变化数据集大小及各项参数值考察本文所提算法TSPQ-G及TSPQ-G^*的I/O性能指标.为了尽量减少模拟评分函数对实验结果可能带来的影响，以下实验都进行了10次并将去掉最大最小值的8次结果的平均值作为最终结果.由图 2可知，随着λ值增大，查询代价逐渐增加，因为λ值增大，U#会明显增加，导致查询代价增加.图 3中随着σ值增大，两个算法的I/O代价都会随之减小，因为σ值变大之后，SC_{_u}(U^λ)分值较低而剪掉的目标对象个数会增加.

4 结论

本文提出了一种新型空间偏好查询——面向组近邻的Top-k空间偏好查询，解决了基于组近邻空间约束的偏好查询问题.本文给出了查询语义，索引策略及两种查询算法，并设计了基于分值剪枝及空间剪枝策略的优化机制，最后通过基于多个真实数据集的实验验证了所提算法的有效性.