Abstract BBoxDB Streams is a distributed stream processing system, which allows the handling of multi-dimensional data. Multi-dimensional streams consist of n-dimensional elements, such as position data (e.g., two-dimensional positions of cars or three-dimensional positions of aircraft). The software is an enhancement of BBoxDB, a distributed key-bounding-box-value store that allows the handling of n-dimensional big data. BBoxDB Streams supports continuous range queries and continuous spatial joins; n-dimensional point and non-point data are supported. Operations in BBoxDB Streams are performed primarily on the bounding boxes of the data. With user-defined filters (UDFs), custom data formats can be decoded, and the bounding box-based operations are refined (e.g., a UDF decodes and performs intersection tests on the real geometries of WKT encoded stream elements). A unique feature of BBoxDB Streams is the ability to perform continuous spatial joins between stream elements and previously stored multi-dimensional big data. For example, the dynamic position of a car can be efficiently joined with the static spatial data of a street network.

Abstract We propose a simple model for distributed query processing based on the concept of a distributed array. Such an array has fields of some data type whose values can be stored on different machines. It offers operations to manipulate all fields in parallel within the distributed algebra. The arrays considered are one-dimensional and just serve to model a partitioned and distributed data set. Distributed arrays rest on a given set of data types and operations called the basic algebra implemented by some piece of software called the basic engine. It provides a complete environment for query processing on a single machine. We assume this environment is extensible by types and operations. Operations on distributed arrays are implemented by one basic engine called the master which controls a set of basic engines called the workers. It maps operations on distributed arrays to the respective operations on their fields executed by workers. The distributed algebra is completely generic: any type or operation added in the extensible basic engine will be immediately available for distributed query processing. To demonstrate the use of the distributed algebra as a language for distributed query processing, we describe a fairly complex algorithm for distributed density-based similarity clustering. The algorithm is a novel contribution by itself. Its complete implementation is shown in terms of the distributed algebra and the basic algebra. As a basic engine the Secondo system is used, a rich environment for extensible query processing, providing useful tools such as main memory M-trees, graphs, or a DBScan implementation.

BBoxDB is a distributed key-bounding-box-value store which is capable of handling large scale n-dimensional data. Unlike existing key-value stores, each value is stored together with a bounding box which describes the location of the value in an n-dimensional space. BBoxDB splits large datasets automatically and spreads them across a cluster of nodes. The software works primarily on the bounding boxes of the stored data; operations like range queries or joins take only the bounding boxes of the data into consideration. In version 0.9.1, we implemented support for user defined filters (UDF) in BBoxDB; UDFs operate on the real values of the data. In this paper, we describe this novel feature for the first time. As an example, a UDF is developed in this paper which is capable of handling GeoJSON encoded data. The UDF consists only of a few lines of code and turns the generic distributed datastore BBoxDB into a specialized system that is capable of processing large scale GeoJSON encoded datasets. Operations like spatial joins or range queries on the real geometries of the data become possible. During our demonstration, we show the implementation of the UDF and perform range queries and spatial joins. The used dataset contains spatial data of the whole world and is obtained from the Open Street Map project. For visualization, the GUI of BBoxDB was extended in a way that spatial queries can easily be executed. Using the GUI, query results can be interactively explored; they are shown as an overlay on a map dynamically fetched from the Open Street Map project.

BBoxDB is a distributed and highly available key-bounding-box-value store which enhances the classical key-value data model with an axis-parallel bounding box. The bounding box describes the location of the values in an n-dimensional space, and enables BBoxDB to efficiently distribute multi-dimensional data across a cluster of nodes. Well-known geometric algorithms (such as the K-D Tree) are used to create distribution regions (multi-dimensional shards). Distribution regions are created dynamically, based on the stored data. BBoxDB stores data of multiple tables co-partitioned, which enables efficient distributed spatial joins. Spatial joins on co-partitioned tables can be executed without data shuffling between nodes. A two-level index structure is employed to retrieve stored data quickly. We demonstrate the interaction with the system, the dynamic creation of distribution regions and the data redistribution feature of BBoxDB.