000190731 001__ 190731
000190731 005__ 20190316235747.0
000190731 037__ $$aREP_WORK
000190731 245__ $$aBLOCK: Efficient Execution of Spatial Range Queries in Main-Memory
000190731 269__ $$a2017
000190731 260__ $$c2017
000190731 336__ $$aReports
000190731 520__ $$aThe 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.
000190731 700__ $$0247657$$aOlma, Matthaios Alexandros$$g202810
000190731 700__ $$0243530$$aTauheed, Farhan$$g182656
000190731 700__ $$0243531$$aHeinis, Thomas$$g194694
000190731 700__ $$0243527$$aAilamaki, Anastasia$$g177957
000190731 8564_ $$s1417387$$uhttps://infoscience.epfl.ch/record/190731/files/a15-olma.pdf$$yn/a$$zn/a
000190731 909C0 $$0252224$$pDIAS$$xU11836
000190731 909CO $$ooai:infoscience.tind.io:190731$$pIC$$preport$$qGLOBAL_SET
000190731 917Z8 $$x194694
000190731 917Z8 $$x194694
000190731 917Z8 $$x148230
000190731 917Z8 $$x218212
000190731 937__ $$aEPFL-REPORT-190731
000190731 973__ $$aEPFL
000190731 980__ $$aREPORT