Range query (database) | EPFL Graph Search

A range query is a common database operation that retrieves all records where some value is between an upper and lower boundary. For example, list all employees with 3 to 5 years' experience. Range queries are unusual because it is not generally known in advance how many entries a range query will return, or if it will return any at all. Many other queries, such as the top ten most senior employees, or the newest employee, can be done more efficiently because there is an upper bound to the number of results they will return. A query that returns exactly one result is sometimes called a singleton. Partial match query Match at least one of the requested keys. *B+ tree

k-d tree
R-tree

See also

Range searching

Computational Neuroscience Breakthroughs Through Innovative Data Management

Anastasia Ailamaki, Laurynas Biveinis, Thomas Heinis, Sadegh Heyrani Nobari, Farhan Tauheed

Simulations have become key in many scientific disciplines to better understand natural phenomena. Neuroscientists, for example, build and simulate increasingly fine grained models (including subcellular details, e.g., neurotransmitter) of the neocortex to understand the mechanisms causing brain diseases and to test new treatments in-silico. The sheer size and, more importantly, the level of detail of their models challenges today's spatial data management techniques. In collaboration with the Blue Brain project (BBP) we develop new approaches that efficiently enable analysis, navigation and discovery in spatial models of the brain. More precisely, we develop an index for the scalable and efficient execution of spatial range queries supporting model building and analysis. Furthermore, we enable navigational access to the brain models, i.e., the execution of of series of range queries where he location of each query depends on the previous ones. To efficiently support navigational access, we develop a method that uses previous query results to prefetch spatial data with high accuracy and therefore speeds up navigation. Finally, to enable discovery based on the range queries, we conceive a novel in-memory spatial join. The methods we develop considerably outperform the state of the art, but more importantly, they enable the neuroscientists to scale to building, simulating and analyzing massively bigger and more detailed brain models.

2013

Accelerating Spatial Range Queries

Anastasia Ailamaki, Thomas Heinis, Alexandros Stougiannis, Farhan Tauheed

It is increasingly common for domain scientists to use computational tools to build and simulate spatial models of the phenomena they are studying. The spatial models they build are more and more detailed as well as dense and are consequently difficult to manage with today's tools. A crucial problem when analyzing spatial models of increasing detail is the scalable execution of range queries. State-of-the-art approaches like the R-Tree perform suboptimally on today's models and do not scale for more dense, future models. The problem is that the amount of overlap in the tree structure increases as a function of the level of detail/density in the model. In this demonstration we showcase ZOOM, a new tool to efficiently execute spatial range queries on increasingly detailed (denser) models. ZOOM is based on FLAT, a novel range query execution approach that effectively decouples the query execution time from the density of the dataset, thereby ensuring efficient query execution. At the core of the demonstration thus is the visualization of the novel query execution strategy of FLAT which we contrast with a visualization of the query execution of the R-Tree.

2013

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