Ordered Indexing Methods for Data Streaming Applications

Abstract: Many data streaming applications need ordered indexing techniques in order to maintain statistics required to answer historical and continuous queries. Conventional DBMS indexing techniques are not specifically designed for data streaming applications; this motivates an investigation on comparing the scalability of different ordered indexing techniques in data streaming applications. This master thesis compares two ordered indexing techniques - tries and B-trees - with each other in the context of data streaming applications.Indexing data streams also requires supporting high insertion and deletion rates. Two deletion strategies, bulk deletion and incremental deletion, were also compared in this project. The Linear Road Benchmark, SCSQ-LR and Amos II were comprehensively used to perform the scalability comparisons and draw conclusions.