BLOCK: Efficient Execution of Spatial Range Queries in Main-Memory

The execution of spatial range queries is at the core of many applications, particularly in the simulation sciences but also in many other domains. Although main memory in desktop and supercomputers alike has grown considerably in recent years, most spatial indexes supporting the efficient execution of range queries are still only optimized for disk access (minimizing disk page reads). Recent research has primarily focused on the optimization of known disk-based approaches for memory (through cache alignment etc.) but has not fundamentally revisited index structures for memory. In this paper we develop BLOCK, a novel approach to execute range queries on spatial data featuring volumetric objects in main memory. Our approach is built on the key insight that in-memory approaches need to be optimized to reduce the number of intersection tests (between objects and query but also in the index structure). Our experimental results show that BLOCK outperforms known in-memory indexes as well as in-memory implementations of disk-based spatial indexes up to a factor of 7. The experiments show that it is more scalable than competing approaches as the data sets become denser.

Published in:
SSDBM '17 Proceedings of the 29th International Conference on Scientific and Statistical Database Management, 1-12
Presented at:
29th International Conference on Scientific and Statistical Database Management, Chicago, Illinois, USA, June 27-29, 2017
Jun 27 2017
New York, NY, USA, ACM New York, NY, USA
Other identifiers:

Note: The status of this file is: EPFL only

 Record created 2018-09-12, last modified 2019-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)