随着空间数据库管理的不断发展, 基于用户角度的top-k查询在许多领域中得到了广泛应用^{[1, 2]}.最近, 学术界提出了反向top-k查询(reverse top-k query)^[3].反向top-k查询查找所有的用户, 这些用户的top-k查询结果包含该查询对象.反向top-k查询主要用于评估某些潜在的产品在市场上的影响力, 可以了解某个产品能够吸引哪些用户或者该产品是否在不同用户偏好之下有很好的排名.由于反向top-k查询能够帮助拥有某个产品的生产者评估该产品对用户的影响, 在商业分析中具有重要价值.

反向top-k问题首次被定义在文献[3]中.反向top-k查询通过查询对象q和用户的偏好集合W来定义, 查询结果是所有满足如下条件的用户:设用户的偏好集合为${W}',{W}'\subseteq W,$满足该用户偏好集合W'的前k'个查询结果中包含q.用户的偏好$w\in {W}'$都用偏好权重$w[i]$表示, 该权重值表示用户对于查询对象的某个属性的偏好程度.与之前的研究类似, 本文仍然假设用户偏好权重被标准化在[0, 1]区间内, 并且同时满足$\sum\nolimits_{i}{w[i]=1}.$

具体以宾馆在线预订为例.如图 1所示, 该空间区域中有7个宾馆和宾馆4种不同设施, 如:餐馆、商场、剧院、咖啡馆(记为${{F}_{1}},{{F}_{2}},{{F}_{3}},{{F}_{4}}$).对于每个宾馆, 给出它与每种设施的最近距离的函数值, 作为该宾馆在每个属性上的得分.假设在该区域中存在3个用户, 分别为May, Jerry和Tom.他们希望宾馆能够与其周围设施的距离越近越好, 每个宾馆及周围设施的分布如图 1(a)所示.若每个用户给出他们对于每种设施的偏好权重值(如图 1(b)所示), 则根据线性模型能够得到每个宾馆对于每个用户的得分情况(该例中, 用户对于宾馆的得分值越高越好, 并且假设空间最大距离为10).从该例中可以得出以下结果:May的top-2宾馆为${{o}_{2}}$和${{o}_{3}}$(得分函数为$\sum{w[{{F}_{i}}]}\cdot (10-dist({{o}_{i}},{{F}_{i}})),$其中, $dist({{o}_{i}},{{F}_{i}})$是宾馆到不同设施的最短距离), 同理, Jerry的top-2宾馆为${{o}_{6}}$和${{o}_{7}}$, Tom的top-2宾馆为${{o}_{2}}$和${{o}_{5}}$.因此, 宾馆${{o}_{2}}$的反向top-2的结果集是Marry和Tom, 而宾馆${{o}_{3}}$的反向top-2结果集为May.

到目前为止, 已知最好的解决反向top-k查询的算法是RTA算法^[3](阈值分析法)和BBR法算法(分支定界法)^[4].但是, RTA算法在处理反向top-k查询时存在着如下缺点:(1) RTA需要访问所有的用户.对于每一个用户, 在给定的一个缓存区中, 如果查询对象的排名低于在缓冲区中任意对象的排名, 则这个对象被排除在用户的top-k列表中; 否则, 继续计算查询对象的排名并且更新缓存区.(2) RTA要求对属于结果集的每个用户的偏好权重值去执行一个top-k操作.当用户数量很多时, RTA算法的计算代价很大.不同于RTA算法, BBR算法能够有效地解决当用户数量很多时的反向top-k查询, 因为不需要访问每个用户的偏好.

在实际生活中, 无论是用户对空间对象的偏好, 还是对空间对象的属性, 都不仅需要考虑非空间性质, 而且也需要考虑空间性质.空间性质是指与对象相邻的周边设施相关的属性(如, 欧式距离).之前有一些文献提出, 在执行查询之前, 把空间对象与周边设施相关的空间属性转化成其非空间属性, 但是, 这样做只适合当空间对象周边设施种类较少时.实际上, 空间中设施的种类有很多, 并且用户给出的偏好的数量远小于设施种类的数量, 所以预先计算出所有空间对象到不同设施的空间属性浪费了大量的存储空间, 给查询处理的性能带来相当大的困难.

同样以图 1中的宾馆在线预订为例.如果图 1(b)中宾馆o周围可能存在的不同设施有100种, 简单记为${{F}_{1}},{{F}_{2}},...,{{F}_{100}},$并且每一种设施对象的数量有很多, 然而用户提出的偏好可能只有其中的几种, 如May的偏好为$({{F}_{49}}:0.3,{{F}_{100}}:0.7),$Jerry的偏好为$({{F}_{1}}:0.4,{{F}_{80}}:0.6),$Tom的偏好为$({{F}_{12}}:0.1,{{F}_{49}}:0.4,{{F}_{100}}:0.5).$

为了解决上述提到的浪费大量存储空间的问题, 本文提出一种新型的查询, 称为反向空间偏好top-k查询.该查询的查询结果与反向top-k查询结果相同.不同之处在于, 对象的属性不是直接给出, 而是由对象与周边设施的空间位置关系计算得到.假设一个宾馆经理根据不同用户给出的不同偏好, 想知道哪些宾馆有更高的得分, 反向空间偏好top-k查询的结果不仅可以把宾馆推荐给未来一些对宾馆有偏好属性的用户, 而且也可以为不太受欢迎的宾馆在其周围进行招商.然而, 随着宾馆周围设施种类的不断增加, 将给查询处理性能带来很大的挑战.本文针对这样的问题提出一些优化算法加以解决.

本文的贡献点如下:

1)本文定义了一种新型的查询, 称为反向空间偏好top-k查询(RSP-k查询).虽然传统的反向top-k查询也能处理从空间对象角度出发的查询, 但是它们并没有考虑到对象周围的设施及对象与这些设施间的位置信息.

2)本文提出了一些新颖的解决方案来有效地处理反向空间偏好top-k查询(RSP-k查询).现有的方法直接处理这类问题会产生巨大的存储代价, 存在较高的时间复杂度$O(m\cdot n)$和较高的空间复杂度$O(n\cdot F),$其中, m是用户的数量, n是查询空间对象的数量, F是对象周围的设施种类数量.因此, 本文提出4种方法来有效地减少代价:(1)基于R-tree的基本算法; (2)批量计算对象的剪枝算法; (3)改进的批量剪枝算法; (4)用户的偏好权重分组算法.前3种方法采用不同的索引结构来减少对查询对象得分的计算量.第4种方法针对用户偏好权重, 把所有用户按照一定的规则进行分组以减少查询计算量.

3)在真实数据集和模拟数据集上进行充分的实验, 验证了所提出方法的有效性.

本文第1节回顾与本文相关的研究工作.第2节提出新型的RSP-k查询并给出形式化的定义.第3节介绍4种优化策略并给出详细的算法.第4节针对本文提出的每一种优化算法, 分析其时间复杂度和空间复杂度.第5节给出充分的实验结果, 展示所提出算法的有效性.第6节对全文进行总结.

1 相关工作

近年来, 支持有效的top-k查询过程已经在数据库研究中得到了广泛的关注.而反向top-k查询是和top-k查询有着十分紧密的关联.下面, 总结一些具有代表性的研究的大致思路.

Top-k查询^[5-8]提出了一种方便的方法, 用户可以通过其偏好来找到很重要的对象.文献[6]提出了一种阈值的方法.该方法是在一个聚合函数f下, 从不同的存储列表中合并对象的排名.阈值算法以循环方式按顺序扫描列表, 并且计算每一个对象的聚合得分, 从而维护top-k结果集.一旦剩余对象的聚合得分没有超过到目前为止被找到的top-k结果, 则阈值算法终止.由于阈值算法的普遍性, 有许多阈值算法的变形被提出来(如文献[5]).文献[9]首先生成实体化视图, 一个top-k查询通过扫描与查询最相似的视图被回答.当top-k查询不断地被提出来时, 一个算法可以决定最好的视图被实体化.然而, 在文献[9]中, 需要在确保满足性能之前实体化很多视图.

文献[7]中提到了BRS方法.该方法是通过R*-tree来处理数据对象的top-k查询的一个分支定界算法.BRS使用一个堆来维护候选记录, 以从上到下的方式遍历R*-tree.在每一次迭代中, BRS从堆中取最好的记录.如果记录是R*-tree的叶子节点, 那么该记录输出作为下一个结果; 如果已经有了足够多的结果(k个), 则算法停止.如果该记录是中间节点, 那么对应的节点将被存储并且对于该节点的每一条记录e的最大得分被计算出来, 同时将e插入到这个堆中.正像文献[9]这样, BRS是一种优化I/O的算法, 这意味着它访问仅仅包含top-k结果的树中的节点.由于最大得分是一个通用的概念, 所以该算法能够同时应用在单色和非单色的偏好函数上.

Yiu等人^{[10, 11]}首次研究空间偏好top-k查询问题.他们把对象分为两类:数据对象和辅助对象, 并且建立索引分别索引两种不同对象.其中, 数据对象被存在R-tree中, 每一种辅助对象集被存在一个单独的聚合R-tree中(aR-tree)^[12].同时, 他们提出3种算法来解决基于R-tree和aR-tree的空间偏好查询.为了提高算法在文献[10]中的有效性, Rocha-Junior等人提出一种方法来解决基于实体化方法的空间偏好top-k查询问题, 从而在很大程度上节省了计算代价和I/O代价.近年来, 处理空间偏好top-k查询的问题已经在路网上展开了研究^{[13, 14]}.然而, 无论是传统的top-k查询还是空间偏好top-k查询都是从用户角度考虑, 而没有从空间对象的角度考虑.

反向最近邻查询(RNN)和反向skyline最近邻查询返回对一个给定查询点作为最近邻查询点的一个集合^[15].现在已有两种方法进行RNN查询:基于预计算的方法和动态方法^[16].基于预计算的方法是预计算每一个点的k近邻结果集之后存储在系统中一些必要信息, 为了更好地、有效地执行未来的某个查询^[17].第2种动态方法经常使用一个索引结构来加速查询过程, 比如R-tree^{[18, 19]}.

多样的top-k查询已在文献[20]中进行研究.文中给出一组数据点集合和一系列排名函数, 并提出一些方法来计算所有关于top-k的函数, 称为全top-k查询.文中提到的方法利用相似查询分享共同的结果来避免一个个地估计top-k查询.第1种算法(BINL)假设数据点被索引在一个多维索引结构上, 并且函数基于相似性被分成组.BINL分别处理每一组函数, 并且为了避免计算MBRs的精确得分, 使用界值来代替.虽然BINL减少了需要被检索的所有top-k查询的计算代价, 但是BINL却不支持提前结束, 这意味着数据点在索引结构中不得不被每一个函数分组遍历一次.于是文中提出了第2种方法, 再物化视图的BLPTA.BLPTA通过遍历一次视图应答多样的top-k查询, 并且可以提前终止算法.

与本文最相关的是反向top-k查询^{[3, 21]}.反向top-k通过市场中潜在的商品对用户的影响被提出来, 这些商品被认为是一些用户偏好的top-k结果.近年来, 许多变化的反向top-k查询被提出来, 包括识别最有影响的空间对象^[22]、基于移动用户的位置流行程度的监测^[23].代表性的工作是基于阈值的算法(RTA)^[3]、基于网格算法(GRTA)^[3]和基于分支定界算法的反向top-k查询(BBR)^[4].通过一个小的缓存区, RTA访问所有的用户.对于每一个用户, 如果查询的空间对象的排名小于缓存区中任意一个空间对象的排名, 那么该空间对象明显不属于用户偏好的top-k空间对象; 否则, 算法将继续查询空间对象的精确排名并且同时更新缓存区.GRTA划分整个空间对象空间为一系列的网格, 然后在内存中实现一些反向top-k的视图以有效地处理查询过程.BBR使用分支定界的思想, 从而达到不需要访问每个用户的偏好来处理查询过程的目的.

Zhang等人^[17]研究反向k排名问题.他们假设有一系列查询向量Q和一系列数据记录D.给定一个正整数M和一个兴趣点$p\in D,$查询在Q中对于p的前m个候选的查询向量.他们考虑了查询向量是带有约束的, 所提出的剪枝算法基于查询向量的特定位置来实现.

然而, 这些反向top-k查询及变形与本文提出的RSP-k查询有着本质的不同.对于对象的属性, 无论是空间性质还是非空间性质, 在进行查询之前, 这些属性得分都是预先给定的, 而本文考虑的对象属性与其周围设施的空间位置相关, 并且在得到用户偏好后再计算对象的属性得分.

2 问题定义

令D表示一个包含n个空间对象的集合, 即$D=\{{{O}_{1}},{{O}_{2}},...,{{O}_{n}}\}.$并且每一个对象O被表示为一个元组$O=\langle l,F\rangle ,$其中, l表示对象O的空间位置, F表示对象O的一个标签.假设标签种类共有c种, 即F有c个不同种类, 把c个不同种类的标签表示为一个集合, 即$\{{{F}_{i}}|i\in [1,c]\}.$在c个标签种类的空间对象中, 对应于查询对象的标签称为主标签, 所有具有主标签的对象称为主体对象.其余c-1种对象作为用户的偏好被提出来, 称为辅助对象.W是m个用户提出的偏好权重集合, 每一个用户提出的偏好权重被描述成一个可用向量表示的${{w}_{i}},$即${{w}_{i}}=\{{{F}_{j}}\}.$ ${{w}_{i}}$中的一个向量${{F}_{j}}$表示用户i对标签为${{F}_{j}}$的对象感兴趣, 并给出对于该标签的偏好权重值, 表示为${{w}_{i}}[{{F}_{j}}],$简写为${{w}_{i}}[j].$假设集合W已知, 那么对于一个用户${{w}_{i}}$来说, 有$\sum\nolimits_{j=1}^{c-1}{{{w}_{i}}[j]=1}.$这种带有偏好的权重模型已经在许多相关文献中广泛应用^[20-28].

为方便表示, 以下用${{F}_{j}}$代替$O.{{F}_{j}}$表示标签为${{F}_{j}}$的空间对象.假设用符号o表示主体对象, 对于任意一个用户i, 由得分函数$f({{w}_{i}},o)$来计算主体对象o对于用户i的得分.该函数被定义为$f({{w}_{i}},o)=\sum\limits_{j=1}^{c-1}{\left( {{w}_{i}}[j]\left( 1-\frac{\min d(o,{{F}_{j}})}{{{d}_{\max }}} \right) \right)},$其中, $\min d(o,{{F}_{j}})$表示主体对象o与标签为${{F}_{j}}$的所有辅助对象中最近的一个对象的距离, ${{d}_{\max }}$表示给定空间中容忍的最大距离.不失一般性, 假设一个用户对空间中一个对象的偏好是得分越大越好, 也就是说, 对于用户提出的偏好, 具有该偏好标签的辅助对象离主体对象的距离越近越好.

因为top-k查询和反向top-k查询与本文的工作有很强的相关性, 所以首先回顾一下相关两个查询的定义, 然后提出反向空间偏好top-k查询(RSP-k查询).

定义1(top-k查询(TP(k, w))).给定一个空间对象数据库D, 一个用户的偏好w和一个正整数k, top-k查询返回一个对象集合$S,S\subseteq D,|S|=k.$那么, 对于$\forall {{o}_{i}}\in S,\forall {{o}_{j}}\in (D-S),$有$f(w,{{o}_{i}})\ge f(w,{{o}_{j}}).$

定义2(反向top-k查询)^[3].给定一个对象数据库D, 一个权重集W, 一个正整数k'和一个指定的查询点q, 反向top-k查询返回一个权重集W中的一个集合$S,S\subseteq W.$对于每一个$w\in S,q\in TP(k,w),$相反, 对于任意一个$w\notin S,q\notin TP(k,w).$

下面介绍本文提出的反向空间偏好top-k查询(RSP-k查询).RSP-k是反向top-k的变形.

首先了解一下RSP-k查询与反向top-k查询不同的相关定义.

定义3(空间地理对象).一个空间地理对象表示为一个元组$O=\langle l,F\rangle ,$其中, l表示空间中对象的经度和纬度位置(例, 52.16N, 21.76E), F表示该对象的一个标签(例, 宾馆).

进一步, 给出RSP-k查询的定义.

定义4(反向偏好top-k(RSP-k)查询).给定一个含有n个空间地理对象的数据库D, D中包含主体对象和辅助对象, 用户的权重集合W和一个正整数k, 若o表示主体对象, 则RSP-k查询返回一个集合$S,S\subseteq W.$对于$\forall {{w}_{i}}\in S,\forall {{w}_{j}}\in (W-S),$有$f({{w}_{i}},o)\ge f({{w}_{j}},o).$

下一节, 本文将提出几种新颖的解决方案, 以有效地处理RSP-k查询.

3 查询处理方法

本节介绍几种优化方法, 以有效地处理所提出的RSP-k查询问题.首先给出系统结构, 如图 2所示.通过对空间对象和用户的同时处理, 最终得到结果集.

3.1 基于R-tree的剪枝算法

最直接的方法是计算每一个主体对象对每一个用户提出的偏好的得分, 但是计算代价特别大.通常, 可以利用R-tree避免查询时产生的巨大计算代价.本节提出一种基于R-tree的剪枝算法来处理RSP-k查询.基于R-tree的方法是基于文献[4]中分支定界的方法而提出的.

首先, 回顾一下两个点的支配关系.这种关系被很多文献提到过, 包括skyline^[29]和反向top-k查询^[3].

定义5(支配).一个对象o₁能够支配另外一个对象o₂当且仅当满足以下两个条件:(i) $\forall j,{{o}_{1}}[j]\le {{o}_{2}}[j]$; (ii) $\exists h,{{o}_{1}}[h]<{{o}_{2}}[h].$其中, $o[j],o[h]$是对象o对于属性j, h的得分.

从定义5可以推出, 若$f({{w}_{i}},o)$表示返回对象o对偏好${{w}_{i}}$的得分函数, 则对于$\forall i,{{w}_{i}}\ge 0,$当对象o₁支配另外一个对象o₂时, 有$f(w,{{o}_{1}})\le f(w,{{o}_{2}}).$当RSP-k查询发出时, 为所有的主体对象构建一个R-tree索引.r表示在R-tree上的一个最小边界矩形(MBR), ${{r}_{\min }}$和${{r}_{\max }}$表示r与${{w}_{i}}$中辅助对象距离的最小值和最大值.

根据以上分析可以得到两个推论.

推论1.给出一个查询对象q, 一个偏好权重${{w}_{i}}$和R-tree上的一个MBR r.如果$f({{w}_{i}},q)<f({{w}_{i}},{{r}_{\max }}),$那么对于$\forall o\in r,$有$f({{w}_{i}},q)<f({{w}_{i}},o),$可得r中所有对象o的排名都比q靠前.

推论2.给出一个查询对象q, 一个偏好权重${{w}_{i}}$和R-tree上的一个MBR r.如果$f({{w}_{i}},{{r}_{\min }})<f({{w}_{i}},q),$那么对于$\forall o\in r,$有$f({{w}_{i}},o)<f({{w}_{i}},q),$可得r中所有对象o的排名都比q靠后.

算法1展示了基于R-tree剪枝算法的主要步骤.

算法1.基于R-tree的剪枝算法(RT).

1. Input: $Q,{Q}';$ /*初始化两个队列$Q$和${Q}'$*/

2.     $\mathbb{R}[{{w}_{i}}]\leftarrow \varnothing ,$${W}'\leftarrow \varnothing ;$ /* $\mathbb{R}[{{w}_{i}}]$记录q在每个用户权重${{w}_{i}}$中的排名, W'记录结果的集合*/

3. Output: W'

4. for each ${{w}_{i}}$ in W do     /*对于每一个用户提出的偏好*/

5.   enqueue($Q,R.root$);

6.   while ($r=dequeue(Q)\ne \varnothing $) do

7.     if ($f({{w}_{i}},{{r}_{\min }})<f({{w}_{i}},q)$) then     /*满足推论2时*/

8.       prune all the objects in r;     /*剪枝掉MBR r中所有对象*/

9.     else if ($f({{w}_{i}},q)<f({{w}_{i}},{{r}_{\max }})$) then     /*满足推论1时*/

10.        $|\mathbb{R}[{{w}_{i}}]|\leftarrow |\mathbb{R}[{{w}_{i}}]|+|r|;$     /*计算在查询对象q排名之前的对象数量*/

11.     if ($|\mathbb{R}[{{w}_{i}}]|<k$) then

12.       if (Dis a leaf node) then     /* MBR r是叶子节点*/

13.         enqueue(${Q}',$r);

14.       else if ($\forall {r}'$ is ${r}'s$ child) then     /* MBR r是非叶子节点, 对r的孩子节点进行操作*/

15.         enqueue(Q, r);

16.     for each r in Q' do

17.       for each oin r do

18.         if $f({{w}_{i}},o)>f({{w}_{i}},q)$ then

19.          $|\mathbb{R}[{{w}_{i}}]|\leftarrow |\mathbb{R}[{{w}_{i}}]|+1;$     /*对所有排名在查询对象q之前的对象都放到W'中*/

20.         ${W}'\leftarrow {W}'\bigcup \{{{w}_{i}}\};$

21.     return W';

假设所有的主体对象已经在R-tree上被索引.首先, 初始化两个队列Q和Q'(第1行).根据查询过程, 通过遍历R-tree来计算每个用户提出的偏好${{w}_{i}}\in W$的得分并进行排名.对于每一个在R-tree上的MBR r(第4行、第5行), 算法计算关于${{w}_{i}}$的${{r}_{\min }}$和${{r}_{\max }}$的得分.通过推论1和推论2, 如果节点满足$f({{w}_{i}},q)<f({{w}_{i}},{{r}_{\max }})$或者$f({{w}_{i}},{{r}_{\min }})<f({{w}_{i}},q),$则节点被安全地剪枝掉(第6行~第10行).否则, 所有r中的孩子节点(当o是非叶子节点时)被添加到Q中做进一步查询.队列Q'记录所有未被剪枝的叶子节点(第12行~第16行).

基于R-tree的剪枝算法的优势在于可以将所有与辅助对象距离相近的主体对象通过MBRs同时进行估计.然而, 这种方法必须考虑计算出所有用户偏好的辅助对象与主体对象之间的距离.这样不仅浪费存储代价而且查找起来也会消耗大量时间.下面提出一种优化计算方法, 当用户给出偏好权重时, 可以快速地查找到RSP-k查询的结果集.

3.2 批量计算主体对象的剪枝算法

当主体对象的数量很多时, 实际就会有很大一部分主体对象不属于任何用户的top-k个结果.所以不需要把所有主体对象与其最近的所有辅助对象的距离都计算出来, 只需要通过用户的偏好来计算.那么, 为了更快地计算, 本节采用一种Quad-tree索引结构来聚集空间中的主体对象.

在本文中使用Quad-tree索引的原因是Quad-tree方便更新.因为Quad-tree中的每个网格(cell)都会把RSP-k查询中的所有主体对象索引在一个互斥的cell中, 所以对主体对象进行插入或者删除操作都简单、方便.相反地, 在R-tree索引的MBR r中, 可能存在互相重叠的MBR r, 这样, 当对空间中主体对象进行插入或删除时, Quad-tree平均耗时远小于R-tree的插入和删除的花费.

另外, 为了避免计算所有的主体对象到其辅助对象之间的最短距离, 本文也把辅助对象进行了索引, 这样不仅能够方便查询, 而且也能减少计算代价.具体方法如下:

1)为了把有距离相近的主体对象进行聚集, 对主体对象用Quad-tree建立索引.同时, 为了最大化有效地剪枝并且减少查询计算量, 所有辅助对象建立一个IR-tree^[17].索引结构如图 3~图 5所示.其中, 图 3表示主体对象和辅助对象在空间中的分布情况, 图 5是对图 3中的主体对象和辅助对象分别建立的索引结构, 图 4是辅助对象在IR-tree的倒排文件中的具体信息.根据用户提出的偏好W, 得到用户提出的偏好的辅助对象F_i由辅助对象的IR-tree找出与查询对象q最近的包含F_i的MBR r.

2)对于每一个用户给定的偏好${{w}_{i}},$根据Quad-tree索引, 每个带有主体对象的cell c都需要找到最近的包含F_i的MBR r.比较q所在cell c.q与r.F_i的最近距离$\min dist(c.q,r.{{F}_{i}})$和其他主体对象所在cell c'o与r.F_i的最远距离$\max dist({c}'.o,r.{{F}_{i}}),$比较c.q与r.F_i的最远距离$\max dist(c.q,r.{{F}_{i}})$和其他c'o与r.F_i的最近距离$\min dist(c.o,r.{{F}_{i}})$.

当满足$\min dist(c.q,r.{{F}_{i}})>\max dist({c}'.o,r.{{F}_{i}})$和$\max dist(c.q,r.{{F}_{i}})<\min dist({c}'.o,r.{{F}_{i}})$条件时, 该主体对象${c}'.o$所在cell被存在一个缓存区中.其余的对象将进行精确计算.可以得到以下的推论.

推论3.给出一个查询对象q所在的cell c, 一个辅助对象F_i所在MBR r.如果$\min dist(c.q,r.{{F}_{i}})>\max dist({c}'.o,r.{{F}_{i}}),$那么对于所有c'中的对象o, 有$f({{F}_{i}},q)<f({{F}_{i}},{c}'.o),$可得查询对象q和主体对象o关于辅助对象F_i的得分, c'中所有对象o的排名都比查询对象q靠前.反之, 如果$\max dist(c.q,r.{{F}_{i}})<\min dist({c}'.o,r.{{F}_{i}}),$则c'中所有对象o的排名都比查询对象q靠后.

证明:若存在$\min dist(c.q,r.{{F}_{i}})>\max dist({c}'.o,r.{{F}_{i}}),$则可以得到, 在cell c中任意位置的查询对象q与另一个cell c'中的对象o满足:$dist(q,r.{{F}_{i}})>\max dist({c}'.o,r.{{F}_{i}}),$根据得分$f({{w}_{i}},o)=\sum\limits_{j=1}^{c-1}{\left( {{w}_{i}}[j]\left( 1-\frac{\min d(o,{{F}_{j}})}{{{d}_{\max }}} \right) \right)},$可以推导出$f({{F}_{i}},q)<\min f({{F}_{i}},{c}'.o),$有$f({{F}_{i}},q)<f({{F}_{i}},{c}'.o),$所以可得查询对象q和主体对象o关于辅助对象F_i的得分, c'中所有对象o的排名都比q靠前.若存在$\max dist(c.q,r.{{F}_{i}})<\min dist({c}'.o,r.{{F}_{i}}),$则可以得到对于在cell c中的任意位置的查询对象q与另一个cell c'中的对象o满足:$\max dist(q,r.{{F}_{i}})<dist({c}'.o,r.{{F}_{i}}),$可以推导出$\min f({{F}_{i}},q)>f({{F}_{i}},{c}'.o),$有$f({{F}_{i}},q)>f({{F}_{i}},{c}'.o),$所以可得查询对象q和主体对象o关于辅助对象F_i的得分, c'中所有对象o的排名都比q靠后.

3)找出所有用户提出的偏好的所有辅助对象F_i与查询对象q和主体对象o之间的关系.

4)为了快速并且有效地得到推论3, 根据以上步骤进行验证.若满足推论3中c'中所有对象o的排名都比q靠前, 则说明Quad-tree cell中的对象o对于用户提出的偏好无论权重的得分, 一定大于对象q, 如果个数大于k, 则说明查询对象q不是RSP-k查询的结果.若个数没有达到k, 则需要精确求解, 求解之前, 需要观察是否满足推论3中c'中所有对象o的排名都比q靠后, 若满足, 则这些节点中的主体对象o不参与精确计算, 被安全地剪枝掉.剩下的点进行精确求解, 当求到有k个主体对象得分时, 算法结束.

以图 3为例, 考虑空间数据库中包含主体对象集$D=\{{{o}_{1}},{{o}_{2}},...,{{o}_{7}}\}$及其中一个查询点q和辅助对象集, 已知用户偏好数据库包含3个用户, $W=\{{{w}_{1}},{{w}_{2}},{{w}_{3}}\},$并且每个用户的偏好辅助对象及偏好权重分别为${{w}_{1}}=({{F}_{1}}:0.4,{{F}_{3}}:0.6),{{w}_{2}}=({{F}_{1}}:0.7,{{F}_{2}}:0.3),{{w}_{3}}=({{F}_{1}}:0.8,{{F}_{3}}:0.2).$假设k=2首先, 检验w₁可以看到, w₁中提到的辅助对象是F₁和F₃从图 3和图 4中看出, 含有F₁的对象在MBRs R₂, R₃, R₄和R₇中, 其次观察查询点Q所在的cell c₁₂和其他cell与R-tree上的R₂的关系.经计算, q到R₂的最近距离是0, 最远距离是12.从Quad-tree结构中可以看出, 没有任何一个cell到R₂的最远距离小于q到R₂的最近距离, 所以不存在能够被剪枝掉的主体对象.同时, 没有任何一个c到R₂的最近距离大于q到R₂的最远距离, 所以也不存在能够被剪枝掉的主体对象.如此继续查找R₄同样观察q到R₄的最近距离是7, q到R₄的最远距离是12, 能够得到c₂₅和c₂₈到c₂₇的最远距离都比q到R₄的最近距离要近, 则记录偏好对象F₁到q的距离大于所有在cell c₂₅和c₂₈到c₂₇中的对象到q的距离.同时记录辅助对象F₁到对象的距离一定远于F₁到q的距离, c₁₃, c₁₄和c₁₅.类似地, 找出辅助对象F₃与查询对象q和其他主体对象的关系.

3.3 改进的批量剪枝算法

之前的方法虽然有效地减少了计算的工作量.但是在过滤掉不可能成为任何用户的top-k的对象后, 如果剩余需要计算的每个叶子节点中的对象数量很多, 那么计算代价大仍是问题.本节提出一种改进的批量剪枝算法, 以进一步降低计算代价.

在批量剪枝算法进行完对主体对象剪枝后, 需要对Quad-tree中未被剪枝的cells中所有主体对象进行精确计算得分.为了更加有效地剪枝和减少计算代价, 本文在批量剪枝后进一步利用Quad-tree中心点来划分空间.

具体划分方法如下:对于不能直接过滤的同一个cell中的主体对象, 根据该cell的中心点向下划分, 并且根据用户给出的偏好权重值来判断该cell的子节点中的主体对象是否需要被精确求解.

已知一个cell被划分为4个子节点, 并且每个子节点的边长为l_c如果中心点表示为c_v那么根据正方形定理可以得到:

$ d({{c}_{v}},{{F}_{i}})-\frac{\sqrt{2}}{2}{{l}_{c}}\le d(o,{{F}_{i}})\le d({{c}_{v}},{{F}_{i}})+\frac{\sqrt{2}}{2}{{l}_{c}}, $

于是可以得到Quad-tree中任意一个对象o到辅助对象F_i的最近距离和最远距离.

定理1. Quad-tree中任意一个对象o到辅助对象F_i的最近距离为$d(o,{{F}_{i}})=d({{c}_{v}},{{F}_{i}})-\frac{\sqrt{2}}{2}{{l}_{c}},$最远距离为$d(o,{{F}_{i}})=d({{c}_{v}},{{F}_{i}})+\frac{\sqrt{2}}{2}{{l}_{c}}.$

证明:根据Quad-tree的性质, 每个节点都是由一个正方形组成.那么对于一个正方形中任意的一个点o到正方形的边缘的距离都存在$\pm \frac{\sqrt{2}}{2}{{l}_{c}}$的误差, 其中${{l}_{c}}$为该正方形的边长.因此可以得到对于正方形内任意一点到空间中另外一点的最大、最小距离分别为$d(o,{{F}_{i}})=d({{c}_{v}},{{F}_{i}})+\frac{\sqrt{2}}{2}{{l}_{c}}$和$d(o,{{F}_{i}})=d({{c}_{v}},{{F}_{i}})-\frac{\sqrt{2}}{2}{{l}_{c}}.$

算法2给出了改进的批量剪枝算法具体流程.

算法2. RSP-k($q,W,k$).

1. Input: Q, Q'$\mathbb{R}[{{w}_{i}}]\leftarrow \varnothing ,$${W}'\leftarrow \varnothing ;$ /*初始化队列Q和Q’$\mathbb{R}[{{w}_{i}}]$记录q在每个用户权重w_i中的排名,

W'记录结果的集合*/

2. Output: W';

3. enqueue(Q, Quad-tree.Root);

4. while ($c=dequeue(Q)\ne \varnothing $) do

5.   if ($\max dist(c.q,r.{{F}_{i}})<\min dist(c.o,r.{{F}_{i}})$) then

6.     prune all the objects in c; /*剪枝掉cell c中所有对象*/

7.   else if ($\min dist(c.q,r.{{F}_{i}})>\max dist(c.o,r.{{F}_{i}})$) then

8     $|\mathbb{R}[{{w}_{i}}]|\leftarrow |\mathbb{R}[{{w}_{i}}]|+|c|;$ /*所有排名比查询对象q靠前的对象都放入$\mathbb{R}[{{w}_{i}}]$中*/

9.     if ($|\mathbb{R}[{{w}_{i}}]|<k$) then /* W'中对象数量小于k'个, 继续划分cellc */

10.        if (c is a leaf node & & $Num(c)<\lambda $) then /* cell c是叶子节点并且cell c中主体对象的数量

比给定阈值$\lambda $小时*/

11.          enqueue(${Q}',c$); /*对于不能划分的cell c, 进行求解计算*/

12.      if ($Num(c)\ge \lambda $) then /*当cell中主体对象的数量比给定阈值$\lambda $大时*/

13.       divide c; /*继续分割cell c */

14.   for ($\forall {c}'$ is the children of c) do /*对于继续划分的cell c, 对其孩子节点进行优化*/

15.    enqueue($Q,{c}'$);

16.     for each c' in Q' do

17.       for each object o in c' do

18.          if $f({{w}_{i}},o)<f({{w}_{i}},q)$ then

19.            $|\mathbb{R}[{{w}_{i}}]|\leftarrow |\mathbb{R}[{{w}_{i}}]|+1;$

20.            ${W}'\leftarrow {W}'\bigcup \{{{w}_{i}}\};$

21.   return W';

若一个子节点的中心点与辅助对象所在的MBR r的最近距离的得分小于查询点q到相同偏好对象的MBR r距离得分, 则这个子节点中的所有主体对象的得分都比q的得分小, 不需要考虑这个子节点中的主体对象, 该子节点中的主体对象被安全剪枝(第4行、第5行).否则, 计算其与辅助对象所在的MBR r的最远距离的得分, 若得分大于查询点q到相同辅助对象的MBR r的距离的得分, 则需要计算整个子节点中的对象的个数, 使用一个参数$\lambda $控制cell的划分.如果cell中主体对象的数量$Num(c)$大于$\lambda $, 则该cell向下划分; 否则不继续划分(第6行~第12行).若其中所有对象的得分都比q的得分大, 则该节点中的所有对象点都被保留在之前的缓存区中, 如果缓存区中对象的个数大于k个, 则查询点q不是用户w的前k'个结果; 若个数小于k, 则继续进行精确求解(第13行~第19行).

以上研究的3种方法都是针对主体对象和辅助对象如何剪枝而提出的, 对于用户偏好的提出并没有做出优化.因此, 仍然需要对每一个用户进行计算.下一节提出针对用户偏好的处理方法, 能够进一步降低查询时间.

3.4 基于用户权重的分组算法

虽然之前的方法可以通过IR-tree和Quad-tree将一部分主体对象过滤掉.然而, 当用户数量和提出的偏好对象重复数量很大时, 上面的算法性能将有所下降.在现实生活中, 如果一个度假村的经理想查询该度假村能够吸引哪些游客, 通常, 游客去度假村可能组团去, 这样, 同一个旅行团中的游客对周边设施可能有同样的偏好.所以, 本节提出一种用户的权重分组法来合并相似的偏好和权重, 以减少计算代价.

在给定所有用户的偏好后, 找出出现频率最高的前$\alpha $个辅助对象, 然后找到偏好包含这些辅助对象的所有用户.把这些用户给出的偏好按照权重大小分组.每种辅助对象被分为$\theta $组等间隔的组, 表示为$\left[ 0,\frac{1}{\theta } \right],\left[ \frac{1}{\theta },\frac{2}{\theta } \right],...,\left[ \frac{\theta -1}{\theta },1 \right],$那么一共存在${{\theta }^{\alpha }}$这样的分组, 表示为g_i注意, 没有任何偏好权重的分组不需要考虑.假设$L{{g}_{i}}$和$U{{g}_{i}}$分别表示每一组中每个区间的下界和上界.那么, 一个分组g_i如果满足以下条件才被认为是有效的: $\sum\nolimits_{m-1}^{\alpha }{L{{g}_{i}}(m)<1}$或者$\sum\nolimits_{m-1}^{\alpha }{U{{g}_{i}}(m)>1\,}.$进而可以找到每一个组与查询点q的关系.比较需要求解的所有主体对象所在cell与q的关系.由于每个对象分组都有上下界, 这样, 每个分组与查询点q的得分与其他主体对象所在cell的得分存在以下几种关系.

1) $Lrel(c,{{g}_{i}})$

当且仅当$\forall o\in c,\forall w\in {{g}_{i}},f(w,o)<f(w,q)$满足, 可以得到在g_i中所有的对象在偏好权重属于分组q中的得分都小于查询点q的得分, 这样, c中所有的对象被安全剪枝.

2) $Urel(c,{{g}_{i}})$

当且仅当$\forall o\in c,\forall w\in {{g}_{i}},f(w,o)>f(w,q)$满足, 可以得到在c中所有的对象在偏好权重属于分组g_i中的得分都大于查询点q的得分, 这样, c中所有的对象被放到结果集中, 并记录个数, 当个数大于k时, 算法终止; 当个数小于k时, 算法继续.

3) $Arel(c,{{g}_{i}})$

当且仅当$\forall o\in c,\exists w\in {{g}_{i}},f(w,o)\le f(w,q)\wedge \exists {w}'\in {{g}_{i}},f({w}',q)\le f({w}',o)$满足, 需要精确计算在c中所有的对象在偏好权重属于分组g_i中的得分.

4)若以上情况都不满足, 则需要划分节点c, 以进一步找出该节点c的子节点c'到分组g_i的得分.重复以上3个步骤, 直到结束.

具体地, 算法3给出了基于用户权重分组的流程.

算法3.基于用户权重分组算法.

1. Input: Q, ${{Q}_{{{g}_{i}}}},$$\mathbb{R}[{{g}_{i}}]\leftarrow \varnothing ,$${W}'\leftarrow \varnothing ;$     /*初始化队列Q, ${{Q}_{{{g}_{i}}}},$, 其中${{Q}_{{{g}_{i}}}},$表示在分组g_i中的队列, $\mathbb{R}[{{g}_{i}}]$记录q在每个分组g_i中的排名, W'记录结果的集合*/

2. Output: W';

3. for each valid g_i do     /*对每一个有效地分组进行处理*/

4.   enqueue(Q, Quad-tree.Root);

5.   while ($c=dequeue(Q)\ne \varnothing $) do

6.     if ($Lrel(c,{{g}_{i}})$) then    /* c中所有的对象被安全剪枝*/

7.       prune all objects in c;

8.     if ($Urel(c,{{g}_{i}})$) then      /* c中所有的对象的个数加到$\mathbb{R}[{{g}_{i}}]$中*/

9.        $|\mathbb{R}[{{g}_{i}}]|\leftarrow |\mathbb{R}[{{g}_{i}}]|+|c|$;

10.        if ($|\mathbb{R}[{{g}_{i}}]|<k$) then

11.         continue;

12.        else

13.          q is not a result in group g_i     /*查询对象Q不是组g_i中的结果*/

14.     if ($Arel(c,{{g}_{i}})$) then     /*计算在C中所有的对象在偏好权重属于分组g_i中的得分*/

15.       enqueue(${{Q}_{{{g}_{i}}}},c$);

16.     else

17.        for ($\forall {c}'$ is a child of c) do

18.          enqueue(${{Q}_{{{g}_{i}}}},{c}'$);

19.     ${W}'\leftarrow {W}'\bigcup \{{{w}_{i}}\};$     /*更新W' */

20.     if ($|\mathbb{R}[{{w}_{i}}]|<k$) then

21.       report q is a result in group g_i     /*查询对象q属于组g_i中的结果*/

22.     else

23.       q is not a result in group g_i     /*查询对象q不是组g_i中的结果*/

24.     ${W}'\leftarrow {W}'\bigcup \{{{g}_{i}}\};$

25.   return W';

4 讨论

本节总结以上所提出方法的时间代价和空间代价.在基本算法中, 最坏的情况是需要处理$|W|$top-k个查询, 所以基于R-tree的算法是一种蛮力搜索算法.然而, 基于R-tree的算法通过实验验证是少于$|W|$top-k个查询而返回正确结果.所以, 基于R-tree的算法的时间复杂度为$O({{n}_{R}}\cdot m),$空间复杂度为$O({{n}_{R}}),$其中, n是空间中对象的个数, m是用户的权重个数, n_R是R-tree中MBRs的数量.在批量计算主体对象的剪枝算法中, 由于把主体对象和辅助对象分别用不同的索引结构进行索引, 则该算法的时间复杂度为$O(({{n}_{c}}+{{{n}'}_{R}})\cdot m),$空间复杂度为$O({{n}_{c}}+{{{n}'}_{R}}).$其中, n_c表示主体对象在Quad-tree中cells的数量, ${{{n}'}_{R}}$表示辅助对象在IR-tree中MBRs的数量.在用户的权重分组中, 把对象提出的偏好按权重大小进行分组, 则算法的时间复杂度为$O(({{n}_{c}}+{{{n}'}_{R}})\cdot {{m}_{g}}),$空间复杂度为$O(({{n}_{c}}+{{{n}'}_{R}})+{{m}_{g}}),$其中m_g为分组的数量.

5 实验

本节将对以上提出的算法进行实验评估.所有实验都是基于Java语言进行, 实验环境采用Intel (R) Core (TM) i7-3770 CPU @3.40GHz和8GB内存.在每一组实验中, 查询1 000次, 每一次随机地选择一个不同的查询点, 最终求出平均值作为实验结果.

5.1 数据集及设置

在实验评估中使用两种类型的数据集, 包括空间对象数据集D和用户偏好权重数据集W.

空间对象数据集D.使用两个真实数据集进行评估.第1个数据集EURO.EURO是一个欧洲地区中包含有179 506个兴趣点的数据集.每一个兴趣点表示一个空间地理对象, 并且每一个对象都有其地理位置和标签(如, 公园、医院、超市等).第2个数据集FSQ.FSQ是一个从Foursquare中提取的数据集, 该数据集包含200万个带有空间地理位置和标签的兴趣点.

用户偏好权重数据集W.生成两个类型的数据集, UNI和CLU.UNI数据集是指生成的用户偏好权重是随机的均匀分布; CLU数据集通过两个参数来创建:r和s².首先随机生成r个独立的用户偏好权重, 把这r个偏好权重当作聚簇中心.然后围绕着聚簇中心生成方差为s²的一些偏好权重.并且根据实际情况选取每个权重集合中包含2个~4个不同的偏好权重, l默认值为20.由于真实数据集中兴趣点的种类数量很大, 为了检验数据更有效果, 实验从真实数据集中选取不同大小的|F|来验证所提出算法的有效性.

在实验中, 估计以下4种方法:(1)基于R-tree的剪枝算法, 简单记为RT.RT作为基础算法在第3.1节中被提出; (2)批量计算主体对象的剪枝算法, 表示为QIR; (3)改进的批量剪枝算法, 表示为MQIR; (4)基于分组处理用户权重, G-MQIR, 实验中也对算法G-MQIR-UNI和G-MQIR-CLU分别进行实验评估.

实验主要对为处理RSP-k查询而提出的算法的执行时间和I/O次数进行评估.由于本文算法是基于索引结构设计的, 算法执行时每对索引中的叶子节点进行一次访问, 就相当于进行一次I/O读取, 所以I/O次数即记录每次查询索引结构中叶子节点的访问次数, 并且叶节点的大小定义为4KB.实验中给出的参数变化为:结果数K为10~50, 用户偏好的数量$|W|$为5k~100k, 辅助对象标签数量$|F|$为100~500, 聚集中心个数$\rho $为5~50.默认值设置为:$k=10,|W|=10k,|F|=200,\rho =10.$其中, 为了验证辅助对象标签数量$|F|$的不同对实验效果的影响, 本文从真实数据集中的数据点的标签总数量中进行抽取并做比较.实验参数具体在表 1中给出.

5.2 实验评估结果 5.2.1 不同数据集对查询时间的影响

图 6对比了4种不同算法在数据集不同时, 运行时间的变化.从图 6中可以看出, 对于两个不同的真实数据集, 在不同算法的比较下, 算法G-MQIR-UNI和G-MQIR-CLU比其他算法查询时间要快.这说明提出的优化算法有一定的效果.在其他参数相同的情况下, FSQ比EURO的查询时间要长, 由于FSQ数据集中空间对象数量比EURO数据集的对象数量多, 那么即使选定了辅助对象的种类数量, FSQ的辅助对象的数量仍然要多于EURO数据集中的辅助对象数量, 所以, 在真实数据集FSQ上做查询, 查询时间要长于在数据集FSQ上做查询.

5.2.2 参数k对查询结果的影响

图 7对比了两个真实数据集在不同算法下的k值变化对查询结果的影响.查询结果分别从查询时间和I/O次数进行比较.从实验结果图中可以看出, 随着k的不断增大, 所有算法的查询时间和I/O次数也在增加.算法G-MQIR-UNI和G-MQIR-CLU比其他算法查询时间要快.其中, 算法G-MQIR-UNI并没有比算法MQIR在查询时间上快很多, 因为算法G-MQIR-UNI虽然对用户偏好权重进行了分组, 但是由于用户偏好权重是均匀分布的, 因此对分组后的用户偏好权重不能有效地进行合并计算.但是, 如果用户偏好权重按照聚集分布进行分组, 查询性能将有很明显的提升.对于I/O次数, 由于算法RT对辅助对象没有进行预处理, 在查询发布时进行在线计算, 虽然查询时间比较长, 但是I/O次数只存在于计算主体对象中.

5.2.3 用户偏好权重W对查询结果的影响

图 8表示的实验结果是当用户偏好的数量|W|从5k变化到100k时, 不同算法的查询性能比较.对于所有的算法, 随着用户偏好的数量|W|的增加, 查询时间越长, I/O次数越大.从实验结果可以看出, 算法G-MQIR-UNI和算法G-MQIR-CLU查询时间仍然是最快的, 因为对用户偏好进行分组可以有效地对相似用户偏好进行合并计算, 从而减少计算量.同样地, I/O次数也会随着优化算法剪枝的效果而随之减少.

5.2.4 辅助对象标签数量|F|对查询结果的影响

图 9展示了所有方法在辅助对象标签数量|F|从100变化到500时的查询时间和I/O次数的变化.从实验结果中可以明显地看出, 随着辅助对象标签数量|F|的增大, 用户偏好的种类也会随之增加, 这样, 在计算每个主体对象的得分时会产生更多的计算量, 查询时间也随之线性地增加.注意到, 算法G-MQIR-UNI在查询时间上并没有远远优于算法MQIR, 因为算法G-MQIR-UNI是把用户的偏好权重均匀地分布, 对于分组后的用户偏好权重不能有效地进行合并计算.

5.2.5 聚集中心个数ρ对查询性能的影响

图 10说明了聚集中心的个数选取的不同对查询时间的变化.实验在两个数据集上分别进行比较.从实验结果中可以看出, 对于采用聚集分布的用户偏好权重, 当聚集中心个数选取的是10个和20个时查询效果最好.因为当聚集中心个数选取得少时, 能够进行合并计算的权重数量也少, 所以查询效果不如聚集中心个数多时好; 如果聚集中心个数选取过多, 虽然可以在合并计算上大幅度减少计算量, 但是最后在进行精确求解时仍然需要一个个地计算, 从而使得查询效率降低.所以选择合适的聚集中心个数能够得到很好的查询效率.

5.2.6 分组个数θ和选取频繁偏好个数α对查询性能的影响

图 11说明了算法G-MQIR-CLU当分组个数θ变化时, 在不同数据集中查询性能的变化.从实验结果中可以看出, 当查询时间最小时, θ取值为4, 最小的分组个数和最大的分组个数都不是最优结果.这说明当分组个数小时, 算法不能达到最大程度的剪枝.同样地, 当分组个数θ增大时, 对于每一组都要进行计算, 反而增加了查询时间.

下面从图 12来解释算法G-MQIR-CLU在不同数据集中选取频繁偏好个数α对查询性能的影响.α的变化正如查询维度的增加, 从实验结果中可以看出, 随着α的增加, 运行时间不断增加.因为α变大, 用户偏好组的个数α也随之增大, 从而查询计算量也随之增大.另外, 从图中可以看出, 当α变化在3和4之间时, 反而运行时间平稳甚至有略微下降, 因为如果频繁偏好个数α选取适中, 那么保证分组的计算量和剩余用户偏好的计算量就可以达到平衡, 同时计算执行时间也随之有所下降.

6 结束语

本文研究反向空间偏好top-k查询, 是从空间对象角度出发并考虑主体对象与周围设施的位置关系的一种新型的反向top-k查询.本文提出3种剪枝算法来处理反向空间偏好top-k查询, 即基于R-tree的剪枝算法(RT)、批量计算主体对象的剪枝算法(QIR)和改进的批量剪枝算法(MQIR).其中, RT计算了很多不需要的主体对象与偏好对象的空间距离; QIR对RT进行了优化, 减少了不必要的计算; 最后, 对QIR进行改进, 提出了MQIR.另外, 为了更好地减少计算代价, 本文对用户提出的偏好权重进行分组, 使得拥有相似的用户权重能够同时处理.最后, 在真实数据集上给出实验结果, 可以证明所提出方法的有效性.