Towards small-effort adaptions to off-the-shelf spatial and temporal indexes for modern database applications

© 2012 Martin James StradlingModern database applications demand high throughput of queries on complex data, such as the increasingly common types of spatial and temporal data. Many structures have been proposed for indexing spatial and temporal data and as standalone implementations they often achieve high levels of performance. However they are generally difficult to implement in an existing DBMS, which makes them very expensive to adopt. For example, Oracle took more than 5 years to implement the R-tree spatial index structure in their commercial DBMS. This thesis examines the techniques that exist in off-the-shelf spatial and temporal indexes with an emphasis on achieving large performance gains with minimal changes. In the domain of spatial data we propose a new index structure called Size Separation Indexing (SSI). This structure builds on the B+-tree, which is present in almost all DBMSs. Through extensive experimentation we show that SSI performs at least as well as all current spatial indexes and better than most on both a flat filesystem and on top of a DBMS. In the domain of temporal data we extend the TSB-tree, which is also based on the B+ -tree. In recent work the TSB-tree has been integrated into Microsoft SQL Server and we introduce the memory Hierarchy-aware Version tree which significantly improves on the performance of the TSB-tree for almost all query types and is scalable to huge datasets. Because our structures build upon existing indexes, we argue that they are better suited for implementation in current systems than other structures, reducing costs and increasing performance