Workload-Aware Indexing of Continuously Moving Objects

Kostas Tzoumas, Man Lung Yiu, Christian Søndergaard Jensen

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

25 Citations (Scopus)


The increased deployment of sensors and data communication networks yields data management workloads with update loads that are intense, skewed, and highly bursty. Query loads resulting from location-based services are expected to exhibit similar characteristics. In such environments, index structures can easily become performance bottlenecks. We address the need for indexing that is adaptive to the workload characteristics, called workload-aware, in order to cover the space in between maintaining an accurate index, and having no index at all. Our proposal, QU-Trade, extends R-tree type indexing and achieves workload-awareness by controlling the underlying index’s filtering quality. QU-Trade safely drops index updates, increasing the overlap in the index when the workload is update-intensive, and it restores the filtering capabilities of the index when the workload becomes query-intensive. This is done in a non-uniform way in space so that the quality of the index remains high in frequently queried regions, while it deteriorates in frequently updated regions. The adaptation occurs online, without the need for a learning phase. We apply QU-Trade to the R-tree and the TPR-tree, and we offer analytical and empirical studies. In the presence of substantial workload skew, QU-Trade can achieve index update costs close to zero and can also achieve virtually the same query cost as the underlying index.
Original languageEnglish
Title of host publicationProceedings of the VLDB Endowment
Number of pages12
PublisherAssociation for Computing Machinery
Publication date2009
Publication statusPublished - 2009
EventInternational Conference on Very Large Databases - Lyon, France
Duration: 24 Aug 200928 Aug 2009
Conference number: 35


ConferenceInternational Conference on Very Large Databases

Fingerprint Dive into the research topics of 'Workload-Aware Indexing of Continuously Moving Objects'. Together they form a unique fingerprint.

Cite this