Trade-offs computing minimum hub cover toward optimized labeled graph query processing

Yelbay, Belma and Birbil, Ş. İlker and Bülbül, Kerem and Jamil, Hasan M. (2018) Trade-offs computing minimum hub cover toward optimized labeled graph query processing. AJIT-e: Online Academic Journal of Information Technology, 9 (33). pp. 39-68. ISSN 1309-1581

This is the latest version of this item.

Full text not available from this repository. (Request a copy)

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.
Item Type: Article
Uncontrolled Keywords: Graph Management, Query Processing, Minimum Hub Cover
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 07 Aug 2019 20:13
Last Modified: 26 Apr 2022 10:08
URI: https://research.sabanciuniv.edu/id/eprint/38156

Available Versions of this Item

Actions (login required)

View Item
View Item