一种基于谓词区分和关联的快速订阅与匹配方法

摘要

本发明提出的一种基于谓词区分和关联的快速订阅与匹配方法，对等值谓词和区间谓词的划分，使得谓词的组织结构更易于修改，增加了谓词插入删除的效率。同时过滤了大量不符合条件的匹配信息，使得匹配桶更加精简，从而减少了遍历匹配桶的时间提高了匹配效率。通过提高匹配效率，增加节点的交互能力，从而增加虚拟现实的仿真场景的实时性，使得街道上的人物与车辆更加真实。本方法兼顾了处理订购和事件匹配的效率，能够有效地解决对称事件匹配问题，从而使基于内容的发布/订购模型能较好地应用于分布式虚拟环境。

说明书

技术领域

本发明涉及一种基于谓词区分和关联的快速订阅与匹配方法。

背景技术

在虚拟现实场景的模拟中，如果我们要模拟条街道的环境，在场景中的每一辆汽 车，每一个人作为仿真节点都将出现在仿真场景中，而仿真场景中每一个节点之间都 会有相互交互的数据，因此节点交互的发布订阅系统中将会有大量的数据来处理。在 处理大量数据时，系统的实时性将会受到很大的影响。这种情况下，我们需要设计一 种方法，能增加各个节点的匹配效率，从而增加其实时性。

在现有的事件匹配方法中，陈继明等人提出了基于内容的快速事件匹配方法一种 适合分布式虚拟环境的快速事件匹配方法（CEEM,content-based effective event  matching algorithm）。CEEM匹配方法在性能上的优势主要体现在以下2个方面：1)动 态性，即该方法不需要像现有的匹配方法，如基于匹配网络的方法需构造静态的匹配 网络，可以实现动态的更新订购信息；2)高效性，即该方法采用以谓词表为核心的数 据结构，利用谓词间的关联性和属性间的相关性来加快匹配速度；同时对谓词族进行 了划分，并对每个谓词族用排序或者散列表的方式进行了索引，使得在对每个谓词进 行匹配时能获得很高的效率。相对于其他方法，CEEM方法更加适应于订购数目众多、 并拥有较多谓词数目的分布式虚拟环境的应用。该方法利用了谓词间的关联性和属性 间的相关性，加快了匹配的速度，使基于谓词索引和基于匹配网络方法各自的优点都 能得到体现，同时又尽量避免了它们的不足。另外，该方法同时还实现了现有其他方 法无法解决的事件匹配的对称性问题。CEEM方法主要的匹配空间需求是谓词表，在 实现时只需采用二维数组的形式，且所有的订购共用同一个谓词表，可避免相同订购 谓词重复记录，减少了存储空间。因此，当分布式虚拟环境中大量的虚拟对象频繁地 向系统发送订购和发布信息时，CEEM方法能够有效解决匹配树方法面临的因路由器 存储空间需求快速增加而导致的“内存危机”问题，不会对系统的运行效率产生造成较 大影响。但该方法的谓词组织结构是将等值谓词和区间谓词不做区分，匹配时在匹配 桶中会做大量的遍历，同时还会因匹配桶结构过于庞大而导致谓词组织结构修改困难， 从而影响了效率。而K.R.Jayaram等人在文献Split and Subsume——Subscription  Normalization for Effective Content-based Messaging中提出的方法将谓词的组织结构 做到了散列谓词和区间谓词的区分，但在匹配过程中没有将谓词的散列和区间相结合， 从而也影响了匹配的效率。

上述两种方法各有利弊，基于内容的快速事件匹配方法中谓词组织结构复杂，匹 配桶数据繁多，匹配结构中插入和删除谓词时动态改变组织结构过于繁琐；文献Split  and Subsume中提出的方法在匹配过程中由于区分了谓词属性而在匹配过程中没有结 合，从而导致了匹配过程部分重复而导致效率降低。

发明内容

要解决的技术问题

为了避免现有技术的不足之处，本发明提出一种基于谓词区分和关联的快速订阅 与匹配方法，在谓词的组织结构和匹配的方式两个方面做了修改，从而降低了匹配结 构的复杂程度，提高了谓词匹配的效率。

技术方案

一种基于谓词区分和关联的快速订阅与匹配方法，其特征在于步骤如下：

步骤1、事件的订购处理：在初始化时由于尚没有订购，谓词集合和订购列表均 为空，接口列表也只是对应当前接口；当接收到新的订购后，需要对谓词表、接口列 表和订购列表分别进行更新，分为以下4步：

1）新的订购到来时，抽取订购的属性，按照偏序的关系插入到先决集合中；

2）分解订购条件，根据每一条订购条件的类型分别建立该属性的哈希列表或区间树；

3）根据订购条件数目确定订购的属性值，订购的初始计数器值为0；

4）将订购映射到每一属性对应的哈希列表或区间树中；

步骤2、事件的匹配，步骤如下：

1）事件到来时，首先抽取事件的属性，在先决集中查找该属性集的位置，如果该属性 集有子结点，匹配策略为：每处理完一个属性的谓词，便对匹配桶中的所有订购执行 计数器自增操作，然后检测匹配桶中的订购是否已达到要求，属性值与计数器值相等； 如果该属性集没有子结点或者先决集中不存在该属性集，匹配策略为：处理完一个属 性的谓词后，该属性集的订购没有子订购，直接对匹配桶的存在的订阅进行下一个属 性的谓词的检测，在匹配桶中淘汰不符合条件的订阅，直到事件的所有属性全部检测 完毕，最后匹配桶中剩余的订阅就是符合条件的订阅；

2）分解事件的谓词，先在哈希列表中找到对应该谓词属性的列表，在该列表中找到该 谓词的值的条目，将该条目对应的所有订购加入到匹配桶中；然后在区间森林中找到 对应该谓词属性的区间树，在该区间树中定位到该值对应的节点，将该节点所对应的 所有订购加入到匹配桶中；

3）如果符合发布要求，则向该订购发布该事件；由于匹配桶的集合特性，当试图加入 桶中已存在的订购时，会加入失败，因此之前加入的同一条订购会再次执行计数器自 增操作；

4）当事件的所有谓词处理完成时，对匹配桶的所有订购进行重置计数器操作并将匹配 桶清空以备下一次使用。

有益效果

本发明提出的一种基于谓词区分和关联的快速订阅与匹配方法，对等值谓词和区 间谓词的划分，使得谓词的组织结构更易于修改，增加了谓词插入删除的效率。同时 过滤了大量不符合条件的匹配信息，使得匹配桶更加精简，从而减少了遍历匹配桶的 时间提高了匹配效率。通过提高匹配效率，增加节点的交互能力，从而增加虚拟现实 的仿真场景的实时性，使得街道上的人物与车辆更加真实。本方法兼顾了处理订购和 事件匹配的效率，能够有效地解决对称事件匹配问题，从而使基于内容的发布/订购模 型能较好地应用于分布式虚拟环境。

附图说明

图1为数据结构图

图2为基于谓词区分和关联的快速订阅与匹配方法实例图

图3为插入新订购时的实例图

图4为订阅流程图

图5为匹配步骤3流程图

图6为匹配步骤4流程图

具体实施方式

现结合实施例、附图对本发明作进一步描述：

在分布式虚拟环境应用中，事件匹配过程是将描述虚拟对象的特征及其状态的事 件发布信息和描述虚拟对象兴趣范围的订购信息进行逻辑判定并转发的过程。由于虚 拟环境中对象订购和发布的信息较为复杂（不仅包括对象的位置信息以及自身特点， 还包括对象的预感区域及兴趣区域等），通常由多个谓词采用逻辑与的关系组成，订 购与发布信息间的匹配其本质上是谓词间的一种匹配运算。

所用数据结构：

偏序先决集：偏序先决集维护属性的之间的相关关系。由于某些订购的属性关系 是固定的，如果第一条属性不满足，则没有必要继续匹配下去，造成不必要的操作， 因此构造偏序先决集来维护属性间的相关关系。当新的订购到来时，首先将该订阅条 件的属性加入到先决集中。先决集按照偏序的关系组织数据。当事件到来时首先通过 先决集的判断来决定采取哪种匹配策略。

谓词集合：谓词集合是数据结构的核心部分，基于谓词的类型分为两部分，其中 等值谓词“=”对应哈希列表，上阈值谓词“<”和下阈值谓词“>”对应区间树。每一属性对 应一列表和一颗区间树，具有相同属性和相同操作的谓词归入同一个哈希列表或区间 树。同一订购映射到其所有的谓词，哈希列表映射到列表中的条目，区间树映射到结 点。多个区间哈希列表构成列表集合，多个区间树构成区间森林。列表集合和区间森 林共同维护订购谓词集合。

匹配桶：用于匹配时存储暂时符合若干条件的订购。由于匹配是根据到来事件的 值逐条进行的。有些订购达到了部分条件，但还没有完全达到可以发送的条件，便暂 时存储到匹配桶中，防止匹配信息的丢失。匹配桶是一set的结构，即只允许加入不 同的订购，当执行加入匹配桶中已存在的订购时，该执行失败。

接口列表和订购列表：订购列表登记了所有加入谓词表的订购，每一条订购映射 到它所有的订购条件，同时维护一个value值和一个count值，value值代表该订购到 达发送条件的订购数，count值代表匹配时以符合的条件数，当count与value值相等 时便达到发送条件。接口代表了事件的传送方向，是事件匹配的最终目的。每个接口 仅对应一个连接（订购者或事件路由节点）的订购信息，每个连接可以有多个订购， 通过订购列表和接口列表将所有的订购组织在一起。

为使本发明的目的、技术方案和优点更加清楚，下面结合实例对本发明作进一步 的详细描述：

初始状态：目前有两个属性，其中X为等值属性，Y为区间属性。

目前有如下订购：

Suber1:f{17<=Y<=19;X=5}

Suber2:f{8<=Y<=9;X=6}

Suber3:f{X=11}

Suber4:f{6<=Y<=10}

Poset先决集如下：

Myset谓词集如下：

插入新的订购：假设新的订购的过滤器如下Suber5:f{25<=Y<=30;X=24}， Suber6:f{A=1;B=1}

Poset先决集如下：

Myset谓词集见图2；

事件匹配:

1）事件如下e{Y=8;X=6}

首先检测先决集，发现{Y，X}的结点并非叶子结点，所以采取第一种匹配方式， 首先检查Y，将与Y匹配的订阅加入到匹配桶中，并将其count+1

匹配桶

Suber2-count=1,value=2 Suber4-count=1==value=1

此时Suber4的count值与value值已相等，故将Suber4加入到结果集中

接下来检查X，将X=6对应的订阅者Suber2加入到匹配桶中，但此时发现匹配 桶中已经有Suber2了，那么将Suber2的count值+1，此时Suber2的count值与value 值相等，故将Suber2加入到结果集中，匹配结束

匹配桶

1）事件如下e{A=1;B=2}

首先检测先决集，发现{A，B}的结点是叶子结点，所以采取第二种匹配方式， 首先检查A，将与A匹配的订阅加入到匹配桶中，并将其count+1

匹配桶

接下来检测匹配桶中的订阅者是否匹配B=2，发现并不匹配，故将Suber2于匹配 桶中移除，此时匹配桶为空，匹配结束，结果为空。

方法性能分析：

假设属性数目为A，订购数为S。

空间复杂度：方法的空间复杂度主要是谓词集合的空间需求。每条订购最多由A个谓 词组成，在谓词表的谓词数是SA，即总的空间复杂度是O(AS)。

事件订购的复杂度：哈希插入的复杂度为O(1)，区间树插入的复杂度为O(logN)，因此 综合复杂度为O(A((logN+1))==O(logN）。

事件匹配的复杂度：哈希查找的复杂度为O(1)，区间树查找的复杂度为O(logN)， 因此综合复杂度为O(A((logN+1))==O(logN）。