位置感知订阅/发布系统的top-k订阅查询匹配方法

摘要

本发明提出一种位置感知订阅/发布系统的top-k订阅查询匹配方法，其包括以下步骤：根据订阅的空间点信息建立R-tree；提取每个订阅中的谓词和该谓词的权重；将谓词载入到R-tree中不同层中的不同节点上得到RRt-tree；根据给定的事件e在RRt-tree中遍历各个订阅进行谓词匹配，根据谓词匹配结果得到订阅的候选集；计算出订阅的候选集中各个订阅与事件e的相似性函数值；将订阅候选集中的订阅按照相似性函数值的大小进行降序排列作为上界队列，并输出前k个订阅作为top-k订阅查询匹配结果。本发明将Rt-tree索引结构和一个谓词索引结构结合起来，并采用一个订阅分区策略。当一个事件到达时，可以快速的检索出他的top-k个匹配最好的订阅。

说明书

技术领域

本发明属于订阅查询匹配方法，特别涉及一种位置感知订阅/发布系统的top-k订阅查 询匹配方法。

背景技术

移动互联网飞速发展和带有GPS功能的智能手机的普及使得位置感知的订阅/发布系 统越来越多地受到了研究人员的关注。大量的带有地理位置标签的信息不断地在很多应用 中产生。例如，在一些社交网络应用中，如Facebook，Twitter，这些应用中含有大量的用 户。他们的个人信息可被描述为一系列属性值对，并可与GPS揭示的地理位置信息相结合 成为带有地理位置信息标签的属性值对。在线上支付线下消费的应用中，有很多用户不断 地在浏览产品，这些产品也可以被描述为一系列属性值对并与地理位置信息想结合。在本 文中，我们将这样的数据信息称为‘带有地理位置信息标签的属性值对’。

在一个基于位置敏感的订阅发布系统当中，订阅者订阅他们的兴趣，同时发布者发布 具有地理位置信息的事件。这种系统在现实世界得到很多应用。在位置感知的广告定向投 放系统当中，广告商是订阅者，他们可以声明一些用户属性作为订阅。比如，(“16<age<28， hobby∈{Tennis，basketball}”，“51.165145”，“0.141123”)。社交网络应用中用户的个人 信息比如年龄、爱好和地理位置可以作为一个事件，比如，(e.g.“age＝20，sex＝female， hobby＝tennis，school＝Harvard”，“51.256543”，“0.145845”)。如果有个事件和订阅高度相 关，那么相应的广告将会被展示在用户的屏幕上。这种广告推送模型对于线上支付线下消 费商业模式也有用处，比如Groupon，Groupon的商家和服务提供者可作为订阅者，这些 订阅者可能想更精确地投送广告给他们的潜在客户，他们可以同时声明用户的个人信息和 一系列的产品信息作为订阅，比如(e.g.，“hobby＝smart-phone，item∈{IPhone6s，IPhone5s}， 299$<price<499$”，“51.25543”，“0.145845”)。该系统的用户是信息发布者。当一个用 户点击一个产品链接时，这条产品信息和用户属性可以作为一个事件，例如(e.g. “hobby＝smart-phone，item＝iphone6s”，price＝469$，“51.32454”，“0.146382”)。在这些 应用中，由于屏幕尺寸的限制，只有一小部分广告可以被展示在用户屏幕上。

当前的非结构化订阅/发布系统可以很好的支持由带有地理位置信息的文本描述的 订阅，然而，这种系统不能支持需要结构化描述的带有地理位置信息的属性值对。当前的 位置感知的结构化订阅/发布系统，采用布尔表达式代表一个订阅，可以高效地检索出所 有匹配的信息，但是用户有可能被信息淹没。

发明内容

为了解决这个问题，我们提出了一个新型的带有布尔表达式的top-k订阅查询匹配。 最近的关于带有布尔表达式的top-k订阅查询匹配工作是处理部分匹配，而本文提出的是 严格的布尔表达式的全部匹配。

该问题有两大挑战，一，怎样从数百万带有多种属性和值的订阅中选出top-k个订 阅查询匹配的候选集。二，我们需要从大量候选集当中选出top-k个匹配最好的订阅。因 此，我们需要一个有效并且高效的解决方案来处理该问题。

本发明的技术方案是：

一种位置感知订阅/发布系统的top-k订阅查询匹配方法，其包括以下步骤：

(1)根据订阅的空间点信息建立R-tree；

(2)提取每个订阅中的谓词和该谓词的权重；

(3)将步骤(2)中谓词载入到R-tree中不同层中的不同节点上得到RR^t-tree；

(4)根据给定的事件e在RR^t-tree中遍历各个订阅进行谓词匹配，根据谓词匹配结 果得到订阅的候选集；

(5)计算出步骤(4)中的订阅的候选集中各个订阅与事件e的相似性函数值；

(6)将订阅候选集中的订阅按照相似性函数值的大小进行降序排列作为上界队列， 并输出前k个订阅作为top-k订阅查询匹配结果。

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，步骤(3) 中)将步骤(2)中谓词载入到R-tree中不同层中的不同节点上得到RR^t-tree的过程为：

步骤(1)中的R-tree的高度是给定一个订阅s，其谓词的个数为

If将s中剩余个谓词载入其叶子结点；

If只有前层的祖先结点包含s中的谓词；

令p_i表示s中第i个谓词，那么p_i将被载入在第i层的祖先结点上，对于第i层中的 每个结点n都有一个谓词集合P。

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，为P设计一 个谓词索引，包括：

第一步，按照谓词的属性将其分成若干个不相交的谓词列表，如下公式：

对于列表中的每个谓词，为统计已匹配的谓词个数，均设有一个指针指向其相 应订阅的M[s]；

第二步，列表中的谓词被进一步根据他们的操作符划分为相应的值列表如 下所示：

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，步骤(4) 谓词匹配的过程为：

为所有订阅设置一个哈希图，并初始化相应的哈希值为0；

当P中的一个谓词被匹配后，我们将其相应的哈希值增加1；

给定一个事件e和一个在第i层的结点n，如果s不可能是e的一个top-k订 阅的候选集；

给定一个事件e和一个在第i层的结点n，如果s一定是e的一个top-k订 阅的候选集；

给定一个事件e和一个在第i层的结点n，如果并且n是一个叶子结点， 那么s一定是e的一个top-k订阅的候选集。

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，把订阅按照 关键属性分成个订阅列表，并用RR^t-tree索引这些列表中的订阅；

给定一个订阅集合,我们根据关键属性δA.将其分区并用RR^t-tree对其进行索引，如 下所示：

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，相似性函数 值的计算包括：

对于一个给定的事件e和RR^t-tree中的一个结点n,布尔表达式相似性函数 UB_BE(e,n)计算公式如下：

${\mathrm{UB}}_{BE}(e,n)=Max\{\forall s\in n.parent[{\Sigma }_1^{i-1}({\omega }_{si}·{\omega }_{ej})+{{\omega }_{emax}}^{*}·(1-{\Sigma }_1^{i-1}{\omega }_{si})\left]\right\}---\left(4\right)$

这里是指出现在1到i-1层中属于s的所有已匹配的谓词的得分，另外 ω_emax*e中尚未匹配的属性值对的最大权重，是s中尚未匹配的谓词权重之和；

对于一个给定的事件e和RR^t-tree中的一个结点n,空间相似性函数UB_BE(e,n)计算 公式如下：

$UBs(e,n)=1-\frac{MinDist(e.loc,n.MBR)}{MaxDist}---\left(5\right)$

MaxDist订阅之间最大的距离，n.MBR是n所确定的最小边界矩形， MinDist(e.loc,n.MBR)是e.loc和n.MBR的最小距离；

对于一个给定的事件e和RR^t-tree中的一个结点n,最终的相似性函数UB(e,n)计算 公式如下：

$UB(e,n)=max\{\forall \alpha \in (n.a_{min},n.a_{max})min[1-\alpha ,{\mathrm{UB}}_{BE}(e,n)]+\alpha ·UBs(e,n)\}---\left(6\right)$

这里n.a_min,和n.a_max是结点n中订阅里最大的阿尔法值和最小的阿尔法值；

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，给定一个事 件e和一个订阅s,其相似性函数计算公式如下：

这里是布尔表达式相似性函数，是空间相似性函数。布尔表达式相似性函数计 算公式如下：

这里表示订阅s中谓词的个数。

空间相似性函数的计算公式如下：

这里dist(e.loc,s.loc)是e和s的欧式距离，MaxDist是订阅之间的最大距离；

给定一个事件e和一个包含一个订阅集合Sⁿ的结点n，对于任意sSⁿ，

优选的是，所述的位置感知订阅/发布系统的top-k订阅查询匹配方法中，如下情况 时停止查询：

1)当k订阅被找到并且它的最小相似性得分大于上界队列中的最大上界UB(e,n)。

2)当上界队列为空时。

本发明提出一种位置感知订阅/发布系统的top-k订阅查询匹配方法，其包括以下步骤： (1)根据订阅的空间点信息建立R-tree；(2)提取每个订阅中的谓词和该谓词的权重；(3) 将步骤(2)中谓词载入到R-tree中不同层中的不同节点上得到RR^t-tree；(4)根据给定的 事件e在RR^t-tree中遍历各个订阅进行谓词匹配，根据谓词匹配结果得到订阅的候选集； (5)计算出步骤(4)中的订阅的候选集中各个订阅与事件e的相似性函数值；(6)将订 阅候选集中的订阅按照相似性函数值的大小进行降序排列作为上界队列，并输出前k个订 阅作为top-k订阅查询匹配结果。本发明将R^t-tree索引结构和一个谓词索引结构结合起 来，并采用一个订阅分区策略。当一个事件到达时，可以快速的检索出他的top-k个匹配 最好的订阅。

本发明的其它优点、目标和特征将部分通过下面的说明体现，部分还将通过对本发明 的研究和实践而为本领域的技术人员所理解。

附图说明

图1是本发明位置感知订阅/发布系统的top-k订阅查询匹配方法的一个实施例中的订 阅和事件的列表图；

图2是图1中10个订阅和一个事件的在一个给定区域的地理位置分布图；

图3是本发明位置感知订阅/发布系统的top-k订阅查询匹配方法中的RR^t-tree的索引 结构图；

图4是本发明位置感知订阅/发布系统的top-k订阅查询匹配方法中的谓词索引结构；

图5是图1中10个订阅的RR^t-tree的索引结构图；

图6是本发明位置感知订阅/发布系统的top-k订阅查询匹配方法中的订阅查询计算过 程。

具体实施方式

下面结合附图对本发明做进一步的详细说明，以令本领域技术人员参照说明书文字能 够据以实施。

应当理解，本文所使用的诸如“具有”、“包含”以及“包括”术语并不配出一个或多 个其它元件或其组合的存在或添加。

我们首先把现存结构化的订阅/发布索引Opindex与R-tree空间索引树结合，其主要 思想就是将R-tree叶子节点上的订阅以Opindex索引起来，在检索出在布尔表达式上完全 匹配的订阅的同时，对这些订阅进行排序从而选出top-k个结果。由于叶子节点的区域可 能很小，所以造成该方法在空间维度的剪枝能力上效率低下。因此，该方法效率并不高。 为了提升效率，我们提出一个RR^t-trees的方法，该方法将R^t-tree索引结构和一个谓词索 引结构结合起来，并采用一个订阅分区策略。当一个事件到达时，该方法可以快速的检索 出他的top-k个匹配最好的订阅。

带有布尔表达式的位置感知订阅/发布系统的Top-k订阅查询匹配问题定义

订阅：订阅者注册他们的兴趣作为订阅，一个订阅s由一个三元组构成s.B,s.loc,α

s.B是一个描述订阅者兴趣的布尔表达式，s.loc是一个订阅的空间位置，α是一个用 来平衡空间维度相似性和布尔表达式维度相似性的一个参数。一个布尔表达式是由一些列 谓词的合取形式构成。一个谓词是一个用户给定的属性和值之间的限制，它有三部分构成， 一个属性A,一个操作符f_op，一个值v。因此p(A,f_op,v)表示一个谓词p。操作符可以 是关系操作符(e.g.,<,≤,>,≥,＝,≠)也可以是集合操作符每一个谓词都有一个权重 s，满足${\Sigma }_{i=0}^n{\omega }_{si}=\mathrm{1..}$

因此，一个订阅可以被如下描述：

s:{(<p₁,ω₁>∧<p₂,ω₂>∧<p_i,ω_i>∧….∧<p_n,ω_n>),loc,α}

事件：一个事件e包括一组属性值对和一个地理位置信息，分别由e.V和e.loc表示.属 性值对e.V由一些列谓词以合取形式构成。因此,υ(A,v)表示一个属性值对.每个属性值对 都有一个权重，满足，因此，事件可被定义成如下形式。

权重s表示用户对于订阅中各个谓词的偏好程度并由用户给。权重e表示属性值对 和谓词的相关程度，它是根据属性值对在整个数据集中的出现频率给定的。

定义1：谓词匹配

给定一个属性值对υ和一个谓词p，如果p.A＝υ.A并且p(A,f_op,v)＝true，那么我们 说谓词p匹配属性值对。

定义2：布尔表达式匹配

一个值对集合e.V匹配一个布尔表达式s.B当且仅当s.B里的每一个谓词均与e.V 中的属性值对匹配。

定义3：相似性函数

给定一个事件e和一个订阅s,其相似性函数定义如下：

这里是布尔表达式相似性函数，是空间相似性函数。布尔表达式相似性函数定 义如下：

这里表示订阅s中谓词的个数。空间相似性函数定义如下：

这里dist(e.loc,s.loc)e和s的欧式距离andMaxDist是订阅之间的最大距离。

如图1所示，对于事件e＝{[A＝3(0.1)ΛB＝3(0.5)ΛC＝4(0.2)ΛF＝2(0.2)],e.loc,α}， 根据定义2，订阅S₁匹配e。然而，订阅S₄不匹配e因为其谓词G≥4不匹配任何e中的 属性值对。根据定义3_,空间相似度is0.35，布尔表达式相似度is0.25。因 此，最终的平衡后的相似度is0.30。类似地，由于空间相似度is0.15，布 尔表达式相似度is0.18，所以总的相似度因此如果我们想检索出 top-1个订阅，那么答案是S1。

初步的解决方案

我们将现存的R-tree空间索引和Op-index结合起来初步解决本问题。Op-index是一 个著名的结构化，采用了布尔表达式的订阅/发布系统的索。其主要思想是根据关键属性¹对 订阅建立倒排并采用了一个两层分区策略来处理高维度属性个数的订阅/发布系统。我们 可以将Op-index和R-tree结合起来(称为OPR-tree)来处理本问题。我们首先根据订阅 的地理位置信息建立R-tree。之后我们以Op-index将处于叶子节点的订阅索引起来。本索 引结构的搭建和查询过程我们将详细描述。

OPR-tree搭建过程:对于每一个订阅s我们找到其叶子节点并将其关键属性A提取 出来。之后我们将叶子节点的订阅根据关键属性建立若干个列表。该列表由(n,A)表示。 每一个列表可以被进一步根据操作符(e.g.,<,≤,>,≥,＝,≠)划分为子列表。该子列表由(n, A,op)表示。对于(n,A,op)中的每一个谓词，我们采用一个哈希函数h(p.A)来确定的签名字 段来定位谓。根据h(p.A)我们在签名字段选取相应的，并将其置为1。除此之外我们还设 置了一个计数数组来跟踪已经匹配的谓词的个数。

OPR-tree查询过程：对于一个事件e，我们在R-tree上检索出其叶子节点n。之后 我们提取出事件e中所有的属性υi.A(υi∈e.V)如果 υi.A确实是一个关键属性。订阅中的每一个属性在整个数据集里都有一个出现频率 ，一个订阅中出现频率最小的那个属性就是该订阅的关键属性那么我们便用e中的属性值 对υi来查询(n,A)。对于每一个υi,我们先计算其哈希值h(υi.A).之后跟去该哈希值在定 位签名字段中的位,如果该位被置为1。我们遍查询相应谓词列表(n,A,op).之后 如果pj(υi.v)＝true,那么该谓词的布尔表达式相似性可以被计算。如果全部谓词都 得到匹，我们计算出它的空间相似性得分因此，最终的相似性被计算出来 并加入top-k订阅匹配的候选集。给定一个事件e,和一个叶子节点n,e相对于叶子结点n 的相似性上届由两者见距离的相似性和该事件e中最大权重而确定。

OPR-tree根据R-tree的叶子结点来分区。然而,叶子结点的区域可能会很小，这将导 致系在空间剪枝能力上的大大减弱。因此,OPR-tree并不十分高效.为了解决这个问题，我 们提出了RR^t-trees的解决方案。

三、RR^t-trees解决方案

1.RR^t-tree索引结构

R^t-tree是一个著名的非结构化订阅/发布系统的解决方案。根据R^t-tree,w我们提出了 一个方法RR^t-tree。RR^t-tree的主要思想是将R^t-tree解决方案中的关键字转化成本问题中订 阅里的谓词。这些谓词将被载入在其订阅落在的叶子节点的祖先节点。之后，我们采用一 个谓词索引结构对所有结点上的谓词进行索引。

RR^t-treeconstruction:我们根据订阅的空间点信息建立R-tree。对于一个给定的订阅 s，我们首先提取出它所有独立的谓词p_i，包括其权重。之后，我们将谓词p_i载入到R-tree 中不同层中的不同结点当中。

给定一个建立好的R-tree,它的高度是给定一个订阅s其谓词的个数为If 我们直接将s中剩余个谓词载入其叶子结点。If只有前层的祖 先结点包含s中的谓词。令p_i表示s中第i个谓词，那么p_i将被载入在第i层的祖先结点 上。对于第i层中的每个结点n,都有一个谓词集合P在其中。我们根据P中的谓词的属性 建立若干个到排文件，具有相同属性的谓词被聚集在一块。为了在事件查询中跟踪订阅s 已匹配的谓词个数，我们为所有订阅设置了一个哈希图，并初始化相应的哈希值 为0。当P中的一个谓词被匹配后，我们将其相应的哈希值增加1。根据我们可以高效地检索出top-k订阅的候选集。作为解释，我们有如下引理。

引理1：给定一个事件e和一个在第i层的结点n，如果那么s不可能是e 的一个top-k订阅的候选集。

引理2：给定一个事件e和一个在第i层的结点n，如果那么s一定是e 的一个top-k订阅的候选集。

引理3：给定一个事件e和一个在第i层的结点n，如果并且n是一个 叶子结点，那么s一定是e的一个top-k订阅的候选集。

谓词索引结构:

在RR^t-tree的每一个结点上,都有一个谓词集合P，以及这些谓词的权重，还有,最大、 最小的阿尔法值max、α_min。为了高效地检索P中匹配的谓词，我们为P设计了一个谓词索 引。

我们分两步索引P中的谓词，第一步，我们按照谓词的属性将其分成若干个不相交的 谓词列表，如下所示。

对于列表中的每个谓词,为统计已匹配的谓词个数，均设有一个指针指向其相应 订阅的M[s]。

第二步，列表中的谓词被进一步根据他们的操作符划分为相应的值列表如 下所示：

基于图1的10组订阅，图3展示了RR^t-tree的索引结构，图4展示了P₃的谓词索引 结构。

2.RR^t-treesindexstructure

由于订阅的数量个能很大，提高RR^t-tree的查询效率是必要的。为了解决该问题，我 们把订阅按照关键属性分成个订阅列表。并用RR^t-tree索引这些列表中的订阅。我们将 这种索引方案成为RR^t-trees。给定一个订阅集合,我们根据关键属性δA_.将其分区并用 RR^t-tree对其进行索引，如下所示：

有定义1和定义2，我们可以做出如下结论：如果一个事件e匹配一个订阅s,那么s 中所有的属性都出现在e中。明显地,如果s中有一个属性不在e中出现。e不可能匹配s。 因此，给定一个事件e,我们只考虑那些关键属性出现在e中的订阅。

RR-trees的索引结构如图4所示。根据上文提及的选取关键属性的规则，A,D,E，G分 别被选为关键属性。给定一个图1中的事件e，列表L_(E)和L_(G)中的订阅不可能匹配。

3SimilarityUpperBoundofR^t-treeBasedSolutions

在描述完RR^t-treeandRR^t-trees索引结构后,现在我们给出其相似性上届。

定义4.UB_BE(e,n):对于一个给定的事件e和RR^t-tree中的一个结点n,布尔表达式 相似性函数UB_BE(e,n)定义如下：

${\mathrm{UB}}_{BE}(e,n)=Max\{\forall s\in n.parent[{\Sigma }_1^{i-1}({\omega }_{si}·{\omega }_{ej})+{{\omega }_{emax}}^{*}·(1-{\Sigma }_1^{i-1}{\omega }_{si})\left]\right\}---\left(5\right)$

这里是指出现在1到i-1层中属于s的所有已匹配的谓词的得分。另外 ω_emax*e中尚未匹配的属性值对的最大权重。是s中尚未匹配的谓词权重之和。

定义5.UBs(e,n):对于一个给定的事件e和RR^t-tree中的一个结点n,空间相似性 函数UB_BE(e,n)定义如下：

$UBs(e,n)=1-\frac{MinDist(e.loc,n.MBR)}{MaxDist}$

这里MaxDist订阅之间最大的距离，n.MBR是n所确定的最小边界矩形， MinDist(e.loc,n.MBR)e.loc和n.MBR的最小距离。

定义6.UB(e,n):

根据定义4和定义5，对于一个给定的事件e和RR^t-tree中的一个结点n,最终的 相似性函数UB(e,n)定义如下：

$UB(e,n)=max\{\forall \alpha \in (n.a_{min},n.a_{max})min[1-\alpha ,{\mathrm{UB}}_{BE}(e,n)]+\alpha ·UBs(e,n)\}$

这里n.a_min,和n.a_max是结点n中订阅里最大的阿尔法值和最小的阿尔法值。

根据定义6，我们有如下引理：

引理5：

给定一个事件e和一个包含一个订阅集合Sⁿ结点n,对于任意的sSⁿ,都有：

四、查询算法

查询算法入图6所示，我们采用一个上界队列来存储尚未访问的结点。这些结点根据 他们的相似性上界UB(e,n)进行降序排列，对于根结点，其上界为1。给定一个事件e，我 们从根结点遍历所有的RR^t-trees中的RR^t-tree_(vi.A),这里vi∈e。该算法将会返回top-k 匹配最好的订阅的候选集。它将会在如下情况下终止：

1)当k订阅被找到并且它的最小相似性得分大于上界队列中的最大上界UB(e,n)。

2)当上界队列为空时。

尽管本发明的实施方案已公开如上，但其并不仅仅限于说明书和实施方式中所列运用， 它完全可以被适用于各种适合本发明的领域，对于熟悉本领域的人员而言，可容易地实现 另外的修改，因此在不背离权利要求及等同范围所限定的一般概念下，本发明并不限于特 定的细节和这里示出与描述的图例。