Utilizing community centers to answer reachability queries for large graphs

Yifei Zhang; Guoren Wang; Changkuan Zhao; Ende Zhang

doi:10.1109/WISA.2013.47

Utilizing community centers to answer reachability queries for large graphs

Yifei Zhang, Guoren Wang, Changkuan Zhao, Ende Zhang

Research output: Contribution to conference › Paper › peer-review

1 Citation (Scopus)

Abstract

As a fundamental problem, reach ability query has been always the research emphasis in many applications in the near 20 years. Especially with the coming of the big data era, its efficiency plays a critical role. Although there are many research results for this issue, they all reach a scalability bottleneck. In this paper, we propose an index structure utilizing community center, i.e. to select a group of vertices from the original graph and construct a sub graph. With this sub graph, we can answer reach ability queries rapidly. The experimental result shows that our approach is superior to the-state-of-the-art algorithms including construction time, index size and query time.

Original language	English
Pages	205-210
Number of pages	6
DOIs	https://doi.org/10.1109/WISA.2013.47
Publication status	Published - 2013
Externally published	Yes
Event	2013 10th Web Information System and Application Conference, WISA 2013 - Yangzhou, Jiangsu, China Duration: 1 Nov 2013 → 3 Nov 2013

Conference

Conference	2013 10th Web Information System and Application Conference, WISA 2013
Country/Territory	China
City	Yangzhou, Jiangsu
Period	1/11/13 → 3/11/13

Keywords

Community center
Reachability query
Reachability trunk

Access to Document

10.1109/WISA.2013.47

Cite this

@conference{a22fc8c566b14a50ad8c5d7a20a39832,

title = "Utilizing community centers to answer reachability queries for large graphs",

abstract = "As a fundamental problem, reach ability query has been always the research emphasis in many applications in the near 20 years. Especially with the coming of the big data era, its efficiency plays a critical role. Although there are many research results for this issue, they all reach a scalability bottleneck. In this paper, we propose an index structure utilizing community center, i.e. to select a group of vertices from the original graph and construct a sub graph. With this sub graph, we can answer reach ability queries rapidly. The experimental result shows that our approach is superior to the-state-of-the-art algorithms including construction time, index size and query time.",

keywords = "Community center, Reachability query, Reachability trunk",

author = "Yifei Zhang and Guoren Wang and Changkuan Zhao and Ende Zhang",

year = "2013",

doi = "10.1109/WISA.2013.47",

language = "English",

pages = "205--210",

note = "2013 10th Web Information System and Application Conference, WISA 2013 ; Conference date: 01-11-2013 Through 03-11-2013",

}

TY - CONF

T1 - Utilizing community centers to answer reachability queries for large graphs

AU - Zhang, Yifei

AU - Wang, Guoren

AU - Zhao, Changkuan

AU - Zhang, Ende

PY - 2013

Y1 - 2013

N2 - As a fundamental problem, reach ability query has been always the research emphasis in many applications in the near 20 years. Especially with the coming of the big data era, its efficiency plays a critical role. Although there are many research results for this issue, they all reach a scalability bottleneck. In this paper, we propose an index structure utilizing community center, i.e. to select a group of vertices from the original graph and construct a sub graph. With this sub graph, we can answer reach ability queries rapidly. The experimental result shows that our approach is superior to the-state-of-the-art algorithms including construction time, index size and query time.

AB - As a fundamental problem, reach ability query has been always the research emphasis in many applications in the near 20 years. Especially with the coming of the big data era, its efficiency plays a critical role. Although there are many research results for this issue, they all reach a scalability bottleneck. In this paper, we propose an index structure utilizing community center, i.e. to select a group of vertices from the original graph and construct a sub graph. With this sub graph, we can answer reach ability queries rapidly. The experimental result shows that our approach is superior to the-state-of-the-art algorithms including construction time, index size and query time.

KW - Community center

KW - Reachability query

KW - Reachability trunk

UR - http://www.scopus.com/inward/record.url?scp=84899077754&partnerID=8YFLogxK

U2 - 10.1109/WISA.2013.47

DO - 10.1109/WISA.2013.47

M3 - Paper

AN - SCOPUS:84899077754

SP - 205

EP - 210

T2 - 2013 10th Web Information System and Application Conference, WISA 2013

Y2 - 1 November 2013 through 3 November 2013

ER -

Utilizing community centers to answer reachability queries for large graphs

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this