0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Hoping for something better than DFS/BFS? $\endgroup$
    – Sasho Nikolov
    Dec 1, 2016 at 17:56
  • $\begingroup$ @SashoNikolov: Yes, I just edited my question with the paper I came across during my search, but I am not sure if this is really the state-of-the-art or are there better ones around. Was hoping for some graph theory guys to help out really. $\endgroup$
    – user43464
    Dec 2, 2016 at 4:51
  • 2
    $\begingroup$ Your question is unclear. If you only need to solve a single reachability query, I don't believe you can hope for anything better than running DFS. The paper you have linked solves the static data structure problem in which you want to pre-process the graph (possibly taking longer time than DFS) into a small-space data structure so that any reachability query can be answered fast. That can help if you want to solve multiple reachability queries, so that it makes sense to spend some time pre-processing. $\endgroup$
    – Sasho Nikolov
    Dec 2, 2016 at 15:52
  • 3
    $\begingroup$ Interesting topic. However, "what is the best one?" is not an answerable question, because what is best depends on your criteria / requirements / workload. Can you try rephrasing your question? What exactly are you trying to optimize for? There are probably many possible algorithms with non-trivial tradeoffs between preprocessing time, space, and per-query time, so you'll need to give us some idea how you plan to evaluate answers and how we should trade those off. $\endgroup$
    – D.W.
    Dec 3, 2016 at 9:31
  • 1
    $\begingroup$ @cbro: please edit your question so that it asks what you are actually looking for, as per your comment. $\endgroup$
    – András Salamon
    Dec 3, 2016 at 11:46

1 Answer 1

Reset to default
4
$\begingroup$

[Rooted trees with edges directed away from the root] are DAGs,
and from reachability on such a DAG, one can recover

the root as the unique vertex from which every other vertex is reachable
and
the tree by observing that x is adjacent to y if and only if [x≠y and [one of {x,y} is
reachable from the other of {x,y}] and [there is no vertex z such that [[z is not in {x,y}] and
[[x is reachable from z is reachable from y] or [y is reachable from z is reachable from x]]]]]

.


Thus, by this formula, there are ​ $n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(\hspace{-0.02 in}n^{n-2}\right)$ ​ distinct reachability oracles
for [rooted trees with edges directed away from the root].
$\log_2\hspace{-0.06 in}\left(n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(n^{n-2}\right)\hspace{-0.03 in}\right) \;\; = \;\; \log_2\hspace{-0.06 in}\left(\hspace{-0.02 in}n^{n-1}\right) \;\; = \;\; (n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n) \;\;$,
so any encoding of [reachability oracles for rooted trees with edges directed away from the root]
will need to use more than $\;\;\; \left((n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n)\right)-3 \;\;\;$ bits for more than 3/4 of such DAGs.



By this paper,
"has n1+o(1) space complexity" ​ and ​ "Can answer reachability queries in O(1) time"
are incompatible:

As described at the bottom of page 5 and the top of page 6,
"butterfly graph"s are directed acyclic.
Accordingly, all of their subgraphs are also DAGs.
By Theorem 1.2 and the two sentences after that,
for constant time, ​ ​ ​ "the space needs to be ​ $n^{1+\Omega \hspace{.02 in}(1)}$ ."



(I'm not aware of any positive results.)

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.