Computer Science ›› 2018, Vol. 45 ›› Issue (7): 42-52.doi: 10.11896/j.issn.1002-137X.2018.07.007

• CCF Big Data 2017 • Previous Articles     Next Articles

R-tree for Frequent Updates and Multi-user Concurrent Accesses Based on HBase

WANG Bo-tao,LIANG Wei,ZHAO Kai-li,ZHONG Han-hui,ZHANG Yu-qi   

  1. School of Computer Science and Engineering,Northeastern University,Shenyang 110169,China
  • Received:2017-07-15 Online:2018-07-30 Published:2018-07-30

Abstract: Application based on location based service (LBS) has entered the era of big data.Traditional location based service techniques face new challenges such as scalability,performance,etc.Cloud computing technology is the basis of big data processing and index is an important way to optimize query.Although there exist a large number of research results,as far as we know,there is no R-tree index which supports frequent updates and multi-user concurrent accesses based on HBase.According to the above characteristics of moving objects,this paper proposed a new R-tree index which supports frequent updates and multi-user concurrent accesses based on HBase.In this new index,the R-tree only indexes the grid which contains the moving object to avoide the problem of frequent updating effectively.Furthermore,based on the organization of HBase data rows and I/O characteristics of data partitions,this paper reorganized the nodes and encoded the grid cells with z-order,which reduce the read and write operations of HBase and improve the query efficiency.Finally,it proposed an optimization strategy for distributed read and write locks based on Zookeeper,which improves the throughput of new indexes.The experimental results show that the query throughput of the proposed strategy is improved by 25%~50% and the update throughput is about the same level in the case of uneven data compared with the grid index.Compared with the index using distri-buted shared locks,the query throughput of the index using distributed read and write locksis increased by nearly 40%.

Key words: HBase, Location based service, Moving object index, R-tree

CLC Number: 

  • TP315
[1]KHAN A U R,OTHMAN M,MADANI S A,et al.A Survey of Mobile Cloud Computing Application Models.IEEE Communications Surveys & Tutorials,2014,16(1):393-413.
[2]WOLFSON O.Moving Objects Information Management:TheDatabase Challenge[M]∥Next Generation Information Technologies and Systems.Springer Berlin Heidelberg,2002:75-89.
[3]WANG S,WANG H J,QIN X P,et al.Architecture of Big Data:Challenges, Status and Prospects.Chinese Journal of Computers,2011,34(10):1741-1752.(in Chinese)
王珊,王会举,覃雄派,等.架构大数据:挑战、现状与展望.计算机学报,2011,34(10):1741-1752.
[4]CARSTOIU D,LEPADATU E,GASPAR M.Hbase-non SQL Database,Performances Evaluation.International Journal of Advancements in Computing Technology,2010,2(5):42-52.
[5]ZHOU X,ZHANG X,WANG Y,et al.Efficient DistributedMulti-dimensional Index for Big Data Management[M]∥Web-Age Information Management.Springer Berlin Heidelberg,2013:130-141.
[6]TAKASU A.An Efficient Distributed Index for Geospatial Databases∥Database and Expert Systems Applications.Springer International Publishing,2015:28-42.
[7]ZHOU X,LI H,ZHANG X,et al.ABR-Tree:An Efficient Distributed Multidimensional Indexing Approach for Massive Data∥International Conference on Algorithms and Architectures for Parallel Processing.Springer,Cham,2015:781-790.
[8]HUANG S,WANG B,ZHU J,et al.R-HBase:A Multi-dimensional Indexing Framework for Cloud Computing Environment[C]∥IEEE International Conference on Data Mining Workshop.IEEE,2015:569-574.
[9]HUANG S,WANG B,DENG S,et al.HMVR-tree:A Multi-version R-tree Based on HBase for Concurrent Access[M]∥Big Data Computing and Communications.Springer International Publishing,2016.
[10]XIA Y,HUANG Z,ZHANG X,et al.Parallel Indexing forPast,Current and Future Locations of Moving Objects∥International Conference on Service Sicence,Technology and Engineering.DEStech Publications,2016:20-27.
[11]DU N,ZHAN J,ZHAO M,et al.Spatio-temporal data index model of moving objects on fixed networks using hbase∥2015 IEEE International Conference on Computational Intelligence & Communication Technology (CICT).IEEE,2015:247-251.
[12]GEORGE L.HBase:The Definitive Guide.The People’s Posts and Telecommunications Press,2013.(in Chinese)
GEORGE L.Hbase权威指南.北京:人民邮电出版社,2013.
[13]Zookeeper.https://zookeeper.apache.org.
[14]WANG B T,ZHAO K L,CHANG L D,et al. OptimizationTechnique fot Continuous Range Query Based on Storm.Computer Science and Engineering,2017,39(1):1-14.(in Chinese)
王波涛,赵凯利,常立东,等.基于Storm的连续范围查询优化技术.计算机工程与科学,2017,39(1):1-14.
[15]Apache Storm.http://storm.apache.org.
[1] XU Jiang-feng and TAN Yu-long. Research on HBase Configuration Parameter Optimization Based on Machine Learning [J]. Computer Science, 2020, 47(6A): 474-479.
[2] HUANG De-ling,YAN Yu-song,PENG Da-qin. Geographic Routing Protocol Based on Prediction for Urban Vehicular Ad Hoc Networks [J]. Computer Science, 2019, 46(7): 74-80.
[3] LEI Xing-bang and FANG Jun. Mass Sensor Information Storage Infrastructure Based on Fusion Database [J]. Computer Science, 2016, 43(6): 68-71.
[4] SONG Hua-zhu, DUAN Wen-jun and LIU Xiang. Ontology Storage Model Based on HBase [J]. Computer Science, 2016, 43(6): 39-43.
[5] HU Bo and TAN Liang. Optimization of Communication Performance of RPC Client in HBase Architecture [J]. Computer Science, 2016, 43(4): 97-101.
[6] PAN Qian, ZHANG Yu-ping and CHEN Hai-yan. Implementation of Parallel K-Nearest Neighbor Join Algorithm Based on CUDA [J]. Computer Science, 2016, 43(10): 190-192.
[7] LI Song, CUI Huan-yu, ZHANG Li-ping and JING Hai-dong. Static R-tree Building Method Based on Cure Clustering Algorithm [J]. Computer Science, 2015, 42(10): 193-197.
[8] . HBase Based Parallel BFS Method [J]. Computer Science, 2013, 40(3): 228-231.
[9] . DDR:A Multidimensional Case Retrieval Optimization Algorithm [J]. Computer Science, 2013, 40(3): 86-88.
[10] . Location Privacy Preserving Nearest Neighbor Querying Based on Coordinates Accumulation [J]. Computer Science, 2012, 39(8): 173-177.
[11] . Indoor Moving Objects Index Research Based on DR-tree [J]. Computer Science, 2012, 39(10): 177-181.
[12] WAN Ya-dong,WANG Qin,ZHANG Xiao-tong. System Level Analysis of Cluster-tree Based Wireless Sensor Network Design [J]. Computer Science, 2010, 37(8): 99-103.
[13] . [J]. Computer Science, 2009, 36(5): 68-71.
[14] . [J]. Computer Science, 2007, 34(5): 28-31.
[15] . [J]. Computer Science, 2007, 34(4): 102-103.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!