  Given a graph G and a query vertex q, the topic of community search (CS),
aiming to retrieve a dense subgraph of G containing q, has gained much
attention. Most existing works focus on undirected graphs which overlooks the
rich information carried by the edge directions. Recently, the problem of
community search over directed graphs (or CSD problem) has been studied; it
finds a connected subgraph containing q, where the in-degree and out-degree of
each vertex within the subgraph are at least k and l, respectively. However,
existing solutions are inefficient, especially on large graphs. To tackle this
issue, in this paper, we propose a novel index called D-Forest, which allows a
CSD query to be completed within the optimal time cost. We further propose
efficient index construction methods. Extensive experiments on six real large
graphs show that our index-based query algorithm is up to two orders of
magnitude faster than existing solutions.
