Workload-Aware Indexing of Continuously Moving Objects

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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

25 Citationer (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.
TitelProceedings of the VLDB Endowment
Antal sider12
ForlagAssociation for Computing Machinery
StatusUdgivet - 2009
BegivenhedInternational Conference on Very Large Databases - Lyon, Frankrig
Varighed: 24 aug. 200928 aug. 2009
Konferencens nummer: 35


KonferenceInternational Conference on Very Large Databases

Bibliografisk note

Udgivelsesdato: August 2009
Volumne: 2
ISSN: 2150-8097

Fingeraftryk Dyk ned i forskningsemnerne om 'Workload-Aware Indexing of Continuously Moving Objects'. Sammen danner de et unikt fingeraftryk.