We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
GRAIL: a scalable index for reachability queries in very large graphs.
- Authors
Yıldırım, Hilmi; Chaoji, Vineet; Zaki, Mohammed
- Abstract
Given a large directed graph, rapidly answering reachability queries between source and target nodes is an important problem. Existing methods for reachability tradeoff indexing time and space versus query time performance. However, the biggest limitation of existing methods is that they do not scale to very large real-world graphs. We present a simple yet scalable reachability index, called GRAIL, that is based on the idea of randomized interval labeling and that can effectively handle very large graphs. Based on an extensive set of experiments, we show that while more sophisticated methods work better on small graphs, GRAIL is the only index that can scale to millions of nodes and edges. GRAIL has linear indexing time and space, and the query time ranges from constant time to being linear in the graph order and size. Our reference C++ implementations are open source and available for download at .
- Subjects
OPEN source software; COMPUTER software; GRAPH theory; INFORMATION retrieval; ELECTRONIC data processing; COMPUTER industry
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2012, Vol 21, Issue 4, p509
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-011-0256-4