  Graph pattern cardinality estimation is the problem of estimating the number
of embeddings of a query graph in a data graph. This fundamental problem
arises, for example, during query planning in subgraph matching algorithms.
There are two major approaches to solving the problem: sampling and synopsis.
Synopsis (or summary)-based methods are fast and accurate if synopses capture
information of graphs well. However, these methods suffer from large errors due
to loss of information during summarization and inherent assumptions.
Sampling-based methods are unbiased but suffer from large estimation variance
due to large sample space.
  To address these limitations, we propose Alley, a hybrid method that combines
both sampling and synopses. Alley employs 1) a novel sampling strategy, random
walk with intersection, which effectively reduces the sample space, 2)
branching to further reduce variance, and 3) a novel mining approach that
extracts and indexes tangled patterns as synopses which are inherently
difficult to estimate by sampling. By using them in the online estimation
phase, we can effectively reduce the sample space while still ensuring
unbiasedness. We establish that Alley has worst-case optimal runtime and
approximation quality guarantees for any given error bound $\epsilon$ and
required confidence $\mu$. In addition to the theoretical aspect of Alley, our
extensive experiments show that Alley outperforms the state-of-the-art methods
by up to orders of magnitude higher accuracy with similar efficiency.

Databases