TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning

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.

Conception et évaluation d'un prototype de simulation de la morphogenèse urbaine par agents vecteurs multi-échelles

Vitor Silva

The research work of this PhD thesis was carried out in the context of an interdisciplinary project related to the study of urban morphogenesis. A team composed of architects and engineers specialized in GIS technologies have worked together in this project during three years, sharing their knowledge in order to understand and simulate the evolution of the urban environment of cities. The fundamental hypothesis that conducted this research is that the city can be seen as a self-organizing system governed by a set of morphogenesis rules, which can for example, determine the location of new architectural programs and induce the city's organization, from local to global scales. Architectural programs themselves are supposed to determine city's development. In this PhD thesis a simulation prototype of the urban growth based on the use of multi-agents systems was carried out. This prototype is a computer tool that allows the analysis and representation of the growth of the built environment. Nowadays, the ability to understand and simulate urban evolution proves to be essential in order to control the evolution of a city in a sustainable development view. Furthermore, this tool should facilitate the understanding and decision-making of those concerned with problems related to urban development. The urban system has been modeled as a set of space objects, such as buildings and networks, which interact between themselves. These interactions are carried out at different levels, from local to global scales, being controlled by behavioral rules or laws of growth. The result of their interaction can be figures or emergent phenomena represented at several scales. The approach using multi-agents vector systems was chosen in order to model a geographical complex system like a city, which integrates a vectorial modeling of space. Hence, each spatial agent does not possess a limit of form and size. The interest of using multi-agents vector systems also lies in their ability to manage various models of individuals, from simple entities to more complex ones. Thus, various levels of representation, such as individuals and groups of individuals, can be managed, which is not easily feasible, for example, with cellular agents. The development platform used is GeOxygene (Java computer programming language), which is an open-source platform developed at IGN (Institut Géographique National, France), by COGIT laboratory. This platform provides several GIS functions, allowing the development and implementation of the prototype here presented. An interaction model between agents was defined and the type of scenarios of each of these interactions was detailed. A set of methods and associated classes was developed. Agent's architecture was conceived in order to allow manipulation (sending, receiving and treatment) of exchanged messages. In order to show the relevance of the multi-agent multi-scale methodology, examples of buildings creation in a case study zone were carried out. Using the multi-scale vector simulation prototype here presented, the development of cities can be computed in a very innovative way. However, the developed prototype still lacks some accuracy, mostly due to the fact that the specified laws adopted for simulation do not reflect the whole reality, which is obviously much more complex to traduce. We have not yet validated the model for other cities – nevertheless, the model could already be used as a decision support tool, particularly as a planning support instrument for architects and urban planners. With regards to future work this prototype shall be integrated in a global approach of urban simulation, allowing the analysis of environmental risks, demographic and economic growth and transports simulation at different scales of analysis and 2D/3D visualization output, such as district and city.

EPFL2010

Data-driven Neuroscience: Enabling Breakthroughs Via Innovative Data Management

Anastasia Ailamaki, Thomas Heinis, Mirjana Pavlovic, Alexandros Stougiannis, Farhan Tauheed

Scientists in all disciplines increasingly rely on simulations to develop a better understanding of the subject they are studying. For example the neuroscientists we collaborate with in the Blue Brain project have started to simulate the brain on a supercomputer. The level of detail of their models is unprecedented as they model details on the subcellular level (e.g., the neurotransmitter). This level of detail, however, also leads to a true data deluge and the neuroscientists have only few tools to efficiently analyze the data. This demonstration showcases three innovative spatial management solutions that have substantial impact on computational neuroscience and other disciplines in that they allow to build, analyze and simulate bigger and more detailed models. More particularly, we visualize the novel query execution strategy of FLAT, an index for the scalable and efficient execution of range queries on increasingly detailed spatial models. FLAT is used to build and analyze models of the brain. We furthermore demonstrate how SCOUT uses previous query results to prefetch spatial data with high accuracy and therefore speeds up the analysis of spatial models. We finally also demonstrate TOUCH, a novel in-memory spatial join, that speeds up the model building process.

2013

Enabling Scientific Discovery Via Innovative Spatial Data Management

Anastasia Ailamaki, Thomas Heinis, Mirjana Pavlovic, Farhan Tauheed

Researchers in several scientific disciplines are struggling to cope with the masses of data resulting from either increasingly precise instruments or from simulation runs on ever more powerful supercomputers. Efficiently managing this deluge of data has become key to understand the phenomena they are studying. Scientists in the simulation sciences, for example, build increasingly big and detailed models, as detailed as the hardware allows, but they lack the efficient technology to update and analyze them. In this paper we discuss how innovative data management techniques we have developed, enable scientists to build and analyze bigger and more detailed spatial models and how these techniques ultimately accelerate discovery in the simulation sciences. These include spatial join methods (in memory and on disk), techniques for the efficient navigation in detailed meshes, an index for range query execution on complex and detailed spatial data as well as in-memory mesh indexes. The evaluation of these techniques using real neuroscience datasets shows a considerable performance improvement over the state of the art, and that the indexes we proposed scale substantially better for the purpose of the analysis of bigger and denser spatial models.

2013

Conception et évaluation d'un prototype de simulation de la morphogenèse urbaine par agents vecteurs multi-échelles

Vitor Silva

EPFL2010