Spatial Index Schemes for Cloud Environments - Geographical Information Systems: Trends and Technologies - page 69

retrieves a list of map <key, columns> or <key, super columns> for specifi c
columns' names or super columns' names in a column family on each of the
given keys; get_range_slices : returns a list of map <key, columns> or <key,
super columns> within the range of keys in a column family; insert: inserts
a column in a column family or a super column family; batch_mutate :
inserts or removes the rows, the super columns or the columns from the
row specifi ed by keys; and remove : removes data from the row specifi ed
by a key in a column family or a super column family. The data could be
an entire row, a super column or a column.
However, these operations could not support the operation of retrieving
rows given two or more restrictions. For instance, in Table 6, we could not
retrieve the result that satisfi es “satisfyrest.name=Friday” and “uid= u 1 ”
using only one operation from the basic operations provided by HBase
or Cassandra. Although we could retrieve rows by scanning all rows and
post-fi lter unqualifi ed data to get the result, it is time-consuming.
Multi-dimensional Index
Due to the high scalability of cloud data managements, there have been
more and more works for constructing indexes on cloud data managements
recently. The B-tree is a commonly used index structure. The work in (Wu et
al. 2010) presented a scalable B-tree based indexing scheme which builds a
local B-tree for the dataset stored in each compute node and a Cloud Global
index, called the CG-index, to index each compute node. However, the B-tree
index can not support multi-dimensional queries effectively. Besides, much
of the work on R-tree index structures for multi-dimensional data had been
done, such as (Wang et al. 2010; Zhang et al. 2009; Liao et al. 2010). Wang et al.
(Wang et al. 2010) present RT-CAN, a multi-dimensional indexing scheme.
RT-CAN is built on top of local R-tree indexes and it dynamically selects a
portion of local R-tree nodes to publish onto the global index. Although it
uses R-tree indexing, it builds the R-tree on the authors' own distributed
system epiC. The work (Zhang et al. 2009) combined R-tree and k-d tree
to be the index structures and the work in (Liao et al. 2010) presented an
approach to construct a block-based hierarchical R-tree index structures.
These works all build an index structure on the Hadoop distributed fi le
system or Google's fi le system to support multi-dimensional queries.
MD-HBase (Nishimura et al. 2011; Nishimura et al. 2013) is a data
management system, based on HBase, using Quad trees and k-d trees
coupled with Z-ordering to index multi-dimensional data for LBSs. The
keys of MD-HBase are the Z-values of the dimensions being indexed. It uses
the trie-based approach for splitting equal-sized space, and builds Quad
tree and k-d tree index structures on the key-value data model. Moreover,
MD-HBase proposed a novel naming scheme, called longest common