Whenever possible we try to implement demonstrations of the algorithms we develop. What follows are demonstrations of FLAT, SCOUT and TOUCH, algorithms developed in collaboration with the neuroscientists of the Blue Brain Project (BBP). The videos below show the demos working on real neuroscience data, i.e., a small model of the rat brain’s neocortex, from the BBP.
FLAT: Extracting Subsets of Spatial Models
Spatial indexes like the R-Tree (and its variants) do not scale well with high density datasets like neuron models because of overlap and dead space in the tree structure. We have developed FLAT, a novel indexing algorithm that avoids overlap. It does so by first finding a random object within the query range (a cheap operation) and then recursively retrieving neighboring objects until all objects in the range are retrieved.
This video shows how on a small representation of the rat’s brain the range query can be defined and how the query is executed with FLAT. The query is executed on FLAT and on the R-Tree in parallel, showing that FLAT can indeed execute it substantially faster. Click here for a video.
FLAT on the iPad: Navigating through Spatial Models
We have also implemented FLAT on the iPad, making full use of the touch screen to define queries on a spatial representation of a neuron model. Given the vast amounts of data, the detailed model is kept on the server. The iPad, however, is used to define the query and to render a detailed visualization of the query result.
This video shows how the user can use gestures to define a spatial range query on a small representation of the rat’s brain. The query is then executed on FLAT and the detailed result is visualized on the iPad, enabling scientists to inspect and analyze it using the usual gestures. Click here to see a video of the demo.
SCOUT: Accurate Prefetching for Spatial Query Sequences
Scientists frequently use guided query sequences to interactively analyze spatial datsets. The guided query sequences typically follow a structure (e.g., a neuron branch) in the dataset. Prefetching along the query sequence effectively reduces response time, but state-of-the-art approaches do not predict future query locations accurately. SCOUT, our approach, identifies the structure being followed during query execution, prefetches along the identified structure accurately and consequently outperforms traditional prefetching techniques.
This video shows how SCOUT speeds up the execution of a guided query sequence on a spatial model of the rat’s brain. SCOUT identifies the structure the sequence follows, prefteches accurately along the query sequence and thereby speeds up query execution considerably. Click here for a video.
TOUCH: Efficient Spatial Joins in Main Memory
Efficient spatial joins are pivotal for many applications and for the simulation sciences where scientists work with spatial models, particularly for the neuroscientists in the BBP. We consequently develop TOUCH, a novel in-memory spatial join algorithm that uses hierarchical data-oriented space partitioning, thereby outperforming state-of-the-art methods by keeping both its memory footprint and the number of comparisons low.
This video shows the parallel execution of a spatial join with both TOUCH and PBSM (the fastest competitor) on a small model of the rat’s brain to find all intersecting neurons. Intersections are highlighted in a visualization of the brain as they are found by the join, showing that TOUCH considerably outperforms its fastest competitor. Click here to see a video of the demo.
