BLOCK: Efficient Execution of Spatial Range Queries in Main-Memory
File(s)BLOCK.pdf (1.62 MB)
Accepted version
Author(s)
Olma, Matthaios
Tauheed, Farhan
Heinis, Thomas
Ailamaki, Anastasia
Type
Conference Paper
Abstract
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.
Date Issued
2017
Date Acceptance
2017-06-01
Citation
Proceedings of the 29th International Conference on Scientific and Statistical Database Management, Chicago, IL, USA, June 27-29, 2017, 2017, pp.15:1-15:12
ISBN
978-1-4503-5282-6
Publisher
ACM
Start Page
15:1
End Page
15:12
Journal / Book Title
Proceedings of the 29th International Conference on Scientific and Statistical Database Management, Chicago, IL, USA, June 27-29, 2017
Copyright Statement
© 2017 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SSDBM '17 Proceedings of the 29th International Conference on Scientific and Statistical Database Management
Article No. 15
Article No. 15
Sponsor
Engineering & Physical Science Research Council (E
European Research Office
Identifier
http://doi.acm.org/10.1145/3085504
Grant Number
EP/N023242/1
720270
Source
SSDBM '17 Proceedings of the 29th International Conference on Scientific and Statistical Database Management
Publication Status
Published
Start Date
2017-06-27
Finish Date
2017-06-29
Coverage Spatial
Chicago
Date Publish Online
2017-06-27