Proceedings of the VLDB Endowment · 2012 · 59 citations · 33 references
ComputingComputer ScienceAlgorithmsData StructuresDatabasesGraph AlgorithmsQuery OptimizationQuery ProcessingSearching AlgorithmsShortest Path AlgorithmsGraph IndexingGraph QueryingIndex-aware Query ProcessingIndexesReachabilityReachability AnalysisShortest Path In Directed GraphsShortest Path Problems
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.
33
The Structure and Function of Complex Networks
Michael Newman · SIAM Review · 2003 · 18.7K citations · Full text
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
R. K. Shyamasundar · Resonance · 1996 · 1.5K citations