Xapian discuss - Jun 2006 - Similarity Measures

Hi, 

I'm currently trying to implement a similarity measure
for xapian.  Ideally I'd like to be able to calculate
the following: 

for document i, and document j

s_ij =  a_ij / ( L_i + L_j + a_ij) 

Where L_i is the number of terms in the document i
and a_ij is:

a_ij = Sum[ t_ik t_jk ] 

Where t_ij is 1 if term "j" occurs in document i.
>From looking at the source code for weights it appears
that the sum should be cut up into peices that can be
calculated incrementally.  Is it possible to calculate
this value within the current weight framework. 



__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

On Tue, Jun 27, 2006 at 09:21:47AM -0700, Gavin Mendel-Gleason
wrote:
> I'm currently trying to implement a similarity measure
> for xapian.  Ideally I'd like to be able to calculate
> the following: 
> 
> for document i, and document j
I don't quite see how you would fit this into Xapian's ranking
framework, unless you fix document i and compute the similarity
for all the other documents as the ranking.  Effectively document
i would be the query, and you'd compute the similarity for each
document j for fixed i.
> s_ij =  a_ij / ( L_i + L_j + a_ij) 
> 
> Where L_i is the number of terms in the document i
> and a_ij is:
> 
> a_ij = Sum[ t_ik t_jk ] 
> 
> Where t_ij is 1 if term "j" occurs in document i.
> 
> From looking at the source code for weights it appears
> that the sum should be cut up into peices that can be
> calculated incrementally.
Yes, each query term which occurs in a document can contribute some
weight, and there's an optional extra weight only related to the
document (such as a document length adjustment factor).  These are all 
summed to get the total weight for a particular document.

This was originally chosen as it allowed us to implemented the various
probabilistic weighting formulae while allowing various optimisations
to reduce the work required.  It turns out to be flexible enough for 
a wide selection of potential weighting formulae, but there are
obviously plenty of conceivable formulae you can't rearrange to fit this
pattern.
> Is it possible to calculate this value within the current weight
> framework.
I don't see a way to do it.  You could calculate a_ij because that's a
sum over the terms in each document, but the a_ij on the bottom is hard
to handle.  The only transformation I can see is:

s_ij = 1 - ( L_i + L_j ) / ( L_i + L_j + a_ij )

But I don't see that leading anywhere.

You can safely transform your ranking formula through any strictly
increasing monotonic function (such as log or e^x) without altering the
rank order, but I don't see how to use that here.

Cheers,
    Olly

On Tue, Jun 27, 2006 at 09:21:47AM -0700, Gavin Mendel-Gleason
wrote:
> I'm currently trying to implement a similarity measure
> for xapian.  Ideally I'd like to be able to calculate
> the following:
I've been thinking about this.  Currently Xapian weighting schemes must
be able to be express the total weight for document d in the form:

     sum     ( weight(t,d) )  + weight(d)
 t indexes d

It wouldn't be too hard to extend that by multiplying the whole thing
by a scaling factor which depends only on the document.  If we have
bounds on the scaling factor, we could adapt the optimisations to take
this scaling factor into account.

This would allow more weighting schemes to be implemented, though it's
likely to further complicate the matcher code.

Cheers,
    Olly