Reachability Indexing for Large-Scale Graphs: Studies and Forecasts

Fu Lizhen; Meng Xiaofeng

doi:10.7544/issn1000-1239.2015.20131567

Journal of Computer Research and Development > 2015 > 52(1): 116-129. > DOI: 10.7544/issn1000-1239.2015.20131567 CSTR: 32373.14.issn1000-1239.2015.20131567

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:

PDF (3239 KB)

Reachability Indexing for Large-Scale Graphs: Studies and Forecasts

Fu Lizhen^1,2,
Meng Xiaofeng²

¹(School of Software, North University of China, Taiyuan 030051)
²(School of Information, Renmin University of China, Beijing 100872)

More Information

Published Date: December 31, 2014

Graphical Abstract

Abstract

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.
- reachability,
- indexing,
- query processing,
- labeling,
- graph data

FullText(HTML)

References (0)

[1]	Bai Xuefei, Wang Wenjian, Liang Jiye. An Active Contour Model Based on Region Saliency for Image Segmentation[J]. Journal of Computer Research and Development, 2012, 49(12): 2686-2695.
[2]	Long Jianwu, Shen Xuanjing, and Chen Haipeng. Interactive Document Images Thresholding Segmentation Algorithm Based on Image Regions[J]. Journal of Computer Research and Development, 2012, 49(7): 1420-1431.
[3]	Liu Zhe, Song Yuqing, Chen Jianmei, Xie Conghua, Song Wenshan. Image Segmentation Based on Non-Parametric Mixture Models of Chebyshev Orthogonal Polynomials of the Second Kind[J]. Journal of Computer Research and Development, 2011, 48(11): 2008-2014.
[4]	Zhu Feng, Luo Limin, Song Yuqing, Chen Jianmei, Zuo Xin. Adaptive Spatially Neighborhood Information Gaussian Mixture Model for Image Segmentation[J]. Journal of Computer Research and Development, 2011, 48(11): 2000-2007.
[5]	Chen Yunjie, Zhang Jianwei, Wang Shunfeng, Zhan Tianming. Brain MR Image Segmentation Based on Anisotropic Wells Model[J]. Journal of Computer Research and Development, 2010, 47(11): 1878-1885.
[6]	Wang Wenhui, Feng Qianjin, Chen Wufan. Segmentation of Brain MR Images Based on the Measurement of Difference of Mutual Information and Gauss-Markov Random Field Model[J]. Journal of Computer Research and Development, 2009, 46(3): 521-527.
[7]	Shi Chunqi, Shi Zhiping, Liu Xi, Shi Zhongzhi. Image Segmentation Based on Self-Organizing Dynamic Neural Network[J]. Journal of Computer Research and Development, 2009, 46(1): 23-30.
[8]	Chen Yunjie, Zhang Jianwei, Wei Zhihui, Xia Desheng, Heng Pheng Ann. Brain MRI Segmentation Using the Active Contours Based on Gaussian Mixture Models[J]. Journal of Computer Research and Development, 2007, 44(9): 1595-1603.
[9]	Shi Chengxian, Wang Hongyuan, Heng Pheng Ann, Xia Deshen. A Parametric Active Contour Model for Medical Image Segmentation Using Priori Shape Force Field[J]. Journal of Computer Research and Development, 2006, 43(12): 2131-2137.
[10]	Zhang Jianwei, Xia Deshen. An Image Segmentation Model Based on Dual Level Sets[J]. Journal of Computer Research and Development, 2006, 43(1): 120-125.