[
https://issues.apache.org/jira/browse/MAHOUT-376?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12966223#action_12966223
]
Dmitriy Lyubimov commented on MAHOUT-376:
-----------------------------------------
{quote}I think that my suggested approach handles this already.
The block decomposition of Q via the blockwise QR decomposition implies a
breakdown of B into column-wise blocks which can each be handled separately.
The results are then combined using concatenation.
{quote}
Ted, yes, i understand that part, but i think we are talking about different
things. What I am talking about is formation of Y rows well before
orthonotmalization is even concerned.
What i mean is that right now VectorWritable loads the entire thing into
memory. Hence, the bound for width of A. (i.e. we can't load A row that is
longer than some memory chunk we can afford for it).
However, what A row is participating in in each case is a bunch of (namely,
k+p) dot-products. In order to produce those, it is sufficient to examine A row
sequentialy (i.e. streamingly) in one pass while keeping only k+p values in
memory as dot-accumulators.
Hence, say if we equipped VectorWritable with a push-parser like element
handler (notorious DocumentHanlder immediately pops in memory form SAXParser)
then we will never have to examine more than one element of A row at a time.
And hence we are not bound by memory for n (A width) anymore. That handler
would form Y rows directly during the sequential examination of A rows.
Identical considerations are in effect when forming Qt*A partial products (i
already checked for this).
I already thought about this approach a little (and i believe Jake Mannix also
posted something very similar to that recently to effect of sequential vector
examination backed by a streaming read).
Since it is touching VectorWritable internals, i think i would need to make a
change proposal for it and if seems reasonable handle it in another issue. I
will do so but i need to check couple of things first in Hadoop see if it is
feasible within current MR framework and doesn't blow off all benefits
code-data collocation.
If that proposal is implemented, and MR considerations are tackled, we will
have SSVD that scales to about a billion rows for 500 singular vlaues and 1G
memory in mapper vertically (m) and a gazillion in n (width).
theoretically. How about that.
> Implement Map-reduce version of stochastic SVD
> ----------------------------------------------
>
> Key: MAHOUT-376
> URL: https://issues.apache.org/jira/browse/MAHOUT-376
> Project: Mahout
> Issue Type: Improvement
> Components: Math
> Reporter: Ted Dunning
> Assignee: Ted Dunning
> Fix For: 0.5
>
> Attachments: MAHOUT-376.patch, Modified stochastic svd algorithm for
> mapreduce.pdf, QR decomposition for Map.pdf, QR decomposition for Map.pdf, QR
> decomposition for Map.pdf, sd-bib.bib, sd.pdf, sd.pdf, sd.pdf, sd.pdf,
> sd.tex, sd.tex, sd.tex, sd.tex, SSVD working notes.pdf, SSVD working
> notes.pdf, SSVD working notes.pdf, ssvd-CDH3-or-0.21.patch.gz,
> ssvd-CDH3-or-0.21.patch.gz, ssvd-m1.patch.gz, ssvd-m2.patch.gz,
> ssvd-m3.patch.gz, Stochastic SVD using eigensolver trick.pdf
>
>
> See attached pdf for outline of proposed method.
> All comments are welcome.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
