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

construct the index structure and have designed the key for effi cient data
access. In addition, we have redefi ned the spatial query algorithm, including
range query and k -NN query for our KR + . KR + took the characteristics of
these CDMs into account so that it is shows much more effi cient than other
index methods in experimentation. Our evaluation using a cluster of 8
nodes handles the range queries and k -NN queries effi ciently, and we also
compared it with the state-of-the-art, MD-HBase, and the result showed that
KR + has better performance than MD-HBase, especially for skewed data. In
this chapter, we study the settings of the parameters (i.e., M, m and o) of the
proposed index method in an empirical way. However, in the real world,
there are different data distributions (such as skewed data) and different
data sizes. To achieve a better performance, the parameters of the proposed
index method may need to be changed when the data distribution or the data
size varies. To apply the proposed index method to real-world data well,
we will study how to set proper parameters of the proposed index method
with respect to different data distributions and different data sizes in the
future. In addition, ad-hoc queries in the real world would have various
ranges, and different query rectangles would affect the performance. Thus,
we will study the effect of different query rectangles on the performance
and study proper parameter settings for ad-hoc queries.
References
Beckmann, N., H.P. Kriegel, R. Schneider and B. Seeger. 1990. The r*-tree: an effi cient and robust
access method for points and rectangles. Proc. of the 1990 ACM SIGMOD international
conference on Management of data. 322-331.
Bentley, J.L. 1975. Multidimensional binary search trees used for associative searching. Com-
munications of the ACM. 18(9): 509-517.
Chang, F., J. Dean, S. Ghemawat, W.C. Hsieh, D.A. Wallach, M. Burrows, T. Chandra, A. Fikes
and R.E. Gruber. 2008. Bigtable: A distributed storage system for structured data. ACM
Transactions on Computer Systems. 26(2): 1-26.
Finkel, R.A. and J.L. Bentley. 1974. Quad trees a data structure for retrieval on composite keys.
Actainformatica. 4(1): 1-9.
Gray, J. 1981. The transaction concept: Virtues and limitations. Proc. of the Very Large Database
Conference. 144-154.
Guttman, A. 1984. R-trees: a dynamic index structure for spatial searching. Proc. of the 1984
ACM SIGMOD International Conference on Management of Data. 47-57.
Kamel, I. and C. Faloutsos. 1994. Hilbert r-tree: An improved r-tree using fractals. Proc. of the
20th International Conference on Very Large Data Bases. 500-509.
Khetrapal, A. and V. Ganesh. 2008. Hbase and hypertable for large scale distributed storage
systems. Dept. of Computer Science, Purdue University.
Lakshman, A. and P. Malik. 2010. Cassandra: a decentralized structured storage system.
ACMSIGOPS Operating Systems Review. 44(2): 35-40.
Liao, H., J. Han and J. Fang. 2010. Multi-dimensional index on hadoop distributed fi le
system. Proc. of the Fifth IEEE International Conference on Networking, Architecture
and Storage. 240-249.