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

《大规模图数据可达性索引技术：现状与展望.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机研究与发展D()I：10．7544／issnlOOO一1239．2015．20131567JournalofCompulerResearchandDevelopment52(1)：116l29，20l5大规模图数据可达性索引技术：现状与展望富丽贞。’孟小峰(巾北大学软件学院太原030051)(中国人民大学信息学院北京100872)(fulizhen303@l63．corD_)ReachabilityIndexingforLarge—ScaleGraphs：StudiesandForecastsFuIAzhen’and

2、MengXiaofeng(S(hool0，So，tZgPar{?，NorthUniversityofChina，Taiyuan030051)2tSchooln{Information，RenmfnUnz'ver．~z't．y()fChina，Beijing100872AbstractWiththerapiddevelopmentofsocialnetworks，biology，ontologyandotheremergingareas，therearealotofgraphdatainrealapplications．Re

3、achabilityqueryisoneofthefundamentalqueriesingraphs．Forsmallgraphs，depth—firstsearch(DFS)orreachabilitytransitiveclosurecananswerreacbabilityqueryeasily．However，asgraphsbecomelargerandlarger，abovetwoapproachesarenOlongerfeasible，becausethequerytimeofDFSisverylonga

4、ndthestoragecostofreachabilitytransitiveclosureisveryhigh．Therefore，lotsofreachabilityindiceshavebeenproposed．Theseapproacheshavebeenwidelyappliedinmanyareasofcomputerscience，suchassoftwareengineering，programminglanguages，distributedcomputing，socialnetworkanalysis

5、，biologicalnetworkanalysis，XMIdatabase，RDFdatabases，routingplanningandotherfields．Inaddition，reaehabilityindicescanalsospeedupothergraphalgorithms，suchastheshortestpathqueriesandsubgraphmatching．Inthissurvey。applicationsofreachabilityindexingschemesareintroducedfi

6、rstly．Secondly，accordingtosupportedgraphsize，supportedgraphtypeandsupportedquerytype，weprovidetaxonomyofexistingworks．Then。weprovideacomparisonofrepresentativeworks．Finally，wediscussthedisadvantagesofexistingscalablereachabilityindexingschemesandputforwardsomesugg

7、estionsforfutureresearchworks．Keywordsreachability；indexing；queryprocessing；labeling；graphdata摘要随着社交网络、生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据．可达性查询是有向图上一类最基本的查询．当图的规模非常小时，利用深度优先遍历(depthfirstsearch，DFS)或可达性传递闭包可以很容易处理可达性查询．但是，随着图的规模越变越大，由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太

8、大，这2种方法不再适用．因此，许多可达性索引方法相继被提出．这些方法已经被广泛应用于多个计算机科学领域，如软件工程、编程语言、分布式计算、社交网络分析、生物网络分析、XMI和RDF数据库、路由规划等领域．此外，可达性索引还可用于加速其他图算法，如最短路径查询和子图模式匹配．首先介绍了可达性索引的应用背景