基于路径时间感知的发布/订阅技术研究

作     者：贾梦迪 

作者单位：苏州大学 

学位级别：硕士

导师姓名：郑凯

授予年度：2019年

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：基于路径 时间感知 发布/订阅 

摘      要：近些年来,随着智能移动设备和社交网络的蓬勃发展,海量带有地理标签的数据从移动互联网中产生。如何充分利用这些数据的优势并为用户提供准确的信息推送分发服务,成为了亟需解决的关键问题。发布/订阅技术作为提供信息推送分发服务的重要手段,受到了学术界和工业界的广泛关注。本文考虑现实应用场景,结合用户的移动行为,提出了基于路径时间感知的发布/订阅问题,为解决该问题使用了过滤-验证框架,并设计了高效的过滤算法。具体研究内容如下:(1)针对传统发布/订阅技术未曾考虑用户移动路径的问题,提出了基于路径时间感知的发布/订阅问题。该问题设计了参数化的订阅以满足用户复杂多样的需求,并且综合考虑了信息和订阅在时间、空间以及文本三个维度的相似性来为用户提供更准确的匹配结果。为解决该问题,设计了过滤-验证框架作为解决方案。(2)针对需要重复计算不同订阅路径产生的交集的问题,提出了基于位置时间感知的过滤算法。该过滤算法通过为每个空间元素建立基于位置时间感知的列表,并考虑空间和时间维度的信息设计剪枝策略并结合文本前缀过滤方法进行剪枝,有效解决了订阅路径的交集所带来的重复计算问题,从而提高效率。(3)为解决需对空间位置相近的订阅元素进行多次类似计算所导致的效率低下问题,提出了基于区域时间感知的过滤算法。该过滤算法通过将订阅元素按照空间位置划分为不同区域,并根据各个区域的空间和时间限制条件设计剪枝策略,另外还对文本前缀过滤方法进行优化,有效解决了空间分布带来的效率低下的问题。最后,分别通过实验分析了关键参数及数据规模对于本文所提出的两种过滤算法的剪枝能力和运行效率的影响,并分别与基准算法进行了实验对比,证明了本文所提出的过滤算法具有高效性及可扩展性。