• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

大规模图数据可达性索引技术：现状与展望

富丽贞, 孟小峰

富丽贞, 孟小峰. 大规模图数据可达性索引技术：现状与展望[J]. 计算机研究与发展, 2015, 52(1): 116-129. DOI: 10.7544/issn1000-1239.2015.20131567
引用本文: 富丽贞, 孟小峰. 大规模图数据可达性索引技术：现状与展望[J]. 计算机研究与发展, 2015, 52(1): 116-129. DOI: 10.7544/issn1000-1239.2015.20131567
shu
Fu Lizhen, Meng Xiaofeng. Reachability Indexing for Large-Scale Graphs: Studies and Forecasts[J]. Journal of Computer Research and Development, 2015, 52(1): 116-129. DOI: 10.7544/issn1000-1239.2015.20131567
Citation: Fu Lizhen, Meng Xiaofeng. Reachability Indexing for Large-Scale Graphs: Studies and Forecasts[J]. Journal of Computer Research and Development, 2015, 52(1): 116-129. DOI: 10.7544/issn1000-1239.2015.20131567
shu
富丽贞, 孟小峰. 大规模图数据可达性索引技术：现状与展望[J]. 计算机研究与发展, 2015, 52(1): 116-129. CSTR: 32373.14.issn1000-1239.2015.20131567
引用本文: 富丽贞, 孟小峰. 大规模图数据可达性索引技术：现状与展望[J]. 计算机研究与发展, 2015, 52(1): 116-129. CSTR: 32373.14.issn1000-1239.2015.20131567
shu
Fu Lizhen, Meng Xiaofeng. Reachability Indexing for Large-Scale Graphs: Studies and Forecasts[J]. Journal of Computer Research and Development, 2015, 52(1): 116-129. CSTR: 32373.14.issn1000-1239.2015.20131567
Citation: Fu Lizhen, Meng Xiaofeng. Reachability Indexing for Large-Scale Graphs: Studies and Forecasts[J]. Journal of Computer Research and Development, 2015, 52(1): 116-129. CSTR: 32373.14.issn1000-1239.2015.20131567
shu

大规模图数据可达性索引技术：现状与展望

  • 1(中北大学软件学院 太原 030051)

  • 2(中国人民大学信息学院 北京 100872) (fulizhen303@163.com)

基金项目: 国家自然科学基金项目(61379050, 91224008)|国家“八六三”高技术研究发展计划基金项目(2013AA013204)|高等学校博士学科点专项科研基金项目(20130004130001)
详细信息

  • 中图分类号: TP392

Reachability Indexing for Large-Scale Graphs: Studies and Forecasts

  • 1(School of Software, North University of China, Taiyuan 030051)

  • 2(School of Information, Renmin University of China, Beijing 100872)

摘要

    摘要
  • 摘要: 随着社交网络、生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时，利用深度优先遍历(depth-first search, DFS)或可达性传递闭包可以很容易处理可达性查询.但是，随着图的规模越变越大，由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大，这2种方法不再适用.因此，许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域，如软件工程、 编程语言、分布式计算、社交网络分析、 生物网络分析、XML和RDF数据库、路由规划等领域.此外，可达性索引还可用于加速其他图算法，如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着，依据支持的数据规模、数据类型以及查询类别，将现有可达性索引工作进行了分类，并对代表性工作进行分类比较；最后，讨论了现有的大规模图数据可达性索引方法存在的问题，并指出了未来的研究方向.
    Abstract: With the rapid development of social networks, biology, ontology and other emerging areas, there are a lot of graph data in real applications. Reachability query is one of the fundamental queries in graphs. For small graphs, depth-first search (DFS) or reachability transitive closure can answer reachability query easily. However, as graphs become larger and larger, above two approaches are no longer feasible, because the query time of DFS is very long and the storage cost of reachability transitive closure is very high. Therefore, lots of reachability indices have been proposed. These approaches have been widely applied in many areas of computer science, such as software engineering, programming languages, distributed computing, social network analysis, biological network analysis, XML database, RDF databases, routing planning and other fields. In addition, reachability indices can also speed up other graph algorithms, such as the shortest path queries and sub-graph matching. In this survey, applications of reachability indexing schemes are introduced firstly. Secondly, according to supported graph size, supported graph type and supported query type, we provide taxonomy of existing works. Then, we provide a comparison of representative works. Finally, we discuss the disadvantages of existing scalable reachability indexing schemes and put forward some suggestions for future research works.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(26)

  • 期刊类型引用(20)

    1. 韦修喜，彭茂松，黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化. 计算机应用. 2024(04): 1009-1017 . 百度学术
    2. 刘超敏，胡玉平. 基于VGG—19和卡尔曼预处理的WSNs测距方法. 传感器与微系统. 2023(10): 139-142 . 百度学术
    3. 刘松旭，张大鹏，乌云娜，刘鹏. 基于RSSI模型的无线传感器网络定位算法. 计算机仿真. 2022(01): 427-431 . 百度学术
    4. 崔焕庆，张娜，罗汉江. 基于改进鸽群算法的无线传感器网络定位方法. 传感技术学报. 2022(03): 399-404 . 百度学术
    5. 陈岩 ，高振国 ，王海军 ，欧阳云 ，缑锦 . 隐私保护能力可调的节点定位协议. 计算机研究与发展. 2022(09): 2075-2088 . 本站查看
    6. 刘琳岚，肖庭忠，舒坚，牛明晓. 基于门控循环单元的链路质量预测. 工程科学与技术. 2022(06): 51-58 . 百度学术
    7. 赵高丽，宋军平. 水下传感器网络自组织连通恢复仿真. 计算机仿真. 2021(03): 152-156 . 百度学术
    8. 刘恒，钟俊，刘辉. 基于优化核极限学习的WSN网络汇聚节点故障诊断. 新乡学院学报. 2021(06): 28-32 . 百度学术
    9. 石秦峰，徐祥涛，杨晓东. 基于节点汇聚链路模型的光纤传感器物联网节点控制. 激光杂志. 2021(07): 109-113 . 百度学术
    10. 张晶，罗施章，付谱平. 基于虚拟力移动锚节点的3D-DVHop-ACR定位算法. 控制与决策. 2021(10): 2409-2417 . 百度学术
    11. 张盛安，周洋，方浩，孙玉洁. 贵州电网贵阳供电局网络资源敏捷定位关键问题设计. 电力大数据. 2021(05): 79-85 . 百度学术
    12. 王礼霞，邰清清. 基于高阶马尔可夫链的无线传感器网络异常节点检测. 黑龙江工业学院学报(综合版). 2021(08): 93-97 . 百度学术
    13. 宰红斌，刘建国，唐保国，马建国，上官明霞，单荣荣. 基于WSN的输电线路状态监测与数据采集跨层优化方法. 电气工程学报. 2021(03): 161-169 . 百度学术
    14. 郑岚. 多信道通信网络环境下基于节点组簇技术通信资源调度算法. 山西能源学院学报. 2021(05): 97-99 . 百度学术
    15. 徐逸夫，段隆振. 基于蛙跳算法的无线传感器网络节点重部署. 计算机仿真. 2021(10): 328-332 . 百度学术
    16. 宋亚磊. 基于虚拟引力约束的光纤传感器网络节点空洞智能修复算法研究. 传感技术学报. 2021(10): 1395-1400 . 百度学术
    17. 易柏言. 关于无线传感器网络的时间同步技术探究. 科技创新与应用. 2020(15): 152-153 . 百度学术
    18. 王林，刘盼. 基于卷积神经网络的行人目标检测系统设计. 计算机测量与控制. 2020(07): 64-68+96 . 百度学术
    19. 左伟伟. 基于微积分算子的网络节点发包概率分布研究. 电子设计工程. 2020(23): 116-119+124 . 百度学术
    20. 李庐，赵晓峰. 基于拓扑感知映射算法的传感器网络数据稳定传输方法. 湖南科技学院学报. 2020(05): 54-57 . 百度学术

    其他类型引用(6)

    • 资源附件(0)
计量
  • 文章访问数:  1800
  • HTML全文浏览量:  0
  • PDF下载量:  1502
  • 被引次数: 26
出版历程
  • 发布日期:  2014-12-31

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献(26)
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计