基于混合处理模型的乱序数据流分布式聚合查询处理技术

为了解决现有的乱序数据流聚合查询处理技术不能在降低查询处理延迟,同时保障聚合查询结果的最终正确性的局限性问题,本研究设计了混合嵌入分布式流处理模块和分布式批处理模块的乱序数据流分布式聚合查询处理技术。该技术一方面基于用户给定的结果质量,限制自适应地优化流处理模块所用的缓冲区大小,从而尽可能降低流处理的查询处理延迟;另一方面基于备份于分布式数据存储系统的历史流数据,并以批处理的方式实现对极其晚到流元组的查询处理,从而保障聚合查询结果的最终正确性。基于真实的乱序数据流数据集对该技术进行测试分析表明:该技术在平均查询处理时延、查询结果精度和系统可扩展性方面,比目前最好的基于缓存的乱序数据流处理技术均具有显著优势。     

QJoin：质量驱动的乱序数据流连接处理技术

数据流乱序现象会导致数据流处理结果的丢失,给数据流的分析处理带来了巨大困难。本研究探讨了质量驱动下的乱序数据流连接处理问题,提出一种质量驱动的乱序数据流连接处理技术(QJoin)。QJoin采用缓冲存储技术和对称连接策略,实现并确保对流元组进行即时分析处理,从而降低了流元组处理的平均等待时间。同时,基于质量驱动的理念,根据临近阶段连接处理过程中收集统计的数据,自适应地调整和优化内存缓存区的大小,从而在满足用户结果质量要求的前提下,降低系统内部历史数据的内存缓存量,尽可能保证迟到元组的连接处理完整性。真实数据集上的实验结果表明,与传统的数据流乱序处理技术MP-K-slack相比,QJoin在满足用户结果质量要求的前提下,确保能够即时地分析处理数据流的流元组,显著降低系统的内存开销。     

面向社交数据流连续查询的基准评测

社交数据流上的连续查询处理具有广泛的应用,但其处理技术仍不成熟.本文对社交数据流上的连续查询问题进行建模,定义数据特征、负载类型与分布,以及性能测度.在此基础上,提出一个面向该问题的基准评测.该工作对社交数据流处理应用的系统选型、相关查询处理技术性能比较具有重要意义.     

一种面向连续查询的虚拟轨迹隐私保护方法

随着全球移动定位设备的普及和网络通信技术的发展,催生出基于位置服务的应用(LBS)。享受LBS带来的便利服务的同时,用户的位置轨迹隐私保护受到严峻考验。现有的位置隐私保护方法大多针对用户单次查询设计,不能适用于连续查询;且匿名效果不佳。提出了一种采用中心服务器结构的假轨迹匿名方案,通过持续选择匿名区域内长时间所在的移动用户生成假位置点,构成虚拟轨迹的方式来混淆攻击者的判断,从而达到保护用户轨迹隐私的目的。仿真实验结果表明方法有效可行。     

连续近邻查询方法的研究

连续近邻查询(CNN)是时空数据库中一种重要的查询类型。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文利用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。     

数据流连续查询处理技术的研究

数据流查询处理技术的研究是目前数据库研究领域的热点问题.传统的数据库技术不能处理诸如网络监测、传感器网络、股票分析等应用中所生成的新型数据,即数据流.数据流作为一种新的数据形态,不同于传统的静态数据,具有连续快速、短暂易逝、规模宏大和不可预测的特点;其研究核心是在一个远小于数据规模的有限存储空间迅速获得近似查询结果.综述关于数据流查询处理技术的研究成果,主要介绍数据流模型、查询的特征、数据流近似查询操作算法的实现以及数据流系统中的查询处理方法.     

一种基于果蝇优化方法的连续查询攻击算法

针对位置信息服务的隐私保护轨迹安全隐患,在已有研究的基础上提出了一种新的连续查询攻击算法(Continuous Queries Attacking algorithms based on Fruit Fly,CQAFF).首先该算法结合熵和查询匿名度量定义了查询识别率的计算模型,并利用果蝇优化方法给出了模型的求解流程.最后,利用移动对象数据生成器来进行实验,深入研究了影响CQAFF算法的关键因素,同时对比分析了该算法与其它算法的性能差异,结果表明CQAFF算法的有效性.     

缓存模式下的轮廓查询优化方法

研究在缓存模式下,利用一组预存储的临时轮廓快照集来高效等价重构用户新提交的轮廓查询Q,并提出一种新颖的缓存模式下轮廓查询处理算法(APSQCM)来完成该任务.APSQCM算法由两阶段组成,第一阶段捕获Q与缓存中临时轮廓快照间的内在关联,进而获取能够用来等价重构Q的所有轮廓基;而在第二阶段中,APSQCM算法使用轮廓基来快速产生Q的正确结果集.实验结果表明,APSQCM算法具有有效性和实用性.     

一种基于变窗口的数据流连续查询方法

目前对数据流连续查询的研究工作大部分基于滑动窗口,窗口大小固定不变.本文从内存资源有限性与查询结果精确性角度出发,采用可变窗口技术,在缓存中加入窗口控制器,当数据到达缓存时,根据用户提出查询具体问题和数据流速情况,窗口分配算子对其进行窗口大小的划分.使得在内存资源有限的情况下,通过动态改变滑动窗口大小,充分利用系统资源,降低内存使用率的同时,使连续查询的查询结果都在允许的误差范围内,此方法经过验证是可行的.     

共享连接结果的连续查询处理

深入研究了适合数据流连续查询处理的Shared PushDown,PullUp和Filtered PullUp三种可共享连接结果的策略.通过理论分析和实验证明,在数据流的连续查询处理中,PullUp策略性能较低,而Filtered PullUp和Shared PushDown策略各占优势.Filtered PullUp处理简单,消耗内存相对较少.而Shared PushDown增加内存使用,但在注册查询的选择因子覆盖较少时有一定优势.考虑到处理的方便,一般情况下Filtered PullUp是适合数据流连续查询处理的最佳方案.     

公路网上移动对象连续k近邻查询的一种方法

公路网上移动对象连续k近邻查询是最近时空数据库查询中的一个研究热点,它是在一个时间段内找到离查询点最近的K个移动对象.我们分析了现有查询方法,存在的问题主要是运动对象位置随时间而频繁变化以至于不能及时更新运动对象的信息而导致返回KNN结果不正确.为了解决这些问题,采用一种距离预计算方法,使计算量减少,从而为更新通讯获得更多时间.通过实验证明,我们提出的方法是有效的.     

一种并发高效的连续时空查询处理算法

分析了SINA在查询结果上的完整性,发现和解决了其在消极更新结果完整性上的一点不足.为了进一步提高SINA的查询效率,将并发机制引入递增计算算法中,并给出了实施并发控制的策略及其在结果正确性上的证明.实验表明,并发运行后的算法,随着时空数据集的增大,查询计算的平均时间有了明显下降,内存和CPU的利用率有了明显提高.     

一种面向空间数据的聚集查询处理方法

提出一种新的面向空间数据的聚集查询处理方法。该方法扩展了AMH和AMH*方法,首先将整个空间栅格化,再将若干频数接近的邻居栅格组合成遵循一定约束条件的桶。随着数据分布变化,各桶不断重组或者拆分,具有空间复杂度低、查询精度高等特点。理论分析与实验结果均表明新方法优于现有方法。     

一种基于流的XML查询算法设计与实现

针对密集型数据查询要消耗大量内存的缺陷,设计了一种基于流的XM L文档查询算法.该算法在对XM L流的一次单向读取过程中处理XPath,接收查询表达式,将表达式转换为树形自动机,自动机以流的方式接收并处理XM L文档,同时输出当前处理结果.在查询树状态转换过程中附加了缓存操作,用于保存XM L流中暂时无法判断的文档片段.算法测试表明其占用内存空间基本恒定,不会随被查询文档的增大而增加.     

基于路网的连续K最近邻查询

连续K最近邻(CKNN)查询是最近邻查询的扩展,可广泛地应用于地理信息系统、城市规划、智能交通等领域.CKNN查询搜索某一路径上所有点的K个最近的感兴趣对象.本文研究基于交通路网的连续K最近邻查询问题,不同于传统的基于欧式空间的CKNN查询,基于路网的CKNN查询中对象间的距离度量不再是欧式距离,而是基于路网的最短可达距离.显然,传统的基于欧式距离的CKNN查询算法并不能直接应用于基于路网的CKNN查询问题.本文提出了一种基于路网的高效的CKNN查询算法-IIE算法,广泛实验表明本文提出的IIE算法优于传统的IE算法.     

位置服务中连续查询隐私保护的动态规划算法

针对基于位置服务中连续查询可能存在的隐私泄露问题,提出基于历史轨迹的连续查询隐私保护匿名算法.首先针对传统基于贪心策略的两条轨迹匿名算法无法保证全局最小轨迹扭曲度的不足,设计出可保证全局最优的两条轨迹匿名动态规划算法,找出历史轨迹与连续查询所对应的基轨迹之间的最优配对方案;然后在此基础上提出可有效保护连续查询隐私的轨迹匿名算法.对本文算法与同类算法在发布轨迹数据质量上进行实验比较分析,仿真实验结果表明本文算法是有效可行的.     

基于对象方向方位的连续方向查询算法

连续的方向查询返回一个拓扑集合,传统的方法无法计算出连续的方向变化,基于这种情况,介绍了一种利用索引结构TPR树来处理基于对象方向方位的连续方向查询算法,通过扩展时间参数化窗口查询技术,提高传送效率来减少I/O和CPU的设备开销。最后通过实验数据表明利用OSS策略进行连续的方向关系查询的I/O性能明显优于重复查询方法的性能。     

圆周连续自映射可嵌入半流的一些结果

本文讨论了圆周连续自映射嵌入半流的问题,得到了圆周连续自映射可嵌入半流的两个充分条件。     

基于LBS的连续查询位置隐私保护模型的动态规划算法

针对现有的算法大多都是静态位置隐私保护的,如果将静态算法应用于动态的连续查询中,会导致位置隐私泄露,提出了一种基于连续查询的动态规划改进算法,旨在保护用户的位置隐私,仿真实验结果证明:该算法在匿名处理时间、匿名成功率和轨迹扭曲度等方面优于现有算法.