MD-HBase: A Scalable Multi-dimensional Data
Infrastructure for Location Aware Services
Shoji Nishimura∗§

Sudipto Das†

Divyakant Agrawal†

Amr El Abbadi†∗ Service Platforms Research Laboratories† Department of Computer Science

NEC Corporation
Kawasaki, Kanagawa 211-8666, Japan

University of California, Santa Barbara
Santa Barbara, CA 93106-5110, USAs-nishimura@bk.jp.nec.com{sudipto, agrawal, amr}@cs.ucsb.edu

Abstract—The ubiquity of location enabled devices has resulted
in a wide proliferation of location based applications and services.
To handle the growing scale, database management systems
driving such location based services (LBS) must cope with highinsert rates for location updates of millions of devices, while supporting efficient real-time analysis on latest location. Traditional
DBMSs, equipped with multi-dimensional index structures, canefficiently handle spatio-temporal data. However, popular opensource relational database systems are overwhelmed by the highinsertion rates, real-time querying requirements, and terabytes
of data that these systems must handle. On the other hand,
Key-value stores can effectively support large scale operation,
but do not natively support multi-attribute accesses needed tosupport the rich querying functionality essential for the LBSs.
We present MD-HBase, a scalable data management system for
LBSs that bridges this gap between scale and functionality. Our
approach leverages a multi-dimensional index structure layered
over a Key-value store. The underlying Key-value store allows
the system to sustain high insert throughput and large data
volumes, while ensuring fault-tolerance, and high availability. On
the other hand, the index layer allows efficient multi-dimensional
query processing. We present the design of MD-HBase thatbuilds two standard index structures—the K-d tree and the Quadtree—over a range partitioned Key-value store. Our prototype
implementation using HBase, a standard open-source Key-value
store, can handle hundreds of thousands of inserts per secondusing a modest 16 node cluster, while efficiently processing multidimensional range queries and nearest neighbor queries in realtime with response times as low as hundreds of milliseconds.
Index Terms—location based services; key value stores; multidimensional data; real time analysis;

I. I NTRODUCTION
The last few years have witnessed a significant increase inhand-held devices becoming location aware with the potential
to continuously report up-to-date location information of theirusers. This has led to a large number of location based
services (LBS) which customize a user’s experience based on
location. Some applications—such as customized recommendations and advertisements based on a user’s current locationand history—have immediate economic incentives, while someother applications—such as location based social networking
or location aware gaming—enrich the user’s experience ingeneral. With major wireless providers serving hundreds of§ Work done as a visiting researcher at UCSB.

millions of subscribers [1], millions of devices registering
their location updates continuously is quite common. Databasemanagement systems (DBMS) driving these location based
services must therefore handle millions of location updates
per minute while answering near real time analysis and statistical queries that drive the different recommendation andpersonalization services.
Location data is inherently multi-dimensional, minimally
including a user id, a latitude, a longitude, and a time stamp.
A rich literature of multi-dimensional indexing techniques—
for instance, K-d trees [2], Quad trees [3] and R-trees [4]—have empowered relational databases (RDBMS) to efficiently
process multi-dimensional data. However, the major challenge
posed by these location based services is in scaling thesystems to sustain the high throughput of location updates
and analyzing huge volumes of data to glean intelligence.
For instance, if we consider only the insert throughput, a
MySQL installation running on a commodity server becomes abottleneck at loads of tens of thousands of inserts per second;
performance is further impacted adversely when answering
queries concurrently. Advanced designs, such as staging thedatabase, defining views, database and application partitioning
to scale out, a distributed cache, or moving to commercial
systems, will increase the throughput; however, such optimizations are expensive to design, deploy, and maintain.
On the other hand, Key-value stores, both in-house systems
such as Bigtable [5] and their open source counterparts like
HBase [6], have proven to scale to millions of updates while
being fault-tolerant and highly available. However, Key-value
stores do not natively support efficient multi-attribute access,a key requirement for the rich functionality needed to support
LBSs. In the absence of any filtering mechanism for secondary
attribute accesses, such queries resort to full scan of the entire
data. MapReduce [7] style processing is therefore a commonlyused approach for analysis on Key-value stores. Even though
the MapReduce framework provides abundant parallelism, afull scan is wasteful, especially when the selectivity of thequeries is high. Moreover, many applications require nearreal-time query processing based on a user’s current location.
Therefore, query results based on a user’s stale location
is often useless. As a result, a design for batched query
processing on data periodically imported into a data warehouse

is inappropriate for the real-time analysis requirement.
RDBMSsproviderich
querying support
for
multidimensional
data but are notscalable,while
Key-value stores
can scale but
Fig. 1. Architecture of MD-HBase.
cannothandlemulti-dimensional data efficiently. Our solution, called MDHBase, bridges this gap by layering a multi-dimensional index
over a Key-value store to leverage the best of both worlds.1
We use linearization techniques such as Z-ordering [8] totransform multi-dimensional location information into a one
dimensional space and use a range partitioned Key-value
store (HBase [6] in our implementation) as the storage backend. Figure 1 illustrates MD-HBase’s architecture showing
the index layer and the data storage layer. We show how thisdesign allows standard and proven multi-dimensional index
structures, such as K-d trees and Quad trees, to be layeredon top of the Key-value stores with minimal changes to theunderlying store and negligible effect on the operation of theKey-value store. The underlying Key-value store provides
the ability to sustain a high insert throughput and large data
volumes, while ensuring fault-tolerance and high availability.
The overlaid index layer allows efficient real-time processingof multi-dimensional range and nearest neighbor queries thatcomprise the basic data analysis primitives for location based
applications. We evaluate different implementations of thedata storage layer in the Key-value store and evaluate thetrade-offs associated with these different implementations.
In our experiments, MD-HBase achieved more than 200K
inserts per second on a modest cluster spanning 16 nodes,
while supporting real-time range and nearest neighbor queries
with response times less than one second. Assuming devices
reporting one location update per minute, this small cluster canhandle updates from 10 − 15 million devices while providing
between one to two orders of magnitude improvement overa MapReduce or Z-ordering based implementation for query
processing. Moreover, our design does not introduce any
scalability bottlenecks, thus allowing the implementation toscale with the underlying Key-value data store.
Contributions.
We propose the design of MD-HBase that uses linearization to implement a scalable multi-dimensional index
structure layered over a range-partitioned Key-value store.
• We demonstrate how this design can be used to implement a K-d tree and a Quad tree, two standard multidimensional index structures.
• We present three alternative implementations of the storage layer in the Key-value store and evaluate the tradeoffs•

1 The name MD-HBase signifies adding multi-dimensional data processing

capabilities to HBase, a range partitioned Key-value store.

associated with each implementation.
We provide a detailed evaluation of our prototype usingsynthetically generated location data and analyze MDHBase’s scalability and efficiency.
Organization. Section II provides background on location based applications, linearization techniques, and multidimensional index structures. Section III describes the design
and implementation of the index layer and Section IV describes the implementation of the data storage layer. Section V
presents a detailed evaluation of MD-HBase by comparing
the different design choices. Section VI surveys the related
literature and Section VII concludes the paper.
•

II. BACKGROUND
A. Location based applications
Location data points are multi-dimensional with spatial
attributes (e.g., longitude and latitude), a temporal attribute(e.g., timestamp), and an entity attribute (e.g., user’s ID).
Different applications use this information in a variety of ways.
We provide two simple examples that illustrate the use of
location data for providing location aware services.
A PPLICATION 1: Location based advertisements andcoupon distribution: Consider a restaurant chain, such as
McDonalds, running a promotional discount for the next hourto advertise a new snack and wants to disseminate coupons
to attract customers who are currently near any of theirrestaurants spread throughout the country. An LBS provider
issues multi-dimensional range queries to determine all users
within 5 miles from any restaurant in the chain and delivers a
coupon to their respecting devices. Another approach to run asimilar campaign with a limited budget is to limit the coupons
to only the 100 users nearest to a restaurant location. In thiscase, the LBS provider issues nearest neighbors queries todetermine the users. In either case, considering a countrywide(or worldwide) presence of this restaurant chain, the amountof data analyzed by such queries is huge.
A PPLICATION 2: Location based social applications: Consider a social application that notifies a user of his/her friends
who are currently nearby. The LBS provider in this case issues
a range query around the user’s current location and intersects
the user’s friend list with the results. Again, considering thescale of current social applications, an LBS provider must
handle data for tens to hundreds of millions of its users toanswer these queries for its users spread across a country.
Location information has two important characteristics.
First, it is inherently skewed, both spatially and temporally.
For instance, urban regions are more dense compared torural regions, while business and school districts are dense
during weekdays, while residential areas are dense during thenight and weekends. Second, the time dimension is potentiallyunbounded and monotonically increasing. We later discuss
how these characteristics influence many of the design choices.
B. Linearization Techniques
Linearization [9] is a method to transform multidimensional data points to a single dimension and is a key

aspect of the index layer in MD-HBase. Linearization allows
leveraging a single-dimensional database (a Key-value store in
our case) for efficient multi-dimensional query processing. A
space-filling curve [9] is one of the most popular approaches
for linearization. A space filling curve visits all points in themulti-dimensional space in a systematic order. Z-ordering [8]is an example of a space filling curve. Z-ordering loosely
preserves the locality of data-points in the multi-dimensional
space and is also easy to implement.
Linearization alone is however not enough for efficientquery processing; a linearization based multi-dimensional index layer, though simple in design, results in inefficient query
processing. For instance, a range query on a linearized system
is decomposed into several linearized sub-queries; however,a trade-off exists between the number of sub-queries andthe number of false-positives. A reduction in the number oflinearized sub-queries results in an increase in the overhead
due to the large number of false-positives. On the other hand,eliminating false-positives results in a significant growth in thenumber of sub-queries. Furthermore, such a naı̈ve technique
is not robust to skew inherent in many real life applications.
C. Multi-dimensional Index Structures
The Quad tree [3] and the K-d tree [2] are two of themost popular multi-dimensional indexing structures. They split
the multi-dimensional space recursively into subspaces in asystematic manner and organize these subspaces as a searchtree. A Quad tree divides the n-dimensional space into 2n
subspaces along all dimensions whereas a K-d tree alternates
the splitting of the dimensions. Each subspace has a maximum
limit on the number of data points in it, beyond which thesubspace is split. Two approaches are commonly used to
split a subspace: a trie-based approach and a point-based
approach [9]. The trie-based approach splits the space at the
mid-point of a dimension, resulting in equal size splits; while
the point-based technique splits the space by the median ofdata points, resulting in subspaces with equal number of data
points. The trie-based approach is efficient to implement as
it results in regular shaped subspaces. On the other hand, thepoint based approach is more robust to skew.
In addition to the performanceissues, trie-based Quad trees and Kd trees have a property that allows
them to be coupled with Z-ordering.
A trie-based split of a Quad tree
or a K-d tree results in subspaces
where all z-values in any subspace
Fig. 2. Space splitting in aare continuous. Figure 2 provides an K-d tree.
illustration using a K-d tree for two
dimensions; an example using a Quad tree is very similar.
Different shades denote different subspaces and the dashedarrows denote the z-order traversal. As is evident, in any of thesubspaces the Z-values are continuous. This observation forms
the basis of the indexing layer of MD-HBase. Compared toa naı̈ve linearization based index structure or a B+-Tree index
built on linearized values, K-d and Quad trees capture data

distribution statistics. They partition the target space based on
the data distribution and limit the number of data points in eachsubspace, resulting in more splits in hot regions. Furthermore,
Quad trees and KD trees maintain the boundaries of subspaces in the original space. This allows efficient pruning of
the space as well as reducing the number of false positive
scans during query processing and therefore is more robust
to skew. Moreover, when executing the best-first algorithm
for kNN queries, the fastest practical algorithm, a B+ tree
based index cannot be used due to the irregular sub-space
shape. MD-HBase therefore uses these multi-dimensional
index structures instead of a simple single-dimension index
based on linearization.
III. M ULTI - DIMENSIONAL I NDEX L AYER
We now present the design of the multi-dimensional index
layer in MD-HBase. Specifically, we show how standard
index structures like K-d trees [2] and Quad trees [3] canbe adapted to be layered on top of a Key-value store. The
indexing layer assumes that the underlying data storage layer
stores the items sorted by their key and range-partitions the key
space. The keys correspond to the Z-value of the dimensions
being indexed; for instance the location and timestamp. We
use the trie-based approach for space splitting. The index
partitions the space into conceptual subspaces that are in-turn
mapped to a physical storage abstraction called bucket. The
mapping between a conceptual subspace in the index layer anda bucket in the data storage layer can be one-to-one, many-toone, or many-to-many depending on the implementation andrequirements of the application. We develop a novel naming
scheme for subspaces to simulate a trie-based K-d tree and a
Quad tree. This naming scheme, called longest common prefix naming, has two important properties critical to efficientindex maintenance and query processing; a description of thenaming scheme and its properties are discussed below.
A. Longest Common Prefix Naming Scheme
If the multi-dimensional space isdivided into equal sized subspaces
and each dimension is enumeratedusing binary values, then the z-orderof a given subspace is given by interleaving the bits from the different
dimensions. Figure 3 illustrates thisFig. 3. Binary Z-ordering.
property. For example, the Z-value ofthe sub-space (00, 11) is represented as 0101. We name eachsubspace by the longest common prefix of the z-values ofpoints contained in the subspace. Figure 4 provides an example
for partitioning the space in a trie-based Quad tree and Kd tree. For example, consider a Quad tree built on the 2D
space. The subspace at the top right of Figure 4(a), enclosed
by a thick solid line, consists of z-values 1100, 1101, 1110,
and 1111 with a longest common prefix of 11∗∗ ; the subspaceis therefore named 11∗∗ . Similarly, the lower left subspace,enclosed by a broken line, only contains 0000, and is named
0000. Now consider the example of a K-d tree in Figure 4(b).

The subspace in the right half, enclosed by a solid line,
is represented by the longest common prefix 1, while thesubspace in the bottom left consisting of 0000 and 0001 is
named as 000∗ . This naming scheme is similar to that of Prefix
Hash Tree (PHT) [10], a variant of a distributed hash table.2(a) A Quad Tree
Fig. 4.

B. Index Layer
The index layer leverages the longest common prefix naming scheme to map multi-dimensional index structures intoa single dimensional substrate. Figure 5 illustrates the mapping of a Quad tree partitioned space to the index layer;
the mapping technique for K-d trees follows similarly. We
now describe how the index layer can be used to efficiently
implement some common operations and then discuss thespace splitting algorithm for index maintenance.

(b) A K-d Tree

The longest common prefix naming scheme

MD-HBase leverages two important properties of thislongest common prefix naming scheme. First, if subspace A
encloses subspace B, the name of subspace A is a prefix of thatof subspace B. For example, in Figure 4(a), a subspace whichcontains 0000−0011 encloses a subspace which contains only
0000. The former subspace’s name, 00∗∗ , is a prefix of thelatter’s name 0000. Therefore, on a split, names of the newsubspaces can be derived from the original subspace name byappending bits depending on which dimensions were split.
Second, the subspace name is enough to determine theregion boundaries on all dimensions. This property derives
from the fact that the z-values are computed by interleaving
bits from the different dimensions and thus improves thepruning power of a range query. Determining the range
boundary consists of the following two steps: (i) given thename, extract the bits corresponding to each dimension; and(ii) complete the extracted bits by appending 0s for the lower
bound and 1s for the upper bound values, both bound values
being inclusive. For instance, let us consider the Quad tree in
Figure 4(a). The subspace at the top right enclosed by a solid
lined box is named 11. Since this is a 2D space, the prefix for
both the vertical and horizontal dimensions is 1. Therefore,
using the rule for extension, the range for both dimensions is[10, 11]. Generalizing to the n-dimensional space, a Quad tree
splits a space on all n dimensions resulting in 2n subspaces.
Therefore, the number of bits in the name of a subspace
will be an exact multiple of the number of dimensions. This
ensures that reconstructing the dimension values in step (i) will
provide values for all dimensions. But since a K-d tree splits
on alternate dimensions, the number of bits in the name is notguaranteed to be a multiple of the number of dimensions, inwhich case the prefix for different dimensions have different
lengths. Considering the K-d tree example of Figure 4(b),for the lower left subspace named 000∗, the prefix for thehorizontal dimension is 00 while that of the vertical dimension
is 0, resulting in the bounds for the horizontal dimension as[00, 00] and that of the vertical dimension as [00, 01].
2 http://en.wikipedia.org/wiki/Distributed hash table

Fig. 5.

Index layer mapping a trie-based Quad tree.

1) Subspace Lookup and Point Queries: Determining thesubspace to which a point belongs forms the basis for point
queries as well as for data insertion. Since the index layer
comprises a sorted list of subspace names, determining thesubspace to which a point belongs is efficient. Recall thatthe subspace name determines the bounds of the region thatthe subspace encloses. The search for the subspace finds theentry that has the maximum prefix matched with the z-valueof the query point; this entry corresponds to the highest value
smaller that the z-value of the query point. A prefix matching
binary search, which substitutes exact matching comparison toprefix matching comparison for the termination condition of
the binary search algorithm, is therefore sufficient. Algorithm 1
provides the algorithm for subspace lookup. To answer a point
query, we first lookup the subspace corresponding to the zvalue of the point. The point is then queried in the bucket towhich the subspace maps.
Algorithm 1 Subspace Lookup
1: /* hqi be the query point. */2: Zq ← ComputeZ-value(q)3: Bktq ← PrefixMatchingBinarySearch(Zp )2) Insertion: The algorithm to insert a new data point(shown in Algorithm 2) is similar to the point query algorithm.
It first looks up the bucket corresponding to the subspace towhich the point belongs, and then inserts the data point in
the bucket. Since there is a maximum limit to the number ofpoints a bucket can hold, the insertion algorithm checks thecurrent size of the bucket to determine if a split is needed. The
technique to split a subspace is explained in Section III-B5.
3) Range Query: A multi-dimensional range query is oneof the most frequent queries for location based applications.
Algorithm 3 provides the pseudo code for range query processing. Let hql , qh i be the range for the query, ql is thelower bound and qh is the upper bound. The z-value of theAlgorithm 2 Insert a new location data point
1: /* hpi be the new data point. */2: Bktp ← LookupSubspace(p)3: InsertToBucket(Bktp , p)4: if (Size(Bktp ) > MaxBucketSize) then5:
SplitSpace(Bktp )lower bound determines the first subspace to scan. All subsequent subspaces until the one corresponding to the upperbound are potential candidate subspaces. Let Sq denote theset of candidate subspaces. Since the z-order loosely preserves
locality, some subspaces in Sq might not be part of the range.
For example, consider the Quad tree split shown in Figure 5.
Consider the range query h[01, 11], [10, 11]i. The z-value range
for this query is [0110, 1111] which results in Sq equal to{01∗∗ , 10∗∗ , 11∗∗ }. Since the query corresponds to only the
top half of the space, the subspace named 10∗∗ is a false
positive. But such false positives are eliminated by a scan of
the index. As the subspace name only is enough to determine
the boundary of the region enclosed by the subspace, points
in a subspace are scanned only if the range of the subspaceintersects with the query range. This check is inexpensive
and prunes out all the subspaces that are not relevant. For
subspaces that are contained in the query, all points will be
returned, while subspaces that only intersect with the query
require further filtering. The steps for query processing areshown in Algorithm 3.
Algorithm 3 Range query(a) A Quad Tree
Fig. 6.

(b) A K-d Tree
Space split at the index layer.

the k-th point is less than the distance to the nearest unscannedsubspace, the query process terminates.
Algorithm 4 k Nearest Neighbors query
1: /* q be the point for the query. */2: P Qsubspace ← CreatePriorityQueue()
3: P Qresult ← CreatePriorityQueue(k) /* queue capacity is k. */4: width ← 0 /* region size for subspace search */5: Sscanned ← φ /* scanned subspaces */6: loop
7:/* expand search region. */8:
if P Qsubspace = φ then9:
Snext ← SubspacesInRegion(q, width) − Sscanned
10:
for each Subspace S ∈ Snext do
11:
Enqueue(S, MinDistance(q, S), P Qsubspace )12:/* pick the nearest subspace. */13:
S ← Dequeue(P Qsubspace )14:/* search termination condition */15:
if KthDistance(k, P Qresult ) ≤ MinDistance(q, S) then16:
return P Qresult17:/* scan and sort points by the distance from q. */18:
for each Point p ∈ S do
19:
Enqueue(p, Distance(q, p), P Qresult )20:/* maintain search status. */21:
Sscanned ∪ S
22:width ← max(width, MaxDistance(q, S))

1: /* hql , qh i be the range for the query. */2: Zlow ← ComputeZ-value(ql )3: Zhigh ← ComputeZ-value(qh )4: Sq ← {Zlow ≤ SubspaceName ≤ Zhigh }5: Rq ← φ /* Initialize result set to empty set. */6: for each Subspace S ∈ Sq do
7:hSl , Sh i ← ComputeBounds(S)8:
if (hSl , Sh i ⊆ hql , qh i) then9:
Rq ∪ ScanBucketForSpace(S)10:else if (hSl , Sh i ∩ hql , qh i) then11:
for each point p ∈ S do
12:
if (p ∈ hql , qh i) then13:
Rq ∪ p14: return Rq

Algorithm 5 Subspace name generation

4) Nearest Neighbor Query: Nearest neighbor queries arealso an important primitive operation for many location based
applications. Algorithm 4 shows the steps for k nearest neighbors query processing in MD-HBase. The algorithm is basedon the best-first algorithm where the subspaces are scanned inorder of the distance from the queried point [9].
The algorithm consists of two steps: subspace search expansion and subspace scan. During subspace search expansion we
incrementally expand the search region and sort subspaces in
the region in order of the minimum distance from the queried
point. Algorithm 4 increases the search region width to the
maximum distance from the queried point to the farthest cornerof the scanned subspaces. The next step scans the nearest
subspace that has not already been scanned and sorts points inorder of the distance from the queried point. If the distance to5) Space Split: Both K-d and Quad trees limit the numberof points contained in each subspace; a subspace is split when
the number of points in a subspace exceeds this limit. We
determine the maximum number of points by the bucket size ofthe underlying storage layer. Since the index layer is decoupledfrom the data storage layer, a subspace split in the data storage
layer is handled separately. A split in the index layer relieson the first property of the prefix naming scheme whichguarantees that the subspace name is a prefix of the namesof any enclosed subspace. A subspace split in the index layer
therefore corresponds to replacing the row corresponding tothe old subspace’s name with the names of the new subspaces.
The number of new subspaces created depends on the index
structure used: a K-d tree splits a subspace only in one
dimension, resulting in two new subspaces, while a Quad tree

1: /* Quad tree */2: NewName ← φ
3: for each dimension in [1, . . . , n] do
4:NewName ∪ {OldName ⊕ 0, OldName ⊕ 1}
5: /* K-d tree */6: NewName ← {OldName ⊕ 0, OldName ⊕ 1}

splits a subspace in all dimensions, resulting in 2n subspaces.
For every dimension split, the name of the new subspaces
is created by appending the old subspace name with a 0
and 1 at the position corresponding to the dimension being
split. Algorithm 5 provides the pseudocode for subspace namegeneration following a split. Figure 6 provides an illustrationof space splitting in the index layer for both Quad and K-dtrees in a 2D space.
Even though conceptually simple, there are a number of
implementation intricacies when splitting a space. These intricacies arise from the fact that the index layer is maintained as atable in the Key-value store and most current Key-value storessupport transactions only at the single key level. Since a split
touches at least three rows (one row for the old subspace nameand at least two rows for the new subspaces), such a change
is not transactional compared to other concurrent operations.
For instance, an analysis query concurrent to a split mightobserve an inconsistent state. Furthermore, additional logic isneeded to ensure the atomicity of the split. Techniques suchas maintaining the index as a key group as suggested in [11]can be used to guarantee multi-key transactional consistency.
We leave such extensions as future work. In addition, sincedeletions are not very common in LBSs, so we leave out thedelete operation. However, deletion and resulting merger ofsubspaces can be handled as straightforward extension of theSpace Split algorithm.
C. Implementing the Index Layer
The index layer
is a sorted sequenceof subspace names.
Since the subspacenames
encodetheboundaries,
the index layer
essentially imposes
an order betweenthesubspaces.
In
our
prior
discussion,
we
represented
the Fig. 7. Index layer Implementation on Bigtable.
index layer as a monolithic layer of sorted subspace names. A
single partition index is enough for many application needs.
Assume each bucket can hold about 106 data points. Each row
in the index layer stores very little information: the subspace
name, the mapping to the corresponding bucket, and some
additional metadata for query processing. Therefore, 100
bytes per index table row is a good estimate. The underlying
Key-value store partitions its data across multiple partitions.
Considering the typical size of a partition in Key-value storesis about 100 MB [5], the index partition can maintain amapping of about 106 subspaces. This translates to about 1012
data points using a single index partition. This estimate mightvary depending on the implementation or the configurations
used. But it provides a reasonable estimate of the size.
Our implementation also partitions the index layer for better

scalability and load balancing. We leverage the B+ tree style
metadata access structure in Bigtable to partition the index
layer without incurring any performance penalty. Bigtable, andits open source variant HBase used in our implementation, uses
a two level structure to map keys to their corresponding tablets.
The top level structure (called the ROOT) is never partitioned
and points to another level (called the META) which points
to the actual data. Figure 7 provides an illustration of thisindex implementation. This seamless integration of the index
layer into the ROOT - META structure of Bigtable does not
introduce any additional overhead as a result of index accesses.
Furthermore, optimizations such as caching the index layer andconnection sharing between clients on the same host reduces
the number of accesses to the index. Adding this additional
level in the index structure, therefore, strikes a good balance
between scale and the number of indirection levels to accessthe data items. Using an analysis similar to that used above, aconservative estimate of the number of points indexed by thistwo level index structure is 1021 .
IV. DATA S TORAGE L AYER
The data storage layer of MD-HBase is a range partitioned
Key-value store. We use HBase, the open source implementation of Bigtable, as the storage layer for MD-HBase.
A. HBase Overview
A table in HBase consists of a collection of splits, called
regions, where each region stores a range partition of the
key space. Its architecture comprises a three layered B+ tree
structure; the regions storing data constitute the lowest level.
The two upper levels are special regions referred to as the ROOT
and META regions, as described in Section III-C. An HBase
installation consists of a collection of servers, called region
servers, responsible for serving a subset of regions. Regions
are dynamically assigned to the region servers; the META table
maintains a mapping of the region to region servers. If aregion’s size exceeds a configurable limit, HBase splits it into
two sub-regions. This allows the system to grow dynamicallyas data is inserted, while dealing with data skew by creating
finer grained partitions for hot regions.
B. Implementation of the Storage Layer
A number of design choices exist to implement the data
storage layer, and it is interesting to analyze and evaluate
the trade-offs associated with each of these designs. Our
implementation uses different approaches as described below.
1) Table share model: In this model, all buckets share asingle HBase table where the data points are sorted by theircorresponding Z-value which is used as the key. Our space
splitting method guarantees that data points in a subspace arecontiguous in the table since they share a common prefix.
Therefore, buckets are managed by keeping their start and end
keys. This model allows efficient space splitting that amounts
to only updating the corresponding rows in the index table. On
the other hand, this model restricts a subspace to be mapped
to only a single bucket.

2) Table per bucket model: This model is another extreme
where we allocate a table per bucket. The data storage layer
therefore consists of multiple HBase tables. This model provides flexibility in mapping subspaces to buckets and allows
greater parallelism by allowing operations on different tables
to be dispatched in parallel. However, a subspace split in thistechnique is expensive since this involves moving data points
from the subspaces to the newly created buckets.
3) Hybrid model: This hybrid model strikes a balance
between the table share model and the table per bucket model.
First, we partition the space and allocate a table to eachresulting subspace. After this initial static partitioning, when asubspace is split as a result of an overflow, the newly createdsubspaces share the same table as that of the parent subspace.
4) Region per bucket model: A HBase table comprises ofmany regions. Therefore, another approach is to use a single
table for the entire space and use each region as a bucket.
A region split in HBase is quite efficient and is executed
asynchronously. This design therefore has a low space split
cost while being able to efficiently parallelize operations acrossthe different buckets. However, contrary to the other threemodels discussed, this model is intrusive and requires changes
to HBase; a hook is added to the split code to determine theappropriate split point based on the index structure being used.
C. Optimizations
Several optimizations are possible that further improve
performance of the storage layer.
1) Space Splitting pattern learning: Space splitting introduces overhead that affects system performance. Therefore,
advanced prediction of a split can be used to perform anasynchronous split that will reduce the impact on the inserts
and queries executing during a split. One approach is to learn
the split patterns to reduce occurrences of space split. Location
data is inherently skewed, however, as noted earlier, such skew
is often predictable by maintaining and analyzing historical information. Since MD-HBase stores historical data, the index
structure inherently maintains statistics of the data distribution.
To estimate the number of times a new bucket will be split in
the future, we lookup how many buckets were allocated to thesame spatial region in the past. For example, when we allocate
a new bucket for region ([t0 , t1 ], [x0 , x1 ], [y0 , y1 ]), we lookup
buckets for region ([t0 − ts , t1 − ts ], [x0 , x1 ], [y0 , y1 ]) in theindex table. The intuition is that the bucket splitting pattern inthe past is a good approximate predictor for the future.
2) Random Projection: Data skew makes certain subspaces
hot, both for insertion and querying. An optimization is to map
a subspace to multiple buckets with points in the subspace
distributed amongst the multiple buckets. When the points
are distributed randomly, this technique is called random
projection. When inserting a data point in a subspace, we
randomly select any one of the buckets corresponding to thesubspace. A range query that includes the subspace must scan
all the buckets mapped to the subspace. Thus, the random
projection technique naturally extends our original algorithm;

it, however, presents a trade-off between load balancing and apotential increase in query cost.
V. E XPERIMENTAL E VALUATION
We now present a detailed evaluation of our prototype implementation of MD-HBase. We implemented our prototype
using HBase 0.20.6 and Hadoop 0.20.2 as the underlying
system. We evaluate the trade-offs associated with the different
implementations for the storage layer and compare our technique with a MapReduce style analysis and query processing
using only linearization over HBase. Our experiments were
performed on an Amazon EC2 cluster whose size was varied
from 4 to 16 nodes. Each node consists of 4 virtual cores,
15.7GB memory, 1,690 GB HDD, and 64bit Linux (v2.6.32).
We evaluate the different implementations of the storage layer
as described in Section IV: table per bucket design simulating
the K-d and Quad trees (TPB/Kd and TPB/Quad), table
sharing design simulating the K-d and Quad trees (TS/Kd
and TS/Quad), and a region per bucket design for K-dtrees (RPB/Kd)3 . The baseline is an implementation using zordering for linearization (ZOrder) without any specializedindex. We also implemented the queries in Map Reduce
to evaluate the performance of a MapReduce system (MR)
performing a full parallel scan of the data; our evaluation
used the Hadoop runtime. Our evaluation uses syntheticallygenerated data sets primarily due to the need for huge data
sets (hundreds of gigabytes) and the need to control different
aspects, such as skew and selectivity, to better understand the
behavior of the system. Evaluation using real data is left for
future work.
A. Insert throughput
Supporting high insert throughput for location updates iscritical to sustain the large numbers of location devices. We
evaluated the insert performance using five different implementations of the storage layer on a cluster with 4, 8, and 16
commodity nodes. Figure 8 plots the insert throughput as afunction of the load on the system. We varied the number ofload generators from 2 to 64; each generator created a loadof 10, 000 inserts per second. We used a synthetic spatiallyskewed data set using a Zipfian distribution with a Zipfian
factor of 1.0 representing moderately skewed data. Usinga Zipfian distribution allows us to control the skew whileallowing quick generation of large data sets. Both the RPB/Kd
system and the ZOrder systems showed good scalability; on
the 16 node cluster, the RPB/Kd and ZOrder implementation
sustained a peak throughput of about 220K location updates
per second. In a system where location devices register alocation update every minute, this deployment can handle
10−15 million devices. The main reason for the low scalabilityof the table per bucket and table sharing designs is the costassociated with the splitting a bucket. On the other hand,
the region per bucket design splits buckets asynchronously
using the HBase region split mechanism which is relatively
3 Since in HBase, a region can only be split into two sub-regions, we could
not implement RPB for Quad trees as our experiments are for a 3D space.

4 nodes5

Throughput (inserts/sec)

2.5

x 10

8 nodes

5

2.5

x 10

2

2

2

1.5

1.5

1.5

1

1

1

0.5

0.5

0.5

x 10

ZOrder
TPB/KdTPB/Quad
TS/Kd
TS/Quad00

Fig. 8.

20

40

60

0
0

20
40
60
Number of Load Generators

00

RPB/Kd204060Insert throughput (location updates per second) as a function of load on the system. Each load generator creates 10,000 inserts per second.

TPB/Kd3

TPB/Quad

TS/Kd

TS/Quad

RPB/KdZOrder

MapReduce

10
Response Time(sec)

16 nodes

5

2.5

2

10

1

10

0

10

−1

10

0.01

0.1
1.0
Selectivity (%)

10.0

Fig. 9. Response times (in log scale) for range query as function of selectivity.
TABLE IFALSE P OSITIVE S CANS ON THE ZO RDER SYSTEM

No. of buckets scanned
False positives
Percentage false positive

0.01
7
3
42.9%

Selectivity (%)
0.1
1.0
28
34
22
16
78.5%
47.1%

10.0
45
16
35.5%

inexpensive. The TPB/TS systems block other operations until
the bucket split completes. In our experiments, the TPB design
required about 30 to 40 seconds to split a bucket and the TS
design required about 10 seconds. Even though these designs
result in more parallelism in distributing the insert load on thecluster, the bucket split overhead limits the peak throughput
sustained by these designs.
B. Range Query
We now evaluate range query performance using the different implementations of the index structures and the storage
layer and compare performance with ZOrder and MR. The
MR system filters out points matching the queried range andreports aggregate statistics on the matched data points.
We generated about four hundred million points using a
network-based model by Brinkhoff et al. [12]. Our data set
simulates 40, 000 objects moving 10, 000 steps along thestreets of the San Francisco bay area. Since the motion paths
are based on a real map, this data set is representative ofreal world data distributions. Evaluation using other models
to simulate motion is proposed future work. We executed therange queries on a four-node cluster in Amazon EC2.
Figure 9 plots the range query response times for thedifferent designs as a function of the varying selectivity. As

is evident from Figure 9, all the MD-HBase design choices
outperform the baseline systems. In particular, for highly
selective queries where our designs show a one to two ordersof magnitude improvement over the baseline implementations
using simple Z-ordering or using MapReduce. Moreover, thequery response time of our proposed designs is proportional
to the selectivity, which asserts the gains from the index layer
when compared to brute force parallel scan of the entire data
set as in the MR implementation whose response times are theworst amongst the alternatives considered and is independentof the query selectivity.
In the design using just Z-ordering (ZOrder), the systemscans between the minimum and the maximum Z-value of thequeried region and filters out points that do not intersect thequeried ranges. If the scanned range spans several buckets,
the system parallelizes the scans per bucket. Even though theZOrder design shows better performance compared to MR,
response time is almost ten times worse when compared toour proposed approaches, especially for queries with highselectivity. The main reason for the inferior performance of theZOrder is the false positive scans resulting from the distortionin the mapping of the points introduced by linearization.
Table I reports the number of false positives (buckets thatmatched the queried range but did not contain a matchingdata point) of the ZOrder design. For example, in case of 0.1
percent selectivity query, 22 out of 28 buckets scanned arefalse positive. The number of false positive scans depends on
the alignment of the queried range with the bucket boundaries.
In the ideal situation of a perfect match, query performanceis expected to be close to that of our proposed designs;
however, such ideal queries might not be frequently observedin practice. Our proposed designs can further optimize the scan
range within each region. Since we partition the target space
into the regular shaped subspaces, when the queried region
partially intersects a subspace, MD-HBase can compute theminimum scan range in the bucket from the boundaries of thequeried region and the subspace. In contrast, the ZOrder design
partitions the target space into irregular shaped subspaces andhence must scan all points in the selected region.
A deeper analysis of the different alternative designs for
MD-HBase shows that the TPB designs result in better
performance. The TS designs often result in high disk contention since some buckets are co-located in the same data

TPB/Kd

TPB/Quad

TS/Kd

TS/Quad

RPB/KdResponse Time(sec)

15

10

5

0

1

10
100
1K
Number of Nearest Neighbours

10K

Fig. 10. Response time for kNN query processing as a function of thenumber of neighbors returned.

partition of the underlying Key-value store. Even though we
randomize the bucket scan order in the TS design, significant
reduction in disk access contention is not observed. The TPB
designs therefore outperform the TS designs. For queries withhigh selectivity, the RPB design has a longer response timecompared to other designs; this however is an artifact of our
implementation choice for the RPB design. In the RPB design,
we override the pivot calculation for a bucket split and delegate
the bucket maintenance task to HBase which minimizes theinsert overhead. However, since HBase stores bucket boundary
information in the serialized form, the index lookup for query
processing must de-serialize the region boundaries. As a result,for queries with very high selectivity, the index lookup costdominates the total response time.
Comparing the K-d and the Quad trees, we observed better
performance of K-d trees for queries with high selectivity.
However, as the selectivity decreases, the response times for
Quad trees are lower. The K-d tree creates a smaller number ofbuckets while the Quad tree provides better pruning comparedto the K-d tree. In the case of high selectivity queries, subquery creation cost dominates the total response time; each
sub-query typically scans a short range and the time to scan abucket comprises a smaller portion of the total response time.
As a result, the K-d tree has better performance compared to
the Quad tree. On the other hand, in case of low selectivity
queries, the number of points to be scanned dominates thetotal response time since each sub-query tends to scan along range. The query performance therefore depends on thepruning power of the index structure.
We also expect the bucket size to potentially effect overall
performance. Selecting a bucket size is a trade-off between theinsertion throughput and query performance. Larger buckets
reduce the frequency of bucket splits thus improving insertion
throughput but limits sub-space pruning power during query
processing.
C. kNN Query
We now evaluate the performance of MD-HBase for k
Nearest Neighbor (kNN) queries using the same dataset as
the previous experiment. Figure 10 plots the response time(in seconds) for kNN queries as a function of the numberof neighbors to be returned; we varied k as 1, 10, 100,
1,000, and 10,000. In this experiment, expansion of the searchregion did not occur for k ≤ 100, resulting in almost similar
performance for all the designs. The TPB/Quad design has thebest performance where the response time was around 250ms
while that of other designs is around 1500ms to 2000ms. As
we increase k to 1K and 10K, the response times also increase;
however, the increase is not exponential, thanks to the bestfirst search algorithm used. For example, when we increased
k from 1K to 10K, the response time increased only by threetimes in the worst case.
The TPB/Quad design outperformed the other designs fork ≤ 100. Due to the larger fan-out, the bucket size of a Quadtree tends to be smaller than that of a K-d tree. As a result,
TPB/Quad has smaller bucket scan times compared to that of
the TPB/Kd design. However, both TS designs have almost
similar response times for small k. We attribute this to otherfactors like the bucket seek time. Since the TPB designs use
different tables for every bucket, a scan for all points in abucket does not incur a seek to the first point in the bucket.
On the other hand, the TS designs must seek to the first entry
corresponding to a bucket when scanning all points of thebucket. As mentioned earlier, the RPB design has a high index
lookup overhead which increases the response time, especiallywhen k is large. This however is an implementation artifact;
in the future, we plan to explore other implementation choices
for RPB that can potentially improve its performance.
Comparing between the K-d tree and the Quad tree, Quadtrees have smaller response times for smaller k, while K-dtrees have smaller response times for larger k. For small valuesof k, the search region does not expand. Smaller sized buckets
in a Quad tree result in better performance compared to larger
buckets in a K-d tree. On the other hand, for larger values ofk, the probability of a search region expansion is higher. Sincea Quad tree results in smaller buckets, it results in more searchregion expansions compared to that of K-d tree, resulting in
better performance of K-d tree.
Since the ZOrder and the MR systems do not have any index
structure, kNN query processing is inefficient. One possible
approach is to iteratively expand the queried region until thedesired k neighbors are retrieved. This technique is howeversensitive to a number of parameters such as the initial queried
range and the range expansion ratio. Due to the absenceof an index, there is no criterion to appropriately determine
the initial query region. We therefore do not include thesebaseline systems in our comparison; however, the performanceof ZOrder and MR is expected to be significantly worse thanthe proposed approaches.
VI. R ELATED WORK
Scalable data processing–both for large update volumes anddata analysis–has been an active area of interest in the last
few years. When dealing with a large volume of updates,
Key-value stores have been extremely successful in scaling tolarge data volumes; examples include Bigtable [5], HBase [6]etc. These data stores have a similar design philosophy where
they have made scalability and high availability as the primary
requirement, rich functionality being secondary. Even thoughthese systems are known to scale to terabytes of data, thelack of efficient multi-attribute based access limits their application for location based applications. On the other hand,when considering scalable data processing, MapReduce [7],[13] has been the most dominant technology, in addition toparallel databases [14]. Such systems have been proven toscale to petabytes of data while being fault-tolerant and highly
available. However, such systems are suitable primarily inthe context of batch processing. Furthermore, in the absenceof appropriate multi-dimensional indices, MapReduce styleprocessing has to scan through the entire dataset to answer
queries. MD-HBase complements both Key-value stores and
MapReduce style processing by providing an index structure
for multi-dimensional data. As demonstrated in our prototype,
our proposed indexing layer can be used directly with Keyvalue stores. Along similar lines, the index layer can also
be integrated with MapReduce to limit the retrieval of false
positives.
Our use of linearization for transforming multi-dimensional
data points to a single dimensional space has been used
recently in a number of other techniques. For instance, Jensen
et al. [15] use Z-ordering and Hilbert curves as space filling
curves and construct a B+ tree index using the linearized
values. Tao et al. [16] proposed an efficient indexing techniquefor high dimensional nearest neighbor search using a collectionof B-tree indices. The authors first use locality sensitive
hashing to reduce the dimensionality of the data points andthen apply Z-ordering to linearize the dataset, which is thenindexed using a B-tree index. Our approach is similar to theseapproaches, the difference being that we build a K-d tree anda Quad tree based index using the linearized data points. The
combination of the index layer and the data storage layer in
MD-HBase however resembles a B+ tree, reminiscent of the
Bigtable design. Subspace pruning in the index layer is key
to speeding up the range query performance which becomes
harder for data points with high dimensionality. In such cases,
dimensionality reduction techniques, as used by Tao et al. [16],can be used to improve the pruning power.
Another class of approaches make the traditional multidimensional indices more scalable. Wang et al. [17] and Zhang
et al. [18] proposed similar techniques where the systems
have two index layers: a global index and a local index.
The space is partitioned into several subspaces and each subspace is assigned a local storage. The global index organizes
subspaces and the local index organizes data points in thesubspace. Wang et al. [17] construct a content addressable
network (CAN) over a cluster of R-tree indexed databases
while Zhang et al. [18] use an R-tree as the global index anda K-d tree as the local index. Along these lines, MD-HBase
only has a global index; it can however be extended to add
local indices within the data storage layer.
VII. C ONCLUSION
Scalable location data management is critical to enable thenext generation of location based services. We proposed MD-

HBase, a scalable multi-dimensional data store supporting
efficient multi-dimensional range and nearest neighbor queries.
MD-HBase layers a multi-dimensional index structure overa range partitioned Key-value store. Using a design basedon linearization, our implementation layers standard index
structures like K-d trees and Quad trees. We implemented
our design on HBase, a standard open-source key-value store,
with minimal changes to the underlying system. The scalability
and efficiency of the proposed design is demonstrated througha thorough experimental evaluation. Our evaluation using acluster of nodes demonstrates the scalability of MD-HBase bysustaining insert throughput of over hundreds of thousands oflocation updates per second while serving multi-dimensional
range queries and nearest neighbor queries in real time withresponse times less than a second. In the future, we plan toextend our design by adding more complex analysis operatorssuch as skyline or cube, and exploring other alternative designs
for the index and data storage layers.
ACKNOWLEDGMENTS
The authors would like to thank the anonymous reviewers
for their helpful comments. This work is partly funded by NSF
grants III 1018637 and CNS 1053594.
R EFERENCES[1] http://en.wikipedia.org/wiki/List of mobile network operators, 2010.
[2] J. L. Bentley, “Multidimensional binary search trees used for associative
searching,” Commun. ACM, vol. 18, no. 9, pp. 509–517, 1975.
[3] R. A. Finkel and J. L. Bentley, “Quad trees: A data structure for retrieval
on composite keys,” Acta Inf., vol. 4, pp. 1–9, 1974.
[4] A. Guttman, “R-trees: a dynamic index structure for spatial searching,”
in SIGMOD, 1984, pp. 47–57.
[5] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, “Bigtable: A Distributed
Storage System for Structured Data,” in OSDI, 2006, pp. 205–218.
[6] “HBase: Bigtable-like structured storage for Hadoop HDFS,” 2010, http://hadoop.apache.org/hbase/.
[7] J. Dean and S. Ghemawat, “MapReduce: simplified data processing onlarge clusters,” in OSDI, 2004, pp. 137–150.
[8] G. M. Morton, “A computer oriented geodetic data base and a newtechnique in file sequencing,” IBM Ottawa, Canada, Tech. Rep., 1966.
[9] H. Samet, Foundations of Multidimensional and Metric Data Structures.
San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2005.
[10] S. Ramabhadran, S. Ratnasamy, J. M. Hellerstein, and S. Shenker,“Prefix hash tree: An indexing data structure over distributed hashtables,” Intel Research, Berkeley, Tech. Rep., 2004.
[11] S. Das, D. Agrawal, and A. El Abbadi, “G-Store: A Scalable Data Storefor Transactional Multi key Access in the Cloud,” in SOCC, 2010, pp.
163–174.
[12] T. Brinkhoff and O. Str, “A framework for generating network-based
moving objects,” Geoinformatica, vol. 6, p. 2002, 2002.
[13] “The Apache Hadoop Project,” http://hadoop.apache.org/core/, 2010.
[14] D. DeWitt and J. Gray, “Parallel database systems: the future of highperformance database systems,” CACM, vol. 35, no. 6, pp. 85–98, 1992.
[15] C. S. Jensen, D. Lin, and B. C. Ooi, “Query and update efficient b+tree based indexing of moving objects,” in VLDB. VLDB Endowment,
2004, pp. 768–779.
[16] Y. Tao, K. Yi, C. Sheng, and P. Kalnis, “Quality and efficiency in highdimensional nearest neighbor search,” in SIGMOD, 2009, pp. 563–576.
[17] J. Wang, S. Wu, H. Gao, J. Li, and B. C. Ooi, “Indexing multidimensional data in a cloud system,” in SIGMOD, 2010, pp. 591–602.
[18] X. Zhang, J. Ai, Z. Wang, J. Lu, and X. Meng, “An efficient multidimensional index for cloud data management,” in CloudDB, 2009, pp.
17–24.