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 costbased 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 coveringbased 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 NPhard, 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.
graph query processing, minimum hub cover problem, linear relaxation, greedy algorithm, subgraph isomorphism
Birincil Dil  İngilizce 

Konular  Fen 
Bölüm  Research Article 
Yazarlar 

Yayımlanma Tarihi  1 Temmuz 2018 
Başvuru Tarihi  1 Temmuz 2018 
Kabul Tarihi  
Yayınlandığı Sayı  Yıl 2018, Cilt 9, Sayı 33 
0216 355 56 19 WhatsApp numarasıyla iletişime geçebilirsiniz.
Bu dergideki makaleler Creative Commons AtıfAynıLisanslaPaylaş 4.0 Uluslararası Lisansı ile lisanslanmıştır.