As the volumes of spatiotemporal trajectory data continue to grow at a rapid pace; a new generation of data management techniques is needed in order to be able to utilize these data to provide a range of data-driven services, including geographic-type services. Key challenges posed by spatiotemporal data include the massive data volumes, the high velocity with which the data are captured, the need for interactive response times, and the inherent inaccuracy of the data. We propose an infrastructure, Elite, that leverages peer-to-peer and parallel computing techniques to address these challenges. The infrastructure offers efficient, parallel update and query processing by organizing the data into a layered index structure that is logically centralized, but physically distributed among computing nodes. The infrastructure is elastic with respect to storage, meaning that it adapts to fluctuations in the storage volume, and with respect to computation, meaning that the degree of parallelism can be adapted to best match the computational requirements. Further, the infrastructure offers advanced functionality, including probabilistic simulations, for contending with the inaccuracy of the underlying data in query processing. Extensive empirical studies offer insight into properties of the infrastructure and indicate that it meets its design goals, thus enabling the effective management of big spatiotemporal data.

1. The minimum capacity is below half of the maximum capacity. Otherwise, the condensed node may exceed the maximum capacity.

2. Details on the *node are covered in Sect. 4.3.1.

3. From experiments, we obtained\(\alpha =5e^{-4}\),\(\beta =1e^{-6}\), and\(\gamma =1e^{-6}\).

4. http://iapg.jade-hs.de/personen/brinkhoff/generator/.

5. http://research.microsoft.com/en-us/downloads/b16d359d-d164-469e-9fd4-daa38f2b2e13/.

6. http://en.wikipedia.org/wiki/DifferentialGPS.

7. http://www.mongodb.org.

8. https://github.com/couchbase/geocouch.

9. There exist different semantics for top-k queries over uncertain data, such as U-TopK, U-kRanks, Expected scores, and Expected ranks. Among them, the Expected score and Expected rank might be best ones in terms of properties such as Containment and Unique-Rank [39].

This work was supported by the 973 program with No 2012CB316205, a grant from the Obel Family Foundation, and National Science Foundation of China under Grant No. 61432006. The work was done in part when some of the authors visited SA Center for Big Data Research at Renmin University of China. The center is partially funded by the Chinese National “111” Project “Attracting International Talents in Data Engineering and Knowledge Engineering Research”.

Authors and Affiliations

1. Department of Computer Science, Aalborg University, Aalborg, Denmark

   Xike Xie & Christian S. Jensen

2. School of Information, Renmin University of China, Beijing, China

   Benjin Mei

3. Key Lab of Data Engineering and Knowledge Engineering, Renmin University of China, Beijing, China

   Jinchuan Chen & Xiaoyong Du

Corresponding author

Correspondence toJinchuan Chen.

Appendix 1: Algorithms

Appendix 2: Routing cost estimation

Lemma 1

The maximum routing cost of a three-dimensional torus ofN nodes is approximately equal to\(0.91 N^{\frac{1}{3}}\).

Proof

For any torus noden, it takes one hop to reach its six neighbors (first-order neighbors) and two hops to reach its 18 second order neighbors. The number ofi-th order neighbors\(a^i\) can be represented by [40]:

Suppose the furthest node on the torus takesm hops from noden. The total number of nodesN visited equals the summation of the number of 1-th tom-th order neighbors. We have:

Thus, the maximum routing cost equals to the distance ton’sm-th order neighbor,\(0.91N^{\frac{1}{3}}\).\(\square \)

Lemma 2

The average routing cost of a three-dimensional torus ofN nodes is approximately equal to\(0.69 N^{\frac{1}{3}}\) hops.

Proof

Based on Lemma 1, the furthest node fromn requiresm hops. Then, the average number of hops is:

\(\square \)

Appendix 3: Estimation ofh

Let us consider the cost estimation on torus node\(T_i\). After the range search\(Q_i \oplus d_{{ max }} \oplus U_{{ max }}\) (Step 6 in Algorithm 2), we get a set\(C_i\) of candidate trajectories with the average length\(\overline{{\mathcal {T}}_c\cdot \varDelta t}=\frac{1}{|C_i|} \sum _{{\mathcal {T}} \in C_i} {\mathcal {T}}\cdot \varDelta t\). According to Definition 5, the cost of STNNQ depends on the number of trajectories at each snapshot. To estimate that, we first assume the trajectories are uniformly distributed in the spatiotemporal region\(Q_i \oplus d_{{ max }} \oplus U_{{ max }}\).

We define the density\(\rho \), as the number of objects per snapshot divided by the area of the filtering bound\(\pi (d_{{ max }}+U_{{ max }})^2\).

Lemma 3

Assume a two-dimensional regionS in the spatial domain\({\mathfrak {S}}\), where the points are uniformly distributed, and let\(N(S) = m\) represent the fact that there arem points inside regionS. The probability of\(N(S) = m\) is given by:

Proof

The probability thatm points out ofn objects are inS is:

The extreme form of the binomial distribution is a Poisson distribution. Let\(\rho = \frac{n}{|{\mathfrak {S}}|}\). The above equation becomes:

Then, the probability that there is at least one point inS is:

\(\square \)

Then, we can infer that there is a nearest neighbor within the circular regionS to the query point with a probability higher than\(P^*\). In our implementation, we set\(P^*\) to 0.9, which is reasonably large forS to contain the nearest neighbor.

The number of candidate objects per snapshot is estimated as:

Appendix 4: Obtaining\(d_{\mathrm{max}}\)

In our system, we try a series of range queries\(Q_i \oplus d \oplus U_{{ max }}\) to incrementally obtain\(d_{{ max }}\), where\(d=5, 10, 20\,\%, \cdots \) of torus node\(T_i\)’s spatial domain size. Upon collecting the candidate trajectory set\(C_i\) by the range search parameterized withd, we test whether the union of these trajectories’ time spans can cover\(Q_i\)’s\(\varDelta t\), i.e., to decide whether\(\cup _{UT \in C}UT\cdot \varDelta t \supseteq Q_i\cdot \varDelta t\) is true. If true, it means that there always exists at least an object for each timestamp in\(Q_i\cdot \varDelta t\). Therefore, currentd is taken as\(d_{{ max }}\), which is sufficiently large for not missing any possible candidate trajectories. Otherwise, we need to increased incrementally and repeat the aforementioned process.

Reprints and permissions