next up previous
Next: Acknowledgements Up: Sparse Matrix Reordering Title Previous: Browsing Clusters

5. Summary and Future Work

Three reordering schemes have been used to produce narrow-banded hypertext matrices for cluster identification. Whereas the spectral-based methods (Fiedler and Correspondence Analysis) tend to produce matrices with smaller envelopes, the symbolic Reverse Cuthill-Mckee (RCM) method produces smaller bandwidths at a substantially reduced computational cost.

The reordered hypertext matrices facilitate the development of browsing tools for isolating document clusters of related information. Such tools are greatly needed to navigate large and/or distributed databases with hypertext links. The ability to identify (without necessarily retrieving) remote documents through their links to available (local) documents on a network is possible. In addition to browsing, indexing schemes based on term-document (or hypertext) matrices such as Latent Semantic Indexing (LSI) can exploit the reorderings presented for a more equitable distribution of nonzeros across processors or nodes of a network.

Future work on the reordering of hypertext matrices involves (i) the consideration of much larger hypertext collections, (ii) the development of a visual browser tool for the X11 Release 5 Windows environment for extracting hypertext clusters of related information, (iii) the use of separator-based reorderings schemes (e.g., nested dissection), and (iv) the exploration of direct methods (as opposed to iterative schemes such as Lanczos) for computing the singular value decomposition (SVD) of banded hypertext matrices.

Michael W. Berry (
Mon Jan 29 14:30:24 EST 1996