-

 

 

 




Optimization Online





 

Mathematical Programming Models Based on Hub Covers in Graph Query Processing

Belma Yelbay (byelbay***at***sabanciuniv.edu)
S. Ilker Birbil (sibirbil***at***sabanciuniv.edu)
Kerem Bulbul (bulbul***at***sabanciuniv.edu)

Abstract: The use of graph databases for social networks, images, web links, pathways and so on, has been increasing at a fast pace and promotes the need for efficient graph query processing on such databases. In this study, we discuss graph query processing -- referred to as graph matching -- and an inherent optimization problem known as the minimum hub cover problem. This optimization problem is introduced to the literature as a new graph representation model to expedite graph queries. With this representation, a graph database can be denoted by a small subset of graph vertices. Searching over only this subset of vertices decreases the response time of a query and increases the efficiency of graph query processing. We also discuss that finding the minimum hub cover alone does not guarantee the efficiency of graph matching computations. The order in which we match the query vertices also affects the cost of querying. For this purpose, we propose a shortest path formulation which gives a hub cover and a search sequence yielding a least cost query. The minimum hub cover problem is NP-hard and there exist just a few studies related to the formulation of the problem and the associated solution approaches. In this study, we present new alternate models and partially fill that gap. Similar to the other problems in the NP-hard class, solving large-scale MHC instances may prove very difficult. Therefore, we introduce relaxations and some rounding heuristics to find optimal or near optimal solutions fairly quickly. We provide a new binary integer programming formulation as well as a quadratic integer programming formulation. Our relaxation for the quadratic model leads to a semidefinite programming formulation. A solution to the minimum hub cover problem can be obtained by solving the relaxations of the proposed models and then rounding their solutions. We introduce two rounding algorithms to be applied to the optimal solutions of the linear programming and semidefinite programming relaxations. In addition, we also implement two other well-known rounding algorithms for the set covering formulation of the problem. Our computational study demonstrates that the results of the rounding algorithms obtained with the relaxations of the proposed mathematical models are better than those obtained with the standard set covering formulation.

Keywords: graph query processing, minimum hub cover, linear programming, semidefinite programming, rounding heuristics

Category 1: Applications -- Science and Engineering

Category 2: Integer Programming (0-1 Programming )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation:

Download: [PDF]

Entry Submitted: 11/30/2014
Entry Accepted: 11/30/2014
Entry Last Modified: 08/27/2017

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society