Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, and subsequently allows for "near-constant time" responses to reachability queries.
Question: Is there a state-of-the-art data structure that has the following features: (1). Pre-processing time or time to build data structure is linear in number of edges or vertices. This can also be quadratic, as its a once-off process. (2). Has linear space complexity (3). Can answer reachability queries in O(1) time (or even logarithmic time)?
The paper I found which mentioned some structures --> http://www.vldb.org/pvldb/vol7/p1191-wei.pdf
The trade-off between properties (1)-(3), would be that we want to optimize (3), then (2) to the best possible, while (1) is still important but can be rated lowest. So, optimize (3) > (2) > (1).
The worst case would be to do a BFS/DFS for every single query. The other extreme is to pre-compute reachability for every pair of vertices, but then storage would be O(n^2) in a matrix.