Scalable ordered indexing of streaming data
Sobhan Badiozamany, Tore Risch · 2012
In order to efficiently answer continuous queries requiring range search in large stream windows, data stream management systems (DSMSs) need ordered indexes. Conventional DBMS indexing methods are not specifically designed for data streaming applications with extremely high insert and delete rates for windows over streams. This motivates a scalability investigation for various ordered main memory indexing methods in a streaming environment, through implementation and experiments. Our experimental studies show that a state-of-the-art implementation of cache-aware compact tries is a very suitable indexing structure for data streaming applications allowing constant time insert and access rates. However, in the best of the investigated implementation the range search was slow. Since a highly optimized implementation of compact tries is very complex we developed a framework for scalable range search in an index without any change to its source code. Another important issue is that index maintenance in window based data stream environments require a scalable way of deleting data, which is addressed by an index independent window aware bulk deletion technique, also without changing any source code. 1.