Trade-offs Computing Minimum Hub Cover toward Optimized Labeled Graph Query Processing

As
techniques for graph query processing mature, the need for optimization is
increasingly becoming an imperative. Indices are one of the key ingredients
toward efficient query processing strategies via cost-based optimization. Due to the apparent absence
of a common representation model, it is difficult
to make a focused effort toward developing access structures, metrics
to evaluate query costs, and
choose alternatives. In this context, recent interests in covering-based graph matching appears to
be a promising direction of research. In this paper, our goal is to formally
introduce a new graph representation model, called Minimum Hub Cover, and demonstrate that
this representation offers interesting strategic advantages, facilitates construction of candidate graphs
from graph fragments, and helps leverage
indices in novel
ways for query
optimization. However, like other covering problems,
minimum hub cover is NP-hard, and thus is a natural candidate for optimization.
We claim that computing the minimum hub cover
leads to substantial cost reduction for graph query processing. We present a computational characterization of minimum
hub cover based
on integer programming to substantiate our claim and
investigate its computational cost on various graph types.