caa a22 4500 44533195X CHVBK 20180317142740.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s10707-011-0122-y doi (NATIONALLICENCE)springer-10.1007/s10707-011-0122-y MOVIES: indexing moving objects by shooting index images [Elektronische Daten] [Jens Dittrich, Lukas Blunschi, Marcos Vaz Salles] 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 index images that 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, trading this property 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 such as a main-memory adapted Bx-tree by orders of magnitude w.r.t.update rates and query rates. In our experimental evaluation, 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, a scenario at a scale unmatched by any previous work. Springer Science+Business Media, LLC, 2011 Moving objects nationallicence Indexing nationallicence Differential indexing nationallicence Large update rates nationallicence Spatial indexing nationallicence High dimensional indexing nationallicence Dittrich Jens Information Systems Group, Saarland University, Saarbrücken, Germany aut Blunschi Lukas Systems Group, ETH Zurich, Zürich, Switzerland aut Vaz Salles Marcos Department of Computer Science, Cornell University, Ithaca, NY, USA aut GeoInformatica Springer US; http://www.springer-ny.com 15/4(2011-10-01), 727-767 1384-6175 15:4<727 2011 15 10707 https://doi.org/10.1007/s10707-011-0122-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10707-011-0122-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dittrich Jens Information Systems Group, Saarland University, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Blunschi Lukas Systems Group, ETH Zurich, Zürich, Switzerland aut NATIONALLICENCE 700 1- Vaz Salles Marcos Department of Computer Science, Cornell University, Ithaca, NY, USA aut NATIONALLICENCE 773 0- GeoInformatica Springer US; http://www.springer-ny.com 15/4(2011-10-01), 727-767 1384-6175 15:4<727 2011 15 10707 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer