%0 Conference Paper %1 857.68036 %A Berry, Michael W. %A Hendrickson, Bruce %A Raghavan, Padma %D 1996 %E et al. Renegar, James %J Lect. Appl. Math. %K decomposition; matrix reordering schemes singular sparse value %P 99-123 %T Sparse matrix reordering schemes for browsing hypertext. %V 32 %X Many approaches for retrieving documents from electronic databases depend on the literal matching of words in a user's query to the keywords defining database objects. Since there is great diversity in the words people use to describe the same object, literal- or lexical- based methods can often retrieve irrelevant documents. Another approach to exploit the implicit higher-order structure in the association of terms with text objects is to compute the singular value decomposition (SVD) of large sparse term by text-object matrices. Latent Semantic Indexing (LSI) is a conceptual indexing method which employs the SVD to represent terms and objects by dominant singular subspaces so that user queries can be matched in a lower-rank semantic space.\par This paper considers a third, intermediate approach to facilitate the immediate detection of document (or term) clusters. We demonstrate that both traditional sparse matrix reordering schemes (e.g., Reverse Cuthill-McKee) and spectral-based approaches (e.g., Correspondence Analysis or Fiedler vector-based spectral bisection) can be used to permute original term by document (hypertext) matrices to a narrow-banded form suitable for the detection of document (or term) clusters. Although this approach would not exploit the higher-order semantic structure in the database, it can be used to develop browsing tools for hypertext and on-line information at a reduced computational cost. %@ 0-8218-0530-4/pbk

@inproceedings{857.68036, abstract = {Many approaches for retrieving documents from electronic databases depend on the literal matching of words in a user's query to the keywords defining database objects. Since there is great diversity in the words people use to describe the same object, literal- or lexical- based methods can often retrieve irrelevant documents. Another approach to exploit the implicit higher-order structure in the association of terms with text objects is to compute the singular value decomposition (SVD) of large sparse term by text-object matrices. Latent Semantic Indexing (LSI) is a conceptual indexing method which employs the SVD to represent terms and objects by dominant singular subspaces so that user queries can be matched in a lower-rank semantic space.\par This paper considers a third, intermediate approach to facilitate the immediate detection of document (or term) clusters. We demonstrate that both traditional sparse matrix reordering schemes (e.g., Reverse Cuthill-McKee) and spectral-based approaches (e.g., Correspondence Analysis or Fiedler vector-based spectral bisection) can be used to permute original term by document (hypertext) matrices to a narrow-banded form suitable for the detection of document (or term) clusters. Although this approach would not exploit the higher-order semantic structure in the database, it can be used to develop browsing tools for hypertext and on-line information at a reduced computational cost. }, added-at = {2008-03-02T02:12:02.000+0100}, author = {Berry, Michael W. and Hendrickson, Bruce and Raghavan, Padma}, biburl = {https://www.bibsonomy.org/bibtex/2f0f56b69420c4af7df6395b3cd764237/dmartins}, classmath = {*68P20 Information storage and retrieval 05C50 Graphs and matrices 65F50 Sparse matrices 65F15 Eigenvalues (numerical linear algebra)}, description = {robotica-bib}, editor = {et al. Renegar, James}, interhash = {4120c33e9ba561ca553ed5292ba7011a}, intrahash = {f0f56b69420c4af7df6395b3cd764237}, isbn = {0-8218-0530-4/pbk}, journal = {Lect. Appl. Math.}, keywords = {decomposition; matrix reordering schemes singular sparse value}, language = {English}, note = {The mathematics of numerical analysis. 1995 AMS-SIAM summer seminar in applied mathematics, July 17--August 11, 1995, Park City, UT, USA. Providence }, pages = {99-123}, timestamp = {2008-03-02T02:12:18.000+0100}, title = {Sparse matrix reordering schemes for browsing hypertext.}, volume = 32, year = 1996 }