Efficient processing of k-hop reachability queries |
| |
Authors: | James Cheng Zechao Shang Hong Cheng Haixun Wang Jeffrey Xu Yu |
| |
Affiliation: | 1. Department of Computer Science and Engineering, The Chinese University of Hong Kong, New Territories, Hong Kong 2. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, New Territories, Hong Kong 3. Microsoft Research Asia, Beijing, China
|
| |
Abstract: | 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=\infty $ ). Existing indexes for processing classic reachability queries, as well as for processing shortest path distance queries, are not applicable or not efficient for processing $k$ -hop reachability queries. We propose an efficient index for processing $k$ -hop reachability queries. Our experimental results on a wide range of real datasets show that our method is efficient and scalable in terms of both index construction and query processing. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|