吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (3): 911-916.doi: 10.13229/j.cnki.jdxbgxb201603035

• 论文 • 上一篇    下一篇

支持高效路径查询的数据空间索引方法

王念滨, 祝官文, 周连科, 王红卫   

  1. 哈尔滨工程大学 计算机科学与技术学院,哈尔滨 150001
  • 收稿日期:2014-11-28 出版日期:2016-06-20 发布日期:2016-06-20
  • 作者简介:王念滨(1967), 男,教授, 博士生导师.研究方向:数据空间,深度学习,并行计算, 机器学习等.E-mail:wangnianbin@hrbeu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61272185); 黑龙江省自然科学基金项目(F201238, F020510); 中央高校基本科研业务费专项项目(HEUCFZ1219, HEUCF100608,HEUCF100613).

Novel dataspace index for efficient processing of path query

WANG Nian-bin, ZHU Guan-wen, ZHOU Lian-ke, WANG Hong-wei   

  1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
  • Received:2014-11-28 Online:2016-06-20 Published:2016-06-20

RICH HTML

0   

PDF (PC)

151

摘要： 首先,通过索引连接例子,分析了影响效率的因素。在扩展倒排索引基础上,构建了B-树索引,以支持大规模数据的高效查找。然后,构建了二级索引,以减少索引连接中的大量重复判断。最后,提出了路径查询算法。实验结果表明:该索引方法能够有效地解决索引连接问题和显著地改善数据空间路径查询效率。

关键词: 计算机软件, 数据空间索引, 辅助索引, 索引连接, 路径查询

Abstract: A novel dataspace index method for efficient processing of path query is proposed. First, an example of joining the extended inverted index was illustrated to find the reason of inefficiency. Then, based on the extended inverted index, a B-tree index was built to efficiently search massive data. Furthermore, a secondary index was constructed in order to significantly reduce the number of repetitive comparisons with respect to index join process. Finally, a path query algorithm was presented based on the proposed dataspace index method. Experimental results show that the proposed method can not only efficiently deal with the problem of index join, but also significantly improve the performance of the path query in the dataspace.

Key words: computer software, dataspace index, auxiliary index, index join, path query

中图分类号: 

  • TP311.13
[1] Chen J C,Chen Y G,Du X Y,et al. Big data challenge: a data management perspective[J]. Frontiers of Computer Science,2013,7(2):157-164.
[2] Franklin M,Halevy A,Maier D. From databases to dataspaces: A new abstraction for information management[J]. SIGMOD Record,2005,34(4):27-33.
[3] Dong X,Halevy A. Indexing dataspaces[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data.United States:ACM,2007:43-54.
[4] Song S,Chen L. Indexing dataspaces with partitions[J]. World Wide Web,2013,16(2):141-170.
[5] Wang N, Du H, Xu B, et al. Compact indexes based on core content in personal dataspace management system[J]. Computing and Informatics,2014,33(2):281-302.
[6] Zhong M,Liu M,Bao Z,et al. MVP Index: Towards efficient known-item search on large graphs[C]∥Proceedings of the 18th International Conference on Database Systems for Advanced Applications.German:Springer Verlag,2013:193-200.
[7] Du F,Chen Y,Du X. Partitioned indexes for entity search over RDF knowledge bases[C]∥Proceedings of 17th International Conference on Database Systems for Advanced Applications.German:Springer Verlag,2012:141-155.
[8] Dittrich J P,Vaz Salles M A. iDM: a unified and versatile data model for personal dataspace management[C]∥Proceedings of International Conference on Very Large Data Bases. United States:ACM,2006:367-378.
[9] 王红滨,周连科,王念滨,等. 基于iMeMex数据模型的数据空间索引方法研究[J]. 计算机科学与探索,2014,8(1):61-72.
Wang Hong-bin,Zhou Lian-ke,Wang Nian-bin,et al. Research on data space index method based on iMeMex data model[J]. Journal of Frontiers of Computer Science and Technology,2014,8(1):61-72.
[10] 严蔚敏,吴为民. 数据结构:C语言版[M]. 北京:清华大学出版社,2001:238-246.
[1] 马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[2] 罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[3] 应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.
[4] 李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[5] 特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[6] 康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[7] 陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[8] 刘磊, 王燕燕, 申春, 李玉祥, 刘雷. Bellman-Ford算法性能可移植的GPU并行优化[J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[9] 冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[10] 李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[11] 王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[12] 黄宏涛，王静，叶海智，黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
[13] 范大娟1, 2, 黄志球1, 肖芳雄1, 祝义1, 王进1. 面向多服务交互的相容性分析与适配器生成[J]. 吉林大学学报(工学版), 2014, 44(4): 1094-1103.
[14] 贺秦禄1, 李战怀1, 王乐晓1, 王瑞2. 云存储系统聚合带宽测试技术[J]. 吉林大学学报(工学版), 2014, 44(4): 1104-1111.
[15] 康辉, 张双双, 梅芳. 一种递归π演算向Petri网的转换方法[J]. 吉林大学学报(工学版), 2014, 44(01): 142-148.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘松山, 王庆年, 王伟华, 林鑫. 惯性质量对馈能悬架阻尼特性和幅频特性的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] 王同建, 陈晋市, 赵锋, 赵庆波, 刘昕晖, 袁华山. 全液压转向系统机液联合仿真及试验[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[3] 张春勤, 姜桂艳, 吴正言. 机动车出行者出发时间选择的影响因素[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[4] 肖锐, 邓宗才, 兰明章, 申臣良. 不掺硅粉的活性粉末混凝土配合比试验[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
[5] 陈思国, 姜旭, 王健, 刘衍珩, 邓伟文, 邓钧忆. 车载自组网与通用移动通信系统混杂网络技术[J]. 吉林大学学报(工学版), 2013, 43(03): 706 -710 .
[6] 孟超, 孙知信, 刘三民. 基于云计算的病毒多执行路径[J]. 吉林大学学报(工学版), 2013, 43(03): 718 -726 .
[7] 仙树, 郑锦, 路兴, 张世鹏. 基于内容转发模型的P2P流量识别算法[J]. 吉林大学学报(工学版), 2013, 43(03): 727 -733 .
[8] 吕源治, 王世刚, 俞珏琼, 王小雨, 李雪松. 基于柱透镜光栅的虚模式下一维集成成像显示特性[J]. 吉林大学学报(工学版), 2013, 43(03): 753 -757 .
[9] 王丹, 李阳, 年桂君, 王珂. 非均质度量掩蔽函数在空域水印中的应用[J]. 吉林大学学报(工学版), 2013, 43(03): 771 -775 .
[10] 冯琳函, 钱志鸿, 尚克诚, 朱爽. 基于IEEE802.15.4标准的改进型隐藏节点冲突避免策略[J]. 吉林大学学报(工学版), 2013, 43(03): 776 -780 .
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发