Not checkedNot checked for notices yet.
Trade-Offs Computing Minimum Hub Cover Toward Optimized Labeled Graph Query Processing
Hasan M. Jamil, Kerem Bülbül, Ş. İlker Birbil and 1 more
Online Academic Journal of Information Technology · 2018
doi:10.5824/1309-1581.2018.3.002.x (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
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.
Abstract licence: CC BY-SA
References48
40 more references, whose wording the paper’s licence keeps private.
All 48 referencesReads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.