Key Formulation Schemes for Spatial Index in Cloud Data Managements
- 1 July 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2012 IEEE 13th International Conference on Mobile Data Management
Abstract
Due to the flexibility and scalability in cloud computing, cloud computing nowadays plays an important role to handle a large-scale data analysis. For data processing operations, several cloud data managements (CDMs), such as HBase and Cassandra, are developed. Such CDMs usually provide key-value storages, where each key is used to access its corresponding value. Both HBase and Cassandra provide some basic operations (e.g., Get, Scan) to retrieve the values via keys specified by users. The exiting CDMs fully inherit the characteristics of cloud computing (i.e., high scalability and availability). With the aforementioned characteristics of cloud computing, CDMs are widely employed for Web data, especially for search engines. However, with the proliferation of smart phones and location-based services, data with spatial information, referring as spatial data, are dramatically increasing. Consequently, how to formulate keys for spatial data in the existing CDMs is a challenge issue. In this paper, we develop several key formulation schemes. In particular, we propose a novel Key formulation scheme based on R+-tree (abbreviated as KR+-index). With our design for keys of spatial data, the existing CDMs are able to efficiently retrieve spatial data. In light of KR+-tree, two spatial queries, k-NN query and range query, are designed. Moreover, we implement the proposed key formulation schemes on HBase and Cassandra, and import real spatial data for spatial queries. The experimental results demonstrate that KR+-tree outperforms other existing key formulations and MD-HBase.Keywords
This publication has 9 references indexed in Scilit:
- MD-HBase: A Scalable Multi-dimensional Data Infrastructure for Location Aware ServicesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- CassandraACM SIGOPS Operating Systems Review, 2010
- SQL databases v. NoSQL databasesCommunications of the ACM, 2010
- BigtableACM Transactions on Computer Systems, 2008
- R-treesPublished by Association for Computing Machinery (ACM) ,1984
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974
- Space-filling curves: Their generation and their application to bandwidth reductionIEEE Transactions on Information Theory, 1969
- Convergence with Hilbert's space filling curveJournal of Computer and System Sciences, 1969