Tag Archives: spatial indexing


The development of TOUCH was co-funded by the HBP during the Ramp-up Phase. This page is kept for reference but will no longer be updated.

Efficient spatial joins are pivotal for many applications and particularly important for geographical information systems or for the simulation sciences where scientists work with spatial models. Past research has primarily focused on disk-based spatial joins; efficient in-memory approaches, however, are important for two reasons: a) main memory has grown so large that many datasets fit in it and b) the in-memory join is a very time-consuming part of all disk-based spatial joins. In this paper we develop TOUCH, a novel in-memory spatial join algorithm that uses hierarchical data-oriented space partitioning, thereby keeping both its memory footprint and the number of comparisons low. Our results show that TOUCH outperforms known in-memory spatial-join algorithms as well as in-memory implementations of disk-based join approaches. In particular, it has a one order of magnitude advantage over the memory-demanding state of the art in terms of number of comparisons (i.e., pairwise object comparisons), as well as execution time, while it is two orders of magnitude faster when compared to approaches with a similar memory footprint. Furthermore, TOUCH is more scalable than competing approaches as data density grows.

Date of release
Version of software
Version of documentation
Software available
DocumentationMore information: http://infoscience.epfl.ch/record/186338?ln=en
ResponsibleEPFL-DIAS: Darius Sidlauskas (darius.sidlauskas@epfl.ch) and Thomas Heinis (t.heinis@imperial.ac.uk)
Requirements & dependencies
Target system(s)Tested on Pico supercomputer (CINECA)


The development of FLAT was co-funded by the HBP during the Ramp-up Phase. This page is kept for reference but will no longer be updated.

FLAT is a spatial indexing tool, which enables scalable range queries on (3D) spatial datasets. Given the user input, which should be a query range, and the dataset to be queried, FLAT returns all the objects that intersect with the query range.

In particular, both the query ranges and the spatial objects should be represented using minimum bounding rectangle, which is the geometry approximation bounding the underlying spatial object.

FLAT outperforms the state-of-the-art spatial indexing techniques (e.g. R-trees, grid file) on extremely dense datasets.

Date of releaseMarch 2015
Version of software1.0
Version of documentation1.0
Software availableCollaboratory, integrated and part of BBP SDK tool set
ResponsibleEPFL-DIAS: Xuesong Lu (xuesong.lu@epfl.ch), Darius Sidlauskas (darius.sidlauskas@epfl.ch)
Requirements & dependenciesLinux, boost library, BBP SDK
Target system(s)PICO supercomputer