Moving objects databases (MOD) have been studied intensively and extensively in the database eld. Recently, the emerging Big Data trend, which refers to a collection of large, complex, and rapidly growing geographical data collected from sensors and GPS-enabled devices, has posed new requirements for MOD: the ability to manage massive volume of data, the support for low-latency spatio-temporal queries and the need for high insertion throughput rate. Although key{value stores handle large-scale data e ciently, they are not equipped with e ective functions for supporting spatio-temporal data. In this project, we aim to build a distributed MOD which ful lls all these requirements. We focus on the design of an e cient distributed spatio-temporal index that can support indexing and querying moving object data in key{value stores.
Recent rapid improvements in positioning technologies such as satellites, the Global Positioning System (GPS), sensors, and wireless networks has resulted in an explosion of data generated by moving objects. For instance, tra c management systems in busy cities such as Tokyo have been collecting large numbers of location updates from probe cars such as taxis, buses and GPS-enabled devices at a rate of multiple updates per minute from each vehicle. The collected data often include location data (longitude and latitude) and time data (a timestamp).
Many systems, in both scienti c research and daily life, have taken advantage of the data collected from moving objects. For example, intelligent transportation systems are exploiting the massive volume of sensor data from probe cars and GPS-enabled devices to provide e cient route planning and tra c balancing based on the current tra c situation. People can take advantage of these systems by continuously sending data about their current location and time, then receiving relevant real-time analyses of their tra c situation. Such systems require a MOD; that can store massive volumes of data, support high insertion throughputs, and respond to queries in real-time.
There are three main challenges for a MOD to be useful for these systems. The Volume Challenge. The database should have high scalability, fault-tolerance and availability while dealing with large volumes of collected data. The High Computational Complexity Challenge. Many queries will involve geometric computations, such as very expensive logical operations on spatial relationships, that are continuously changing. The Real-time Processing Challenge. Because many agents keep registering their location updates continuously, the database must have high insertion throughput to handle the volume of data. It must also guarantee satisfactory performance on queries, but as the dataset become bigger, query time can increase dramatically.
Some systems have been proposed, such as SpatialHadoop
[
Spatial support has been extended to KVS. For instance,
MD-HBase [
The goal of our work is to build a complete MOD based
on KVS that overcomes the above challenges. We rst
proposed a novel two-tier index structure to handle spatial data
1https://hbase.apache.org
2http://geohash.org
3http://accumulo.apache.org
in HBase. Our experimental results indicate that queries
using the proposed index outperformed queries with other
indexes and queries in a MapReduce-based system. Then
we indexed moving objects data by presenting a lightweight
spatio-temporal index structure based on STCode [
In our project, we build the database based on the
architecture of KVS. This is modeled after Google's BigTable
[
HBase is a distributed scalable database that takes advantage of the HDFS. Tables in HBase include rows and columns like other databases, but they can scale to large numbers of rows and columns. To store such large tables in a distributed cluster, tables are split into a number of smaller chunks called regions, which are stored in servers called RegionServers.
HBase is also a KVS since its data model is organized as a KVS. Within a table, data are stored as a sorted list of keyvalue pairs according to rows that are uniquely identi ed by their rowkeys, which therefore play an important role when searching or scanning. Rowkey design is one of the most important aspects of HBase schema as well as other KVS.
The physical data model in HBase is column-oriented, making it a column-oriented database. Rows in HBase are composed of columns and columns are grouped into column families. Columns in a family are stored together in a lowlevel storage le called an HFile. The column family forms the basic unit of physical storage to which HBase features such as compression can be applied. Hence, proper design of column families is also essential when storing and processing data on HBase.
3.1.1
Data stored in HBase are accessed by a single rowkey. However, spatial data are represented by two coordinates (longitude and latitude), which are equally important in de ning a location. Geohash provides a solution to transform longitude/latitude coordinates into unique codes. Figure 1 shows how to generate a Geohash code for a spatial point. Geohash recursively performs binary partitioning to divide the range into two equal parts, and then assign bit 0 if the location is in the left part and bit 1 if it is the right part, respectively. Then it interleaves bits from the two dimensions and uses base 32 to encode the bit sequence into a hash code.
There are some advantages of using Geohash to store
spatial data into KVS. Points that share the same Geohash
pre x will be close to each other geographically. If we store
objects in lexicographical order of row keys in the KVS,
objects that are close to each other spatially will also be close to
each other in the database and we can scan relevant objects
e ciently by using pre x lters. However, using Geohash
alone does not guarantee e cient spatial query processing.
For instance, a pre x lter may give insu cient results when
nding k nearest neighbors of a point that is near the
rectangle border of the pre x. Geohash uses Z-order to order
the rectangles, as shown in Figure 2, so when the system
scans all points ranging from rectangles with Geohash 1 to
4, it will scan the unrelated rectangles 2 and 3. To obtain
accurate query results and prune unnecessary scanning, we
utilized the R-Tree, a multidimensional index structure for
geographical data, as the secondary index tier.
To bridge the two tiers Geohash and R-Tree, we propose a
novel data structure, the binary Geohash rectangle-partition
tree (BGRP Tree) [
We built a cluster with 64 nodes. Each node had a virtual core, 8 GB memory and a 64 GB hard drive. The operating system for the nodes was CentOS 7.0 (64-bit). We set up one HMaster, 60 Region Servers and three Zookeeper Quorums using Apache HBase 0.98.7 with Apache Hadoop 2.4.1 and Zookeeper 3.4.6. Replication was set to two. To conduct queries on SpatialHadoop, we installed SpatialHadoop v2.1, which shipped with Apache Hadoop 1.2.1, and con gured one master and 64 slaves.
We evaluated the insert performance using Yahoo! Cloud
System Benchmark. The number of workloads was varied
from one to 64. Because real spatial data are often skewed,
we chose a Zip an distribution to generate longitude and
latitude of each input point. We observed that the system
could sustain a peak throughput of 600 K inserts per second
when there were eight workloads generating data. However,
when the number of workloads was increased to 32 or 64,
we observed a drop in performance. This was because of the
cost of splitting regions when a region becomes a hot spot.
Moving objects data are naturally skewed but as shown in
Figure 2, Geohash divides the space into equal buckets, so
some pre xes in dense areas (e.g., u, s, w ) are used more
frequently than the pre xes in sparse areas (e.g., 0, 1, 2, 3 ),
and regions of the pre xes in dense area can easily become
hot spots.
We executed k nearest neighbours (kNN) queries using the
two real datasets, T-Drive [
A spatial index is important in indexing moving objects,
but we cannot apply it directly to create a moving-objects
index because of the evolution of objects over time. In our
current approach, temporal information is simply treated as
an extra dimension on top of the spatial hash. For instance,
STCode [
Because KVS keeps rowkeys in lexicographical order, we can exploit STCode as a rowkey on HBase. Since STCode cannot encode the year information, we achieve the same STCode for points that are in the same place and time but in di erent years. To handle this limitation, we stored the year information as a column family in HBase. The reason we chose a column family is that it is the secondary information to identify a row beside the rowkey, and the basic unit of physical storage in HBase. By using year information as a column family, we can distinguish data for di erent years and store or compress all data for a year in the same or nearby physical storage, thus improve the performance when searching for close points in the database. 4.
In this section, we describe the key future directions to meet the requirements of a MOD and to overcome some limitations of our previous work as discussed in Section 3.
Space- lling curves: Transforming from two-dimensional
spatial data into one-dimensional data is essential to store
moving objects data into KVS. In previous work, we have
used Z-order because of its simplicity for both encoding
and decoding, so it could support high insertion
throughput. However, the quality measures for space- lling curves
in [
Indexing current and near future movement: Temporal information has a special feature|monotonicity. For example, if the evolution of an object is represented by a set of records (oi; si; ti) where si is the location of object oi at the timestamp ti, for each two consecutive records of an object oi (oi; si; ti) and (oi; si+1; ti+1), we always have ti+1 > ti. Because of this feature, some moving objects data could be considered as obsolete if their timestamps are smaller than a prede ned threshold. To handle these obsolete entries, pack and purge operations could be employed to save index and storage space. Purging obsolete entries and reorganizing after purge operations must be considered while designing index structures. Separately maintaining temporal and spatial information in uences purge operations less than other queries, which are often related to recent data. Therefore, instead of indexing temporal information as another dimension, which occurs in STCode, incorporating it as a special dimension is a potential and challenging approach in our research.
Density based partition: While Z-order as well as some other space- lling curves divide the surface into equal buckets, moving objects data are naturally skewed. This leads to some problems in handling spatial queries. First, as mentioned in Section 3.1, the load imbalance of data insertion into distributed storage could reduce the insertion throughput. Second, it also causes many false positive scans if the scanning bucket is bigger than the query range. On the other hand, if we divide the query range into a large number of small buckets to scan, the I/O increment would cause signi cant performance deterioration. To overcome these problems, we should partition the space according to the density of the data.
Storing and querying geospatial data have been supported
by some NoSQL databases such as document-oriented
databases (CouchDB, MongoDB) or network-oriented (Neo4j).
[
With the development of large main memories, many
researchers have proposed main-memory indexes to deal with
the challenge of trading o between high update rates and
low-latency location-based queries. TwinGrid [
This paper discusses the challenges of building MOD that can support large volumes of data and provide both lowlatency queries and high insertion throughput. We have proposed an index structure to support spatial data on KVS and observed improved query performance compared with other index structures and with the state-of-the-art framework based on MapReduce. We are in the early stages of integrating temporal information into spatial index structures to support moving objects data. We described the problems left to solve and the approaches and plans to achieve the goal of this PhD project.