Saturday, January 31, 2009

Bandwidth reduction, permutation of docs, fast pagerank

A common problem with research is that same results are achieved again and again with different names and in different contexts.

Matrix Bandwidth reduction is a well-known numerical analysis technique to reduce the bandwidth of a matrix. A quite famous method is the Cuthill-McKee algorithm. Other well-known techniques are the king ordering and the min degree ordering.

Recently, the similar techniques for bandwidth reductions have been studied in the context of document ids permutation for indexing compression (Index Compression through Document Reordering, Investigating the Effectiveness of Clickthrough Data for Document Reodering)

Lately, an interesting application has been suggested for Fast PageRank Computation

Boost provides an elegant and flexible support for Generic Graph representation. It also provides support for matrix bandwidth reduction.
Here you have the C++ code for boost matrix reodering.

No comments:

Post a Comment