可伸缩的道路网络多连续k近邻查询处理

针对基于道路网络的多用户连续k近邻查询处理,提出了一种可伸缩的多用户连续查询处理(scalable processing of multiple continuous queries,SPMCQ)框架.SPMCQ框架采用流水线处理策略,将连续k近邻查询执行分解为可同时作业的预处理、查询执行和结果分发3个阶段,利用多线程技术提高查询处理的并行性.基于SPMCO框架,分别利用基于内存的哈希表和线性链表结构对移动对象位置和道路网络有向图模型进行存储和管理,提出了多连续k近邻查询处理SCkNN算法.实验结果表明,在处理多用户连续k近邻查询时,该算法性能优于目前的道路网络连续k近邻查询处理算法.     

多用户连续k近邻查询多线程处理技术研究

针对面向移动对象集的多用户连续k近邻查询处理,提出了基于多线程的多用户连续查询处理(MPMCQ)框架,采用流水线处理策略,将连续查询处理过程分解为可同时作业的查询预处理、查询执行以及查询结果分发三个执行阶段,利用多线程技术来提高多用户连续查询处理的并行性;基于MPMCQ框架和移动对象内存格网索引,提出了基于多线程的连续k近邻查询处理(MCkNN)算法。实验结果与分析表明,基于MPMCQ框架的MCkNN算法在多核平台上优于CPM、YPK-CNN等现有算法。     

面向多核多线程的移动对象连续K近邻查询

针对移动对象的多用户连续K近邻查询处理问题,结合多核多线程技术的发展,提出了一种基于多线程的两阶段多用户连续K近邻查询处理框架.将查询处理分为查询预处理阶段和查询执行阶段,分别执行数据更新任务和查询处理任务,每个阶段都设计了优化cache访问命中率,并利用多线程技术提高多用户连续查询处理并行性的方法及数据结构.提出了一...     

道路网络环境下的连续k近邻查询处理研究

针对基于道路网络的连续k近邻查询处理, 提出一种新的道路网络有向图模型, 分别利用基于内存的哈希表和线性链表结构对移动对象当前位置和道路网络有向图模型进行存储和管理.通过引入单向网络距离度量和双向网络距离度量, 提出单向网络扩展(UNE)算法和双向网络扩展(BNE)算法以支持不同语义的连续k近邻查询处理, 并采用影响树及网络扩展策略来减少连续k近邻查询更新的搜索代价. 实验结果表明, 上述两种算法性能优于目前的IMA和MKNN等连续k近邻查询处理算法.     

一种高效的移动对象连续多范围查询处理框架

针对连续多范围查询处理,结合多核多线程技术和大容量内存技术,通过将移动对象和查询放在内存中处理,提出了一种基于多线程的连续多范围查询处理框架.该框架基于多核处理器平台采用多线程技术周期性地处理查询和移动对象的更新,并周期性地计算多范围查询的结果.提出了基于移动对象数据均匀划分的多线程连续多范围查询处理算法,该算法以为查询建立的格网索引为基础.给出了该索引的构建思想和更新算法.考虑到基于内存的算法受Cache访问性能影响,提出了基于空间填充曲线的移动对象存储优化方法.实验证明,基于多核平台的多线程处理能够高效地处理连续多范围查询,同时通过移动对象存储优化能够提高算法运行中Cache访问命中率,进而提高算法性能.     

多元连接查询的并行执行

文中首先分析了传统的并行查询处理算法,然后针对面向对象数据库及其查询的特点,结合查询处理的分阶段执行策略,基于对象类的混合式数据放置策略和基于合格标记的数据操作并行执行算法,提出了基于ｓｅｍｉｊｏｉｎ的并行查询处理算法,对算法的正确性进行了证明,并给出了性能评价的结果。     

一种新的道路网络连续查询处理方法

基于道路网络的连续k近邻查询是移动对象数据库领域的研究重点和热点.提出了一种新的道路网络有向图模型,通过引入有向网络空间度量,利用基于内存的格网索引和线性链表结构来对移动对象当前位置和道路网络有向图模型进行存储和管理;基于有向距离度量提出了单向网络扩展(DNE)算法,以减少连续k近邻查询的网络扩展搜索代价.实验结果表明,DNE算法性能优于现有的连续k近邻查询处理算法.     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

基于半连接的并行查询处理算法的研究

多元连接查询的并行执行是并行数据库的研究重点,传统的并行查询处理算法没有利用面向对象数据库及其查询的特点,算法效率较低.借鉴分布式数据库查询处理中基于半连接的优化思想,提出了基于半连接的并行查询处理算法.性能评价表明了其实用性和有效性.     

基于Supersonic的并行分组聚集

针对在分析型联机分析处理(OLAP)应用中频繁出现的数据密集型操作符——分组聚集耗时较多的问题,提出Cache友好的分组聚集算法对该操作进行性能优化。首先,为充分发挥列存储在数据密集型计算方面的优势,采用基于开源的列存储查询执行引擎Supersonic,并在此之上设计Cache友好的分组聚集算法;其次,为加速查询的执行,使用并行技术,将单线程的分组聚集算法改为多线程并行的分组聚集算法。基于Supersonic设计并实现4种并行分组聚集算法:无共享Hash表并行分组聚集(NSHPGA)算法、表锁共享Hash表并行分组聚集(TLSHPGA)算法、桶锁共享Hash表并行分组聚集(BLSHPGA)算法、节点锁共享Hash表并行分组聚集(NLSHPGA)算法,且在不同的分组势集、不同的线程数的情况下,针对上述4种算法做了多组实验。通过对比3种不同粒度的共享Hash表并行分组聚集算法的加速比,得出NLSHPGA算法在加速比和并发度两方面表现最好,部分查询可达到10倍加速比;通过比较NSHPGA算法和NLSHPGA算法的加速比、Cache miss内存使用等情况,得出NLSHPGA算法在分组势集大于8时,加速比超过NSHPGA算法,并且Cache miss更低,使用的内存更少。