File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs

TitleCLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs
Authors
Issue Date2014
PublisherOpenProceedings.
Citation
Advances in Database Technology - EDBT 2014: Proceedings of the 17th International Conference on Extending Database Technology, Athens, Greece, 24-28 March, 2014 , p. 319-330 How to Cite?
AbstractIn many applications, entities and their relationships are represented by graphs. Examples include the WWW (web pages and hyperlinks) and bibliographic networks (authors and co-authorship). A graph can be conveniently modeled by a matrix from which various quantitative measures are derived. Some example measures include PageRank and SALSA (which measure nodes’ importance), and Personalized PageRank and Random Walk with Restart (which measure proximities between nodes). To compute these measures, linear systems of the form Ax = b, where A is a matrix that captures a graph’s structure, need to be solved. To facilitate solving the linear system, the matrix A is often decomposed into two triangular matrices (L and U). In a dynamic world, the graph that models it changes with time and thus is the matrix A that represents the graph. We consider a sequence of evolving graphs and its associated sequence of evolving matrices. We study how LU-decomposition should be done over the sequence so that (1) the decomposition is efficient and (2) the resulting LU matrices best preserve the sparsity of the matrices A’s (i.e., the number of extra non-zero entries introduced in L and U are minimized.) We propose a cluster-based algorithm CLUDE for solving the problem. Through an experimental study, we show that CLUDE is about an order of magnitude faster than the traditional incremental update algorithm. The number of extra non-zero entries introduced by CLUDE is also about an order of magnitude fewer than that of the traditional algorithm. CLUDE is thus an efficient algorithm for LU decomposition that produces high-quality LU matrices over an evolving matrix sequence.
DescriptionSession: Matrix Factorization, Clustering and Probabilistic Data
Persistent Identifierhttp://hdl.handle.net/10722/203633
ISBN

 

DC FieldValueLanguage
dc.contributor.authorRen, CHen_US
dc.contributor.authorMo, Len_US
dc.contributor.authorKao, CMen_US
dc.contributor.authorCheng, CKen_US
dc.contributor.authorCheung, DWLen_US
dc.date.accessioned2014-09-19T15:49:07Z-
dc.date.available2014-09-19T15:49:07Z-
dc.date.issued2014en_US
dc.identifier.citationAdvances in Database Technology - EDBT 2014: Proceedings of the 17th International Conference on Extending Database Technology, Athens, Greece, 24-28 March, 2014 , p. 319-330en_US
dc.identifier.isbn9783893180653-
dc.identifier.urihttp://hdl.handle.net/10722/203633-
dc.descriptionSession: Matrix Factorization, Clustering and Probabilistic Data-
dc.description.abstractIn many applications, entities and their relationships are represented by graphs. Examples include the WWW (web pages and hyperlinks) and bibliographic networks (authors and co-authorship). A graph can be conveniently modeled by a matrix from which various quantitative measures are derived. Some example measures include PageRank and SALSA (which measure nodes’ importance), and Personalized PageRank and Random Walk with Restart (which measure proximities between nodes). To compute these measures, linear systems of the form Ax = b, where A is a matrix that captures a graph’s structure, need to be solved. To facilitate solving the linear system, the matrix A is often decomposed into two triangular matrices (L and U). In a dynamic world, the graph that models it changes with time and thus is the matrix A that represents the graph. We consider a sequence of evolving graphs and its associated sequence of evolving matrices. We study how LU-decomposition should be done over the sequence so that (1) the decomposition is efficient and (2) the resulting LU matrices best preserve the sparsity of the matrices A’s (i.e., the number of extra non-zero entries introduced in L and U are minimized.) We propose a cluster-based algorithm CLUDE for solving the problem. Through an experimental study, we show that CLUDE is about an order of magnitude faster than the traditional incremental update algorithm. The number of extra non-zero entries introduced by CLUDE is also about an order of magnitude fewer than that of the traditional algorithm. CLUDE is thus an efficient algorithm for LU decomposition that produces high-quality LU matrices over an evolving matrix sequence.-
dc.languageengen_US
dc.publisherOpenProceedings.-
dc.relation.ispartofAdvances in Database Technology - EDBT 2014: Proceedings of the 17th International Conference on Extending Database Technologyen_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleCLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphsen_US
dc.typeConference_Paperen_US
dc.identifier.emailKao, CM: kao@cs.hku.hken_US
dc.identifier.emailCheng, CK: ckcheng@cs.hku.hken_US
dc.identifier.emailCheung, DWL: dcheung@cs.hku.hken_US
dc.identifier.authorityKao, CM=rp00123en_US
dc.identifier.authorityCheng, CK=rp00074en_US
dc.identifier.authorityCheung, DWL=rp00101en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5441/002/edbt.2014.30-
dc.identifier.hkuros237613en_US
dc.identifier.spage319-
dc.identifier.epage330-
dc.publisher.placeKonstanz, Germany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats