Trade-Offs Computing Minimum Hub Cover Toward Optimized Labeled Graph Query Processing

Online Academic Journal of Information Technology

Hasan M. Jamil¹  Kerem Bülbül²  Belma Yelbay²  Ş. İlker Birbil³ 

[1] Department of Computer Science, University of Idaho, USA;Department of Industrial Engineering, Sabancı University, Turkey;Econometric Institute, School of Economics, Erasmus University Rotterdam, The Netherlands;

关键词: graph query processing;    minimum hub cover problem;    linear relaxation;    greedy algorithm;    subgraph isomorphism;   

DOI  :  10.5824/1309-1581.2018.3.002.x

来源: DOAJ

【 摘 要 】

Astechniques for graph query processing mature, the need for optimization isincreasingly becoming an imperative. Indices are one of the key ingredientstoward efficient query processing strategies via cost-based optimization. Due to the apparent absenceof a common representation model, it is difficultto make a focused effort toward developing access structures, metricsto evaluate query costs, andchoose alternatives. In this context, recent interests in covering-based graph matching appears tobe a promising direction of research. In this paper, our goal is to formallyintroduce a new graph representation model, called Minimum Hub Cover, and demonstrate thatthis representation offers interesting strategic advantages, facilitates construction of candidate graphsfrom graph fragments, and helps leverageindices in novelways for queryoptimization. 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 coverleads to substantial cost reduction for graph query processing. We present a computational characterization of minimumhub cover basedon integer programming to substantiate our claim andinvestigate its computational cost on various graph types.

【 授权许可】

Unknown