|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|