Supplementary

Citations:
 Appears in Collections:
Conference Paper: CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs
Title  CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs 

Authors  
Issue Date  2014 
Publisher  OpenProceedings. 
Citation  Advances in Database Technology  EDBT 2014: Proceedings of the 17th International Conference on Extending Database Technology, Athens, Greece, 2428 March, 2014
, p. 319330 How to Cite? 
Abstract  In many applications, entities and their relationships are
represented by graphs. Examples include the WWW (web
pages and hyperlinks) and bibliographic networks (authors
and coauthorship). 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 LUdecomposition 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
nonzero entries introduced in L and U are minimized.) We
propose a clusterbased 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 nonzero 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 highquality LU matrices over an
evolving matrix sequence. 
Description  Session: Matrix Factorization, Clustering and Probabilistic Data 
Persistent Identifier  http://hdl.handle.net/10722/203633 
ISBN 
DC Field  Value  Language 

dc.contributor.author  Ren, CH  en_US 
dc.contributor.author  Mo, L  en_US 
dc.contributor.author  Kao, CM  en_US 
dc.contributor.author  Cheng, CK  en_US 
dc.contributor.author  Cheung, DWL  en_US 
dc.date.accessioned  20140919T15:49:07Z   
dc.date.available  20140919T15:49:07Z   
dc.date.issued  2014  en_US 
dc.identifier.citation  Advances in Database Technology  EDBT 2014: Proceedings of the 17th International Conference on Extending Database Technology, Athens, Greece, 2428 March, 2014 , p. 319330  en_US 
dc.identifier.isbn  9783893180653   
dc.identifier.uri  http://hdl.handle.net/10722/203633   
dc.description  Session: Matrix Factorization, Clustering and Probabilistic Data   
dc.description.abstract  In many applications, entities and their relationships are represented by graphs. Examples include the WWW (web pages and hyperlinks) and bibliographic networks (authors and coauthorship). 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 LUdecomposition 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 nonzero entries introduced in L and U are minimized.) We propose a clusterbased 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 nonzero 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 highquality LU matrices over an evolving matrix sequence.   
dc.language  eng  en_US 
dc.publisher  OpenProceedings.   
dc.relation.ispartof  Advances in Database Technology  EDBT 2014: Proceedings of the 17th International Conference on Extending Database Technology  en_US 
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.title  CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Kao, CM: kao@cs.hku.hk  en_US 
dc.identifier.email  Cheng, CK: ckcheng@cs.hku.hk  en_US 
dc.identifier.email  Cheung, DWL: dcheung@cs.hku.hk  en_US 
dc.identifier.authority  Kao, CM=rp00123  en_US 
dc.identifier.authority  Cheng, CK=rp00074  en_US 
dc.identifier.authority  Cheung, DWL=rp00101  en_US 
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5441/002/edbt.2014.30   
dc.identifier.hkuros  237613  en_US 
dc.identifier.spage  319   
dc.identifier.epage  330   
dc.publisher.place  Konstanz, Germany   