The COST Benchmark: Comparison and Evaluation of Spatio-Temporal Indexes

Christian Søndergaard Jensen, Dalia Tiesyte, Nerius Tradisauskas

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


An infrastructure is emerging that enables the positioning of populations of on-line, mobile service users. In step with this, research in the management of moving objects has attracted substantial attention. In particular, quite a few proposals now exist for the indexing of moving objects, and more are underway. As a result, there is an increasing need for an independent benchmark for spatio-temporal indexes. This paper characterizes the spatio-temporal indexing problem and proposes a benchmark for the performance evaluation and comparison of spatio-temporal indexes. Notably, the benchmark takes into account that the available positions of the moving objects are inaccurate, an aspect largely ignored in previous indexing research. The concepts of data and query enlargement are introduced for addressing inaccuracy. As proof of concepts of the benchmark, the paper covers the application of the benchmark to three spatio-temporal indexes - the TPR-, TPR*-, and Bx-trees. Representative experimental results and consequent guidelines for the usage of these indexes are reported.
Original languageEnglish
Title of host publicationProceedings of the Eleventh International Conference on Database Systems for Advanced Applications
Number of pages16
Publication date2006
ISBN (Print)3540333371
Publication statusPublished - 2006
EventInternational Conference on Database Systems for Advanced Applications - Singapore, Singapore
Duration: 12 Apr 200615 Apr 2006
Conference number: 11


ConferenceInternational Conference on Database Systems for Advanced Applications
SeriesLecture Notes in Computer Science

Cite this