QDM-Tree:支持数据流频繁更新的Cache敏感索引

QDM-Tree:Cache Conscious Indexing for Frequent Updates over Data Streams

随着硬件和通信技术的飞速发展,数据流技术已广泛应用于金融分析、网络监控及传感器网络等诸多领域,这类应用通常具有高速、海量、连续和实时等特性.因此,在数据流上渐进、实时地更新索引成为一个极具价值和挑战性的问题.为了克服现有支持频繁更新的索引树性能大都深受处理器缓存失效率的影响,提出了一种新颖的基于双Memo的量化R*索引树-QDM-Tree(Quantized R*-tree with Double Memos),并给出了相应的插入、删除、更新和范围查询算法,理论分析表明:与已有R*树及其变种相比,该索引树能成倍地压缩树结点,具有更强支持频繁更新的能力.

Emerging hardware and communication technologies enable data stream techniques which have been applied in widespread fields such as financial analysis, network monitoring, and sensor network, etc. These applications generally have the characteristics high speed, massive quantity, continuous and real time. So, updating index in a progressive and real-time fashion becomes a meaningful and challenging problem on data strearo.s. To conquer the high cache miss ratio of existed index tree for frequent updates, this paper provides a novel O.DM-tree （Quantized R ＊ -tree with Double Memos）, and corresponding insert, delete, update and range query algorithms. Theoretical analysis demonstrates that the O.DM tree significantly outperforms other state of the art R-tree variants, it can compress the tree nodes to several times and more suitable for massive frequent updates.