The problem of evaluating orthogonal range queries e ciently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20% of the elements of the dataset a linear scanning of the data was the most e cient solution. In recent experimental works using modern hardware{with main memory and parallelism{ the conclusion is that linear scan is preferable for almost every query con guration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm {using main memory and concurrency. Our aim is to prove that under this framework, it is possible to beat the performance of linear scanning by the one of hierarchical multidimensional data structures{ such as kd trees, quad trees, R trees or similar.
? Work supported by grant GRAMM (TIN2017-86727-C2-1-R) and EU FEDER funds.
queries. However, in practice, the usefulness of this approach heavily relies on the
selectivity and con guration of the sequence of range queries and, unfortunately
common wisdom told that a simple scan beats multidimensional data structures
for queries accessing more than 15%-20% of a data collection [
Recently, multidimensional range queries as well as the e ciency of
hierarchical multidimensional data structures to support them have been revisited
under a modern hardware perspective [
In this work, we propose a new way to parallelise the multidimensional range
query problem using the dynamic pipeline model [
We propose an algorithm based on a dynamic pipeline [
Algorithms under this paradigm must specify four kind of stages: input, output, generator and lter stages as well as the number and the type of the I/O unidirectional channels. The input and output stages are the interface of the pipeline, managing the input and output data respectively. Input data is fed to the input stage and the output stage will produce results. The generator is responsible to create the (parameterised) lter stages.
We now describe two algorithms to solve range queries based on the dynamic pipeline model: a nave algorithm equivalent to a linear scan of the whole dataset followed by the algorithm that we propose, based on a preprocessing of the dataset by means of data structures such as kd trees, quad trees or R trees. We will describe both algorithms for a single range query since the same process is applicable to a sequence of queries iterating on the process for a single one. Nave Algorithm. We start by describing a nave algorithm equivalent to a concurrent approach of the complete scan of the data set.
To answer Q using the pipeline approach it is necessary to have a recursive process that constructs a sequence of lters (processes). Every lter stands for one of the s unidimensional ranges of Q, let us say j (1 j s), and it discards from further consideration all the points of the data set that are outside range (ij ; lj ; uj ), that is, all those points with ij -th coordinate smaller than lj or greater than uj . Since the query has s ranges, the pipe will end up with s processes acting concurrently.
This nave algorithm starts by setting an initial pipeline consisting of 3 stages {the input, the generator and the output stages, in this sequential order{ and two channels {the rst carry the sequence of triplets of Q and the second the sequence of points in F .
The process starts by feeding (in sequential order) the input stage with the triplets of Q carried by the rst channel. The con guration of the pipe evolves (stretches) as follows. The input stage passes the data from the rst channel (a triplet of the query at a time) to its successor neighbour. At the very beginning the triplet (i1; l1; u1) is passed from the input stage to the generator stage. Every time a triplet arrives to the generator a lter stage, standing for this triplet, is created as the stage immediately previous to the generator stage. So, at the very beginning, a lter f1 for the rst range of Q is created. The pipeline consists now of four stages: input, f1, generator and output, in this order. When triplet (ij ; lij ; uij ) passes through the input stage, it passes also through f1, since ij 6= i1, it passes through f2, . . . , fj , up to arrive to the generator where lter fj+1 is created. The process continues until the elements carried by the rst channel are all treated and the channel is empty. The pipe now, regarding the initial pipe, has s additional stages, one per each triplet of the query.
The next step is to treat the data carried by the second channel, the points. Every point of the data set passes through the pipe. At every lter fi, as we already mentioned, if the i-th coordinate of the point is outside the range stored at fi the point is discarded, otherwise it is passed to next stage. Therefore, all the points that arrive to the output stage should be reported as part of Q.
This nave algorithm will force to read and check every point in the original set, having therefore complexity proportional to n, independently of the con guration of Q.
Proposed Algorithm. To improve the e ciency of the nave algorithm we
propose a preprocessing of the dataset by means of a hierarchical
multidimensional data structure. The data structure can be any of the classical ones [
Now, instead of directly ltering points, the pipe will lter, rst, the sequence S of bounding boxes produced by the data structure (it will have then 3 channels instead of two, as before). The bounding boxes will pass through the pipe by their speci cation and not by the points that they contain. Every lter stage, checking for the i-th range of the query, will discard from further consideration all the bounding boxes whose i-th range does not intersect the i-th range of the query and will pass the intersecting bounding boxes to next stage. Additionally, the ltering of bounding boxes divides them into two groups: BBC (the group of bounding boxes which are completely contained into Q) and BBP (the group of bounding boxes that intersect Q but are not contained in it).
The algorithm will output all points that are inside of BBC bounding boxes (since they are all in Q) and it will look and lter all the points in BBP bounding boxes to decide whether they are in Q.
The total number of treated points corresponds to the number of points contained in the BBC and BBP bounding boxes, which can be considerably less than the total number of points in F (but this highly depends on the con guration of the queries, data points, and chosen data structure). Additionally, the algorithm incurs in the cost of checking the m bounding boxes of S. Our proposal is to maintain this cost negligible compared to the number of points that have to be checked by choosing correctly the number of levels of the tree data structure during the preprocessing of the data. 3
We have implemented quad tries in the C++ programming language
producing with this program the sequence of m les that containing the points inside
the corresponding bounding box in sequence S. Besides, we have implemented
the pipeline in the Go programming language (because of its mechanisms of
go-routines and channels). Our preliminar experiments show that our proposed
algorithm beats the nave one treating systematically half the points of the data
set for queries containing up to a 25% of the points of F . We plan to conduct
further experiments according to the following guidelines: (a) Considering huge
datasets and allocating their corresponding (tree-like) hierarchical
representations in the RAM, we envision that the performance of our algorithm overcomes
the results presented in [