Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2020, Vol. 14 Issue (1) : 208-218    https://doi.org/10.1007/s11704-018-7030-3
RESEARCH ARTICLE
HGeoHashBase: an optimized storage model of spatial objects for location-based services
Jingwei ZHANG1,2, Chao YANG1,2, Qing YANG3(), Yuming LIN1, Yanchun ZHANG4
1. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China
2. Guangxi Cooperative Innovation Center of Cloud Computing and Big Data, Guilin University of Electronic Technology, Guilin 541004, China
3. Guangxi Key Laboratory of Automatic Measurement Technology and Instrument, Guilin University of Electronic Technology, Guilin 541004, China
4. Centre for Applied Informatics, College of Engineering and Science, Victoria University,Melbourne 8001, Australia
 Download: PDF(730 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Many location-based services need to query objects existing in a specific space, such as location-based tourism resource recommendation. Both a large number of spatial objects and the real-time object access requirements of location-based services pose a big challenge for spatial object storage and query management. In this paper, we propose HGeoHashBase, an improved storage model by integrating GeoHash with key-value structure, to organize spatial objects for efficient range queries. GeoHash is responsible for spatial encoding and key-value structure as underlying data storage. Both the similarity of the encodings for objects in the close geographical locations and the multi-version data mechanism are blended into the proposed model well. Considering the tradeoff between encoding precision and query performance, a theoretical proof is presented. Extensive experiments are designed and conducted, whose results show that the proposed model can gain significant performance improvement.

Keywords location-based services      distributed storage model      storage and access optimization     
Corresponding Author(s): Qing YANG   
Just Accepted Date: 15 November 2017   Online First Date: 04 September 2018    Issue Date: 24 September 2019
 Cite this article:   
Jingwei ZHANG,Chao YANG,Qing YANG, et al. HGeoHashBase: an optimized storage model of spatial objects for location-based services[J]. Front. Comput. Sci., 2020, 14(1): 208-218.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7030-3
https://academic.hep.com.cn/fcs/EN/Y2020/V14/I1/208
1 A Guttman. R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 1984, 47–57
https://doi.org/10.1145/602259.602266
2 N Beckmann, H P Kriegel, R Schneider, B Seeger . The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 1990, 322–331
https://doi.org/10.1145/93597.98741
3 F Chang, J Dean, S Ghemawat, W C Hsieh, D A Wallach, M Burrows, T Chandra, A Fikes, K E Gruber. Bigtable: a distributed storage system for structured data. In: Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation. 2006, 205–218
4 F Chang, J Dean , S Ghemawat, W C Hsieh, D A Wallach, M Burrows, T Chandra, A Fikes, K E Gruber. Bigtable: a distributed storage system for structured data. ACM Transactions on Computer Systems, 2008, 26(2): 4
https://doi.org/10.1145/1365815.1365816
5 A Lakshman, P Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating System Review, 2010, 44(2): 35–40
https://doi.org/10.1145/1773912.1773922
6 L Wang, C Q Cheng, S Z Wu, F L Wu, W Teng. Massive remote sensing image data management based on HBase and GeoSOT. In: Proceedings of IEEE International Geoscience and Remote Sensing Symposium. 2015, 4558–4561
https://doi.org/10.1109/IGARSS.2015.7326842
7 L Wang, B Chen, Y H Liu. Distributed storage and index of vector spatial data based on HBase. In: Proceedings of the 21st International Conference on Geoinformatics. 2013, 1–5
https://doi.org/10.1109/Geoinformatics.2013.6626052
8 J Dean, S Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 2008, 51(1): 107–113
https://doi.org/10.1145/1327452.1327492
9 A S Noghabi, S Subramanian, P Narayanan, S Narayanan, G Holla, M Zaldeh, T Li , I Gupta, R H Campbell. Ambry: linkedin’s scalable geo-distributed object store. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 253–265
https://doi.org/10.1145/2882903.2903738
10 A Shanbhag, A Jindal, Y Lu, S Madden. Amoeba: a shape changing storage system for big data. Proceedings of the VLDB Endowment, 2016, 9(13): 1569–1572
https://doi.org/10.14778/3007263.3007311
11 G DeCandia, D Hastorun, M Jampani, G Kakulapati, A Cakshman, A Pilchin, S Sivasubramanian, P, Vosshall W Vogels. Dynamo: Amazon’s highly available key-value store. In: Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles. 2007, 205–220
https://doi.org/10.1145/1294261.1294281
12 A Halevy, F Korn, N F Noy, C Olston, N Polyzotis, S Roy, S E Whang. Goods: organizing google’s datasets. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 795–806
https://doi.org/10.1145/2882903.2903730
13 H Samet, E R Webber. Storing a collection of polygons using quadtrees. ACM Transactions on Graphics, 1985, 4(3): 182–222
https://doi.org/10.1145/282957.282966
14 D Han, E Ztroulia. HGrid: a data model for large geospatial data sets in HBase. In: Proceedings of the IEEE International Conference on Cloud Computing. 2013, 910–917
https://doi.org/10.1109/CLOUD.2013.78
15 A Fox, C Eichelberger, J Hughes, S Lyon. Spatio-temporal indexing in non-relational distributed databases. In: Proceedings of the 2013 IEEE International Conference on Big Data. 2013, 291–299
https://doi.org/10.1109/BigData.2013.6691586
16 D Xie, F Li, B Yao, G F Li, L Zhou, M Y Guo. Simba: efficient inmemory spatial analytics. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 1071–1085
17 M J Tang, Y Y Yu, M Q Malluhi, M Ouzzani, G W Aref. Locationspark: a distributed in-memory data management system for big spatial data. Proceedings of the VLDB Endowment, 2016, 9(13): 1565–1568
https://doi.org/10.14778/3007263.3007310
18 R Fernandes, P Zaczkowski, B Göttler, C Ettinoffe, A Moussa. TrafficDB: here’s high performance shared-memory data store. Proceedings of the VLDB Endowment, 2016, 9(13): 1365–1376
https://doi.org/10.14778/3007263.3007274
19 S Lakshman, S Melkote, J Liang, R Mayuram. Nitro: a fast, scalable in-memory storage engine for NoSQL global secondary index. Proceedings of the VLDB Endowment, 2016, 9(13): 1413–1424
https://doi.org/10.14778/3007263.3007278
20 J J Liu, H R Li, Y Gao, H Yu, D Jiang. A Geohash-based index for spatial data management in distributed memory. In: Proceedings of the 22nd International Conference on Geoinformatics. 2014, 1–4
21 T Arnold. An entropy maximizing Geohash for distributed spatiotemporal database indexing. 2015, arXiv preprint arXiv:1506.05158
[1] Huiping LIU, Cheqing JIN, Aoying ZHOU. Popular route planning with travel cost estimation from trajectories[J]. Front. Comput. Sci., 2020, 14(1): 191-207.
[2] Zhefan ZHONG, Xin LIN, Liang HE, Jing YANG. Answering why-not questions on KNN queries[J]. Front. Comput. Sci., 2019, 13(5): 1062-1071.
[3] Xiao PAN, Xiaofeng MENG. Preserving location privacy without exact locations in mobile services[J]. Front Comput Sci, 2013, 7(3): 317-340.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed