2009 | OriginalPaper | Buchkapitel
Indexing Moving Objects Using Short-Lived Throwaway Indexes
verfasst von : Jens Dittrich, Lukas Blunschi, Marcos Antonio Vaz Salles
Erschienen in: Advances in Spatial and Temporal Databases
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach we do
not
require a sophisticated index structure that needs to be adjusted for each incoming update. Rather we construct conceptually simple
short-lived throwaway indexes
which we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique
MOVIES
supports at the same time high query rates
and
high update rates and trades this for query result staleness. Moreover,
MOVIES
is the first main memory method supporting time-parameterized predictive queries. To support this feature we present two algorithms: non-predictive
MOVIES
and predictive
MOVIES
. We obtain the surprising result that a predictive indexing approach — considered state-of-the-art in an external-memory scenario — does not scale well in a main memory environment. In fact our results show that
MOVIES
outperforms state-of-the-art moving object indexes like a main-memory adapted B
x
-tree by orders of magnitude w.r.t. update rates and query rates. Finally, our experimental evaluation uses a workload unmatched by any previous work. We index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second which is unmatched by any previous work.