K-reach : who is in your small world
We study the problem of answering k-hop reachability queries in a directed graph, i.e., whether there exists a directed path of length k, from a source query vertex to a target query vertex in the input graph. The problem of k-hop reachability is a general problem of the classic reachability (where...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2014
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/102236 http://hdl.handle.net/10220/18931 http://dl.acm.org.ezlibproxy1.ntu.edu.sg/citation.cfm?id=2350247&dl=ACM&coll=DL |
| _version_ | 1826112408342495232 |
|---|---|
| author | Cheng, James Shang, Zechao Cheng, Hong Wang, Haixun Yu, Jeffrey Xu |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Cheng, James Shang, Zechao Cheng, Hong Wang, Haixun Yu, Jeffrey Xu |
| author_sort | Cheng, James |
| collection | NTU |
| description | We study the problem of answering k-hop reachability queries in a directed graph, i.e., whether there exists a directed path of length k, from a source query vertex to a target query vertex in the input graph. The problem of k-hop reachability is a general problem of the classic reachability (where k = ∞). Existing indexes for processing classic reachability queries, as well as for processing shortest path queries, are not applicable or not efficient for processing k-hop reachability queries. We propose an index for processing k-hop reachability queries, which is simple in design and efficient to construct. Our experimental results on a wide range of real datasets show that our index is more efficient than the state-of-the-art indexes even for processing classic reachability queries, for which these indexes are primarily designed. We also show that our index is efficient in answering k-hop reachability queries. |
| first_indexed | 2024-10-01T03:06:31Z |
| format | Journal Article |
| id | ntu-10356/102236 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:06:31Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | ntu-10356/1022362020-05-28T07:18:03Z K-reach : who is in your small world Cheng, James Shang, Zechao Cheng, Hong Wang, Haixun Yu, Jeffrey Xu School of Computer Engineering DRNTU::Engineering::Computer science and engineering We study the problem of answering k-hop reachability queries in a directed graph, i.e., whether there exists a directed path of length k, from a source query vertex to a target query vertex in the input graph. The problem of k-hop reachability is a general problem of the classic reachability (where k = ∞). Existing indexes for processing classic reachability queries, as well as for processing shortest path queries, are not applicable or not efficient for processing k-hop reachability queries. We propose an index for processing k-hop reachability queries, which is simple in design and efficient to construct. Our experimental results on a wide range of real datasets show that our index is more efficient than the state-of-the-art indexes even for processing classic reachability queries, for which these indexes are primarily designed. We also show that our index is efficient in answering k-hop reachability queries. 2014-03-20T09:07:47Z 2019-12-06T20:52:05Z 2014-03-20T09:07:47Z 2019-12-06T20:52:05Z 2012 2012 Journal Article Cheng, J., Shang, Z., Cheng, H., Wang, H., & Yu, J. X. (2012). K-reach: who is in your small world. Proceedings of the VLDB Endowment, 5(11), 1292-1303. https://hdl.handle.net/10356/102236 http://hdl.handle.net/10220/18931 http://dl.acm.org.ezlibproxy1.ntu.edu.sg/citation.cfm?id=2350247&dl=ACM&coll=DL en Proceedings of the VLDB endowment © 2012 VLDB Endowment. |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Cheng, James Shang, Zechao Cheng, Hong Wang, Haixun Yu, Jeffrey Xu K-reach : who is in your small world |
| title | K-reach : who is in your small world |
| title_full | K-reach : who is in your small world |
| title_fullStr | K-reach : who is in your small world |
| title_full_unstemmed | K-reach : who is in your small world |
| title_short | K-reach : who is in your small world |
| title_sort | k reach who is in your small world |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/102236 http://hdl.handle.net/10220/18931 http://dl.acm.org.ezlibproxy1.ntu.edu.sg/citation.cfm?id=2350247&dl=ACM&coll=DL |
| work_keys_str_mv | AT chengjames kreachwhoisinyoursmallworld AT shangzechao kreachwhoisinyoursmallworld AT chenghong kreachwhoisinyoursmallworld AT wanghaixun kreachwhoisinyoursmallworld AT yujeffreyxu kreachwhoisinyoursmallworld |