基于HBase的多维索引查询机制的优化

doi:10.11772/j.issn.1001-9081.2019081462

《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 571-577.DOI: 10.11772/j.issn.1001-9081.2019081462

基于HBase的多维索引查询机制的优化

徐江峰, 谭玉龙()

郑州大学信息工程学院，郑州 450001

收稿日期:2019-08-22 修回日期:2019-11-04 接受日期:2019-11-18 发布日期:2019-12-04 出版日期:2020-02-10
通讯作者: 谭玉龙
作者简介:徐江峰（1965—），男，河南禹州人，教授，博士，CCF会员，主要研究方向：数据加密、网络安全；
基金资助:
中央高校基本科研业务费专项资助项目(20190605)

Optimization of multidimensional index query mechanism based on HBase

Jiangfeng XU, Yulong TAN()

School of Information Engineering，Zhengzhou University，Zhengzhou Henan 450001，China

Received:2019-08-22 Revised:2019-11-04 Accepted:2019-11-18 Online:2019-12-04 Published:2020-02-10
Contact: Yulong TAN
About author:XU Jiangfeng，born in 1965，Ph. D.， professor. His research interests include data encryption， network security.
Supported by:
the Fundamental Research Funds for the Central Universities(20190605)

摘要/Abstract

摘要：

键值存储旨在从非常大的数据量中提取值，同时具有高可用性、容错性和可伸缩性，因此提供了非常需要的基础设施来支持基于位置的服务（LBS）。然而，多维数据上的复杂查询不能有效地处理，因为键值存储不提供访问多个属性的方法。针对键值存储HBase不能有效处理多维数据的问题，提出了一个统一的索引框架——New-grid，使键值存储HBase支持多维查询。在改进的P-grid覆盖网络中，组织了一组节点，提供了高效的数据分布、容错和多维数据的查询处理。为了进行索引，使用基于Hilbert空间填充曲线来保存数据的局部性，从而有效地管理键值存储中的多维数据。同时使用HBase底层存储管理数据，并提出了一种范围查询和K最近邻查询的算法，以消除维护单独索引表的开销。在Amazon EC2上使用4、8和16个普通节点的集群进行了广泛的实验。实验结果表明，New-grid的性能相比MD-Hbase以及MapReduce更优。

关键词: 基于位置的服务, 多维索引, Hbase, 空间填充曲线, 覆盖网络

Abstract:

The key value store is designed to extract values from very large amounts of data and is highly available， fault-tolerant， and scalable， providing a much needed infrastructure to support Location-Based Service （LBS）. However， complex queries on multidimensional data cannot be processed effectively because the key value store does not provide a way to access multiple properties. For the key value storage， HBase cannot effectively deal with the problem of multidimensional data， a uniform indexing framework named New-grid was proposed. In the improved P-grid coverage network， a group of nodes was organized to provide efficient data distribution， fault tolerance and multi-dimensional data query processing. For indexing purposes， the locality of data storage based on Hilbert space filling curves was used to effectively manage the multidimensional data in the key value store. Simultaneously， HBase underlying storage was used to manage data， and an algorithm of range query and K-Nearest Neighbors （KNN） query were given to eliminate the overhead of maintaining separate index tables. Extensive experiments were conducted on Amazon EC2 using cluster sizes of 4， 8 and 16 normal nodes. Experimental results show that New-grid performance is more optimized than MD-HBase and MapReduce.

Key words: Location-Based Service (LBS), multidimensional index, HBase, space filling curve, coverage network

中图分类号:

TP391

徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 计算机应用, 2020, 40(2): 571-577.

Jiangfeng XU, Yulong TAN. Optimization of multidimensional index query mechanism based on HBase[J]. Journal of Computer Applications, 2020, 40(2): 571-577.

图/表 16

图1 二维空间及其等效一阶希尔伯特曲线

Fig. 1 Two-dimensional space and its equivalent first order Hilbert curve

图2 二维二阶Hilbert曲线

Fig. 2 Two-dimensional second-order Hilbert curve

图3 二维二阶Hilbert曲线的树表示

Fig. 3 Tree representation of two-dimensional second order Hilbert curve

图4 P-Grid字典树示例

Fig. 4 Example of P-Grid trie

图5 New-grid系统架构

Fig. 5 New-grid system architecture

图6 映射到二维Hilbert曲线的二阶点的范围查询示例

Fig. 6 Example of a range query on points mapped to two-dimensional second order Hilbert curve

图7 更改工作负载生成器数量的效果

Fig. 7 Effect of varying the number of workload generators

图8 点查询性能(D=3)

Fig. 8 Performance of point query (D=3)

图9 范围查询的性能(节点数为4,D=2)

Fig. 9 Performance of range query （number of nodes is 4， D=2）

图10 范围查询的性能（选择性 =10%,D=2）

Fig. 10 Performance of range query （selectivity =10%,?D=2）

图11 范围查询的性能（节点数为4，D=3）

Fig. 11 Performance of range query （number of nodes is 4， D=3）

图12 范围查询的性能（选择性=10%，D=3）

Fig. 12 Performance of range query （selectivity=10%， D=3）

图13 KNN查询的性能（节点数为4，D=2）

Fig. 13 Performance of KNN query （number of nodes is 4， D=2）

图14 KNN查询性能（k=10?000,?D=2）

Fig. 14 Performance of KNN query （k=10?000,?D=2）

图15 KNN查询的性能（节点数为4，D=3）

Fig. 15 Performance of KNN query （number of nodes is 4， D=3）

图16 KNN查询性能（k=10 000， D=3）

Fig. 16 Performance of KNN query （k=10 000， D=3）

参考文献 21

1	McMAHON M， STEKETEE C. Investigation of proposed applications for LBS enabled mobile handsets ［C］// Proceedings of the 2006 International Conference on Mobile Business. Washington， DC： IEEE Computer Society， 2006： 26. 10.1109/icmb.2006.27
2	GUTTMAN A. R-trees：a dynamic index structure for spatial searching［C］// Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1984： 47-57. 10.1145/602259.602266
3	FINKEL R A， BENTLEY J L. Quad trees a data structure for retrieval on composite keys ［J］. Acta Informatica，1974， 4（1）： 1-9. 10.1007/bf00288933
4	CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： a distributed storage system for structured data［J］. ACM Transactions on Computer Systems， 2008， 26（2）： 1-1-26. 10.1145/1365815.1365816
5	HBase ［2019-05-12］. . 10.1007/978-1-4842-2424-3_2
6	Apache. Apache Cassandra［2019-04-19］. . 10.1007/978-1-4842-3126-5_1
7	夏露.基于MapReduce的PageRank计算系统的设计与实现［D］.沈阳：东北大学，2011：22-24.
	XIA L. Design and implementation of a PageRank computing system based on MapReduce［D］. Shenyang： Northeast University， 2011： 22-24.
8	HILLERT D.Ueber die stetige Abbildung einer Line auf ein Flächenstück［J］. Mathematische Annalen， 1891， 38： 459-460. 10.1007/bf01199431
9	ABERER K， CUDRÉ-MAUROUX P， DATTA A， et al. P-Grid： a self-organizing structured P2P system［J］. ACM SIGMOD Record， 2003， 32（3）： 29-33. 10.1145/945721.945729
10	LI F， CHEN R， ZHOU C， et al. A novel geo-spatial image storage method based on Hilbert space filling curves［C］// Proceedings of the 2010 18th International Conference on Geoinformatics. Piscataway： IEEE， 2010： 1-4. 10.1109/geoinformatics.2010.5567999
11	PAVANAKUMAR M， KAUSHIK K N. Revisiting the space-filling curves for storage， reordering and partitioning mesh based data in scientific computing ［C］// Proceedings of the 2013 20th International Conference on High Performance Computing （HiPC）. Washington， DC： IEEE Computer Society， 2013， 1： 362-367. 10.1109/hipc.2013.6799097
12	HU C， ZHAO Y， WEI X， et al. ACTGIS： a Web-based collaborative tiled geospatial image map system［C］// Proceedings of the 2010 IEEE Symposium on Computers and Communications. Piscataway： IEEE， 2010： 521-528. 10.1109/iscc.2010.5546717
13	BUTZ A R. Alternative algorithm for Hilbert’s space-filling curve ［J］. IEEE Transactions on Computers， 1971， C-20（4）： 424-426. 10.1109/t-c.1971.223258
14	BIALLY T. Space-filling curves： their generation and their application to bandwidth reduction［J］. IEEE Transactions on Information Theory， 1969， 15（6）： 658-664. 10.1109/tit.1969.1054385
15	HAMILTON C H， RAU-CHAPLIN A. Compact Hilbert indices for multi-dimensional data［C］// Proceedings of the First International Conference on Complex， Intelligent and Software Intensive Systems. Washington， DC： IEEE Computer Society， 2007： 139-146. 10.1109/cisis.2007.16
16	田敬，代亚非.P2P持久存储研究［J］.软件学报，2007，18（6）：1379-1399. 10.1360/jos181379
	TIAN J， DAI Y F. Study on durable Peer-to-Peer storage techniques［J］. Journal of Software， 2007， 18（6）： 1379-1399. 10.1360/jos181379
17	ABERER K， DATTA A， HAUSWIRTH M： Indexing data-oriented overlay networks ［C］// Proceedings of the 31st International Conference on Very Large Data Bases. New York： ACM， 2005： 685-696.
18	TAO Y， ZHANG J， PAPADIAS D， et al. An efficient cost model for optimization of nearest neighbor search in low and medium dimensional space ［J］. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（10）： 1169-1184. 10.1109/tkde.2004.48
19	NISHIMURA S， DA S， AGRAWAL D， et al. MD-HBase： design and implementation of elastic infrastructure for cloud-scale location services［J］. Distributed and Parallel Databases， 2013， 31： 289-319. 10.1007/s10619-012-7109-z
20	COOPER B F， SILBERSTEIN A， TAM E， et al. Benchmarking cloud serving systems with YCSB［C］// Proceedings of the 1st ACM Symposium on Cloud Computing. New York： ACM， 2010： 143-154. 10.1145/1807128.1807152
21	CRAINICEANU A， LINGA P， MACHANAVAJJHALA A， et al. P-ring： an efficient and robust P2P range index structure［C］// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2007： 223-234. 10.1145/1247480.1247507

[1]	包玄, 陈红梅, 肖清. 融入时间的兴趣点协同推荐算法[J]. 计算机应用, 2021, 41(8): 2406-2411.
[2]	崔双双, 王宏志. 基于日志结构合并树的轻量级分布式索引实现方法[J]. 计算机应用, 2021, 41(3): 630-635.
[3]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[4]	付宇, 王红. 位置隐私保护的虚拟轨迹填充算法[J]. 计算机应用, 2019, 39(8): 2318-2325.
[5]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[6]	崔晨, 郑林江, 韩凤萍, 何牧君. 基于内存的HBase二级索引设计[J]. 计算机应用, 2018, 38(6): 1584-1590.
[7]	吴仁彪, 刘超, 屈景怡. 基于HBase和Hive的航班延误平台的存储方法[J]. 计算机应用, 2018, 38(5): 1339-1345.
[8]	李琰, 刘嘉勇. 基于作者主题模型和辐射模型的用户位置预测模型[J]. 计算机应用, 2018, 38(4): 939-944.
[9]	房俊, 李冬, 郭会云, 王嘉怡. 面向海量交通数据的HBase时空索引[J]. 计算机应用, 2017, 37(2): 311-315.
[10]	赵大鹏, 宋光旋, 靳远远, 王晓玲. 基于查询概率的位置隐私保护方法[J]. 计算机应用, 2017, 37(2): 347-351.
[11]	刘青, 付印金, 倪桂强, 梅建民. 基于Hadoop平台的分布式重删存储系统[J]. 计算机应用, 2016, 36(2): 330-335.
[12]	邳文君, 宫秀军. 基于Hadoop架构的数据驱动的SVM并行增量学习算法[J]. 计算机应用, 2016, 36(11): 3044-3049.
[13]	李振举, 李学军, 谢剑薇, 李雁南. 基于HBase的海量地形数据存储[J]. 计算机应用, 2015, 35(7): 1849-1853.
[14]	陆婷, 房俊, 乔彦克. 基于HBase的交通流数据实时存储系统[J]. 计算机应用, 2015, 35(1): 103-107.
[15]	陈曦曾华燊吴涛. 基于分布式哈希表的协作式Web服务组合[J]. 计算机应用, 2013, 33(05): 1197-1202.

基于HBase的多维索引查询机制的优化

Optimization of multidimensional index query mechanism based on HBase

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 21

相关文章 15

编辑推荐

Metrics