K-Reach: Who is in Your Small World
| Autor: | Cheng, James, Shang, Zechao, Cheng, Hong, Wang, Haixun, Yu, Jeffrey Xu |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 11, pp. 1292-1303 (2012) |
| Druh dokumentu: | Working Paper |
| Popis: | 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=infinity). 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. Comment: VLDB2012 |
| Databáze: | arXiv |
| Externí odkaz: |
|