  


Mathematical Programming Models Based on Hub Covers in Graph Query Processing
Belma Yelbay (byelbaysabanciuniv.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 NPhard 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 NPhard class, solving largescale 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 wellknown 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 (01 Programming ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 11/30/2014 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  