Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Efficient matching for column intersection graphs
Auer B., Bisseling R. Journal of Experimental Algorithmics19 1.1-1.22,2014.Type:Article
Date Reviewed: Jul 30 2014

Graph partitioning and hypergraph partitioning have been used extensively in applications ranging from very-large-scale integration (VLSI) to portioning of data in parallel and distributed applications. Hypergraph and graph partitioning problems are nondeterministic polynomial-time (NP)-complete. Hence, many heuristics as well as effective software packages have been developed in the past. These software packages include Mondriaan, PaToH, and Zoltan. The package Zoltan is used with a cluster of Linux workstations. A strategy that is often used in these packages for constructing hypergraph partitioning is to do a coarse-grained partitioning, followed by a fine-grained partitioning. Coarse-grained partitioning focuses on the merging of the columns based on a matching of the columns, and the matching is based on the inner products of the columns. Fine-grained partitioning uses the well-known heuristic of Kernighan and Lin with an improvement suggested by Fiduccia and Mattheyses.

This paper presents an algorithm that incrementally constructs the inner products of columns and generates the matchings. This overcomes one of the disadvantages of constructing an AT A matrix, which could be dense (even if the original matrix A is sparse). The two steps involved in this process are a graph-matching function and a neighborhood function. The authors propose and use many different heuristics for computing both of these functions. For matching the heuristics used are the path-growing algorithm (PGA), the global paths algorithm (GPA), and the random order matching augmentation algorithm. For a neighborhood function, they propose and use heuristics such as FindHeavyUnmatchedNeighbors (FHUN), the stairway heuristic implementation of the FHUN, and StairwayM (a combination of stairway and Mondriaan).

This well-written paper tests these heuristics on large matrix data (with rows and columns varying from thousands to millions). The authors explain how the matching quality improves (from 95.3 percent to 97.4 percent), as well as the speed-up (to a factor of 19.6).

Reviewer:  M. S. Krishnamoorthy Review #: CR142567 (1411-0977)
Bookmark and Share
 
Hypergraphs (G.2.2 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Hypergraphs": Date
Closures of database hypergraphs
Saccà D. Journal of the ACM 32(4): 774-803, 1985. Type: Article
Apr 1 1987
On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
Lee S., Ho H. Information Processing Letters 87(5): 271-275, 2003. Type: Article
Oct 22 2003
Fault-tolerant cycle-emebedding of crossed cubes
Yang M., Li T., Tan J., Hsu L. Information Processing Letters 88(4): 149-154, 2003. Type: Article
Jun 9 2004
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy