File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.5441/002/edbt.2014.30
- Scopus: eid_2-s2.0-85014402487
Supplementary
-
Citations:
- Scopus: 0
- 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, 24-28 March, 2014
, p. 319-330 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 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. |
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 | 2014-09-19T15:49:07Z | - |
dc.date.available | 2014-09-19T15: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, 24-28 March, 2014 , p. 319-330 | 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 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.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.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.scopus | eid_2-s2.0-85014402487 | - |
dc.identifier.hkuros | 237613 | en_US |
dc.identifier.spage | 319 | - |
dc.identifier.epage | 330 | - |
dc.publisher.place | Konstanz, Germany | - |