Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing

Download PDF

Abstract

Although several spatial indexes achieve fast query processing, they are ineffective for highly dynamic data sets because of costly updates. On the other hand, simple structures that enable efficient updates are slow for spatial queries. In this paper, we propose Waffle, a workload-aware, query-sensitive spatial index, that effectively accommodates both update-and query-intensive workloads. Waffle combines concepts of the space and data partitioning frameworks, and constitutes a complete indexing solution. In addition to query processing algorithms, it includes: (i) a novel bulk loading method that guarantees optimal disk page utilization on static data, (ii) algorithms for dynamic updates that guarantee zero overlapping of nodes, and (iii) a maintenance mechanism that adjusts the trade-off between query and update speed, based on the workload and query distribution. An extensive experimental evaluation confirms the superiority of Waffle against state of the art space and data partitioning indexes on update and query efficiency.