Quantized Indexing Tree for Frequent Updates over Data Streams

Emerging hardware and communication technologies enable new data stream applications that deal efficiently with very high rates of data updates. In this paper, we propose a novel index structure, termed the QDM-tree (quantized R*-tree with double memos), to support efficient similarity search over data streams. We integrate quantized minimum bounding spheres (QMBSs) and quantized minimum bounding rectangles (QMBRs) which can improve the cache behavior of QDM-tree due to effectively pack more entries in a node and reduce the tree height. Two compact main memory memos (Insert Memo and Delete Memo) can accelerate the speed of insert operations and convert the cost of update to the cost of insert. Therefore, the RamDisk technique reduces the cost of disk accesses to the cost of memory accesses. Theoretical analysis and experimental evaluation demonstrate that the QDM-tree significantly outperforms other state of the art R-tree variants with frequent updates, and is more suitable for massive data streams.