Mailing-List: contact user-help@mahout.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@mahout.apache.org
Received-SPF: pass (nike.apache.org: domain of jake.mannix@gmail.com
 designates 209.85.212.170 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:from:date:message-id:subject:to
         :content-type;
        b=hebrLBYNIyKogJukuuoCqnW04LUoBTO4bLbhf0OjO9HvKxJrUEr1hcbTjQ28y1Pd5F
         OBa0KFCosQzCklM28rG2UqqRvuEMCO7lbmmPZ3D/t+SJW2It7KRrYQ9mQJBpTL0VyYZu
         VP17CuGJsR/p4lqWQ/W8Hab2FK+jnG0cjVmFw=
MIME-Version: 1.0
In-Reply-To: <AANLkTikUwX38xBrqu-iH5jTlMUcfYY0LpLZ6C_JN391U@mail.gmail.com>
References: <AANLkTikz1BLhOG4pv5uEGIOLl5pKUKT_uoETGaS6NMsb@mail.gmail.com>
	<AANLkTin0qVeaHCFkrWF7Le9YZxMN4I9qD_KZYeAhSPNH@mail.gmail.com>
	<AANLkTimGqHTk1_Q0t1W5SmhNY9AGxq5V2kT3JKqWWWYx@mail.gmail.com>
	<AANLkTindRW5vutBRW85RYcMBBlhjiL6psFcsjDaFxx_F@mail.gmail.com>
	<AANLkTikUwX38xBrqu-iH5jTlMUcfYY0LpLZ6C_JN391U@mail.gmail.com>
From: Jake Mannix <jake.mannix@gmail.com>
Date: Tue, 8 Jun 2010 16:16:16 -0700
Message-ID: <AANLkTik9MkTSQ0qr0DEsU3DUn4alg7cQGRf37aBNnE92@mail.gmail.com>
Subject: Re: Generating a Document Similarity Matrix
To: user@mahout.apache.org
Content-Type: multipart/alternative; boundary=001636e1fbfd158c8c04888cfb23

--001636e1fbfd158c8c04888cfb23
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Jun 8, 2010 at 3:56 PM, Olivier Grisel <olivier.grisel@ensta.org>wrote:

> 2010/6/8 Jake Mannix <jake.mannix@gmail.com>:
> > Hi Kris,
> >
> >  If you generate a full document-document similarity matrix offline, and
> > then make sure to sparsify the rows (trim off all similarities below a
> > threshold, or only take the top N for each row, etc...).  Then encoding
> > these values directly in the index would indeed allow for *superfast*
> > MoreLikeThis functionality, because you've already computed all
> > of the similar results offline.
>
> For 10e6 documents if might not be reasonable to generate the complete
> document-document similarity matrix: 1e12 components => a couple of
> tera bytes of similarity values just to find the find the top N
> afterwards:


Nope, this isn't what happens in what I described: when you take
a sparseDocumentMatrix.transpose().times(itself), the scaling does
not go N^2*M, with N^2 outputs - the calculation is sparse, only
computing the entries which are nonzero.  If you pre-sparsify the
documents a little (remove all terms which occur in more than
1% of all documents, or something like that), this sparse calculation
is even faster - it scales as sum_{i=1...N}(k_i)^2, where k_i is the
number of nonzero elements in document i.  If all documents were
the same length (k), then this scales as N*k^2, and the total
number of nonzero entries in the output is far less than N^2 if
k << N,M.

Getting rid of the common terms (even *lots* of them) beforehand
is still a very good idea.

   -jake

--001636e1fbfd158c8c04888cfb23--