hadoop-common-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <tdunn...@maprtech.com>
Subject Re: breadth-first search
Date Wed, 22 Dec 2010 19:00:37 GMT
The Mahout math package has a number of basic algorithms that use
algorithmic efficiencies when given sparse graphs.

A number of other algorithms use only the product of a sparse matrix on
another matrix or a vector.  Since these algorithms never change the
original sparse matrix, they are safe against fill-in problems.

The random projection technique avoids O(v^3) algorithms for computing SVD
or related matrix decompositions.  See http://arxiv.org/abs/0909.4061 and
https://issues.apache.org/jira/browse/MAHOUT-376

None of these these algorithms are specific to graph theory, but all deal
with methods that are useful with sparse graphs.

On Wed, Dec 22, 2010 at 10:46 AM, Ricky Ho <rickyphyllis@yahoo.com> wrote:

> Can you point me to Matrix algorithms that is tuned for sparse graph ?
>  What I
> mean is from O(v^3) to O(v*e)  where v = number of vertex and e = number of
> edges.
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message