ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (1): 116-129.doi: 10.7544/issn1000-1239.2015.20131567

Previous Articles     Next Articles

Reachability Indexing for Large-Scale Graphs: Studies and Forecasts

Fu Lizhen1,2,Meng Xiaofeng2   

  1. 1(School of Software, North University of China, Taiyuan 030051); 2(School of Information, Renmin University of China, Beijing 100872)
  • Online:2015-01-01

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.

Key words: reachability, indexing, query processing, labeling, graph data

CLC Number: