You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Dalton, Jeffery" <jd...@globalspec.com> on 2007/01/09 15:25:33 UTC

Beyond Lucene 2.0 Index Design

Hi,

I wanted to start some discussion about possible future Lucene file /
index formats.  This is an extension to the discussion on Flexible
Lucene Indexing discussed on the wiki:
http://wiki.apache.org/jakarta-lucene/FlexibleIndexing

Note: Related sources are listed at the end.    

I would like to have the ability to create term frequency [Persin, et
al. 1996] or "impact" sorted [Anh, Moffat 2001,2006] posting lists (freq
data) . A posting list sorted by Term frequency rather than document id
is straightforward (posting design below).  An Impact sorted list is
relatively new (and perhaps unfamiliar).  An Impact is a single integer
value for a term in a document that is stored in the posting list and is
computed from the combination of the term frequency, document boost,
field boost, length norms, and other arbitrary scoring features (word
position, font, etc...) -- all local information. 

The driving motivation for this change is to avoid reading the entire
posting list from disk for very long posting lists (it also leads to
simplified query-time scoring because the tf, norms, and boosts are
built into the impact).  This would address scalability issues with
large collections that have been seen in the past; back in December 2005
there were two threads: "Lucene Performance Bottlenecks" (Lucene User)
and "IndexOptimizer Re: Lucene Performance Bottlenecks" (Nutch Dev)
where Doug and Andrzej addressed some speed concerns by sorting the
Nutch index based on Document Boost (IndexSorter and a TopDocsCollector)
[inpsired by Long, Suel]. The goal is that an impact sorted posting list
would address these and other concerns in a generic manner.    

Allowing a frequency or impact sorted posting list format would lead to
a posting list with the following structure:  
(Frequency or impact could be used interchangeably in the structure.
Lettering continued from Wiki)

e. <impact, num_docs, (doc1,...docN)> 
f. <impact, num_docs, ([doc1, freq ,<positions>],...[docN, freq
,<positions>]) 

The positions are delta encoded for compression.  Similarly, the
document numbers for a given frequency/impact are delta encoded.  If you
read Moffat and Persin, the papers show that this achieves compression
comparable to, or even better than, a standard delta encoded docId
sorted index.  The structure lends itself well to early termination,
pruning, etc... where the entire posting list is not read from disk.  

This type of Impact sorted structure (or similar concept) seems to be
becoming a "standard" solution described in a lot of new research / text
books on IR for large scale indexes.  It would be great if Lucene
supported something like this someday ;-).

Thanks,

Jeff Dalton

References:
Anh, Moffat. Vector-Space Ranking with Effective Early Termination.
2001.
Anh, Moffat. Impact Transformation: Effective and Efficient Web
Retrieval. 2006.  
Anh, Moffat. Pruned Query Evaluation Using Pre-Computed Impacts. 2006.
Long, Suel. Optimized Query Execution in Large Search Engine with Global
Page Ordering.
Manning, Raghavan, Schutze. Introduction to Information Retrieval,
Chapters 2,7.
http://www-csli.stanford.edu/%7Eschuetze/information-retrieval-book.html

Persin, et al. Filtered Document Retrieval with Frequency-Sorted
Indexes. 1996.






---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Paul Elschot <pa...@xs4all.nl>.
Gentlemen,

On Friday 12 January 2007 21:00, Chuck Williams wrote:
> 
> Doug Cutting wrote on 01/12/2007 09:49 AM:
> > Marvin Humphrey wrote:
> >> Can you show us some code or pseudo-code for a BooleanScorer that
> >> would use impact-sorted posting lists?
> >
> > Another way to interpret this proposal is index-only: the low-level
> > indexing APIs should be general enough to permit impact-sorted posting
> > lists, and perhaps an impact-sorted posting list index implementation
> > could be provided in the core, but the existing search API's might not
> > work well or at all with an impact-sorted index.  Perhaps they could
> > interoperate at a "weighted filter" level.  There could be a separate
> > search implementation for impact-sorted indexes, and it could provide
> > output as a weighted filter, and the document-sorted search
> > implementation could accept weighted-filter clauses.  Does that make
> > sense?  It would be a little like span queries: a separate query
> > resolving engine that interoperates with the standard engine, but does
> > not replace it.
> I think this makes perfect sense.  Not all applications place an
> emphasis on relevance ranking.  E.g., in my current application, the
> focus is on categorizing and manipulating large complete result sets. 
> Lucene as it stands is excellent at that.  For very large indexes in
> domains where users are most interested in the top few hits, e.g. web
> search, then impact-sorted posting lists and partial retrieval have
> great value.  Adding this capability to lucene in a manner that supports
> both uses cases seems the way to go.  Sufficient flexibility in the
> indexing api's and core implementation(s) so that apps can specify
> whether or not they want impact sorting, combined with similarly
> flexibility in the query engine(s) to provide complete or incremental
> partial retrieval, would achieve this.  Weighted-filter clauses could
> require the impact-sorted index representation.

A weighted filter clause could already be used as a prescored clause
in a boolean query. That makes weighted filters a useful addition to
the current search methods.

Regards,
Paul Elschot

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Chuck Williams <ch...@manawiz.com>.
Doug Cutting wrote on 01/12/2007 09:49 AM:
> Marvin Humphrey wrote:
>> Can you show us some code or pseudo-code for a BooleanScorer that
>> would use impact-sorted posting lists?
>
> Another way to interpret this proposal is index-only: the low-level
> indexing APIs should be general enough to permit impact-sorted posting
> lists, and perhaps an impact-sorted posting list index implementation
> could be provided in the core, but the existing search API's might not
> work well or at all with an impact-sorted index.  Perhaps they could
> interoperate at a "weighted filter" level.  There could be a separate
> search implementation for impact-sorted indexes, and it could provide
> output as a weighted filter, and the document-sorted search
> implementation could accept weighted-filter clauses.  Does that make
> sense?  It would be a little like span queries: a separate query
> resolving engine that interoperates with the standard engine, but does
> not replace it.
I think this makes perfect sense.  Not all applications place an
emphasis on relevance ranking.  E.g., in my current application, the
focus is on categorizing and manipulating large complete result sets. 
Lucene as it stands is excellent at that.  For very large indexes in
domains where users are most interested in the top few hits, e.g. web
search, then impact-sorted posting lists and partial retrieval have
great value.  Adding this capability to lucene in a manner that supports
both uses cases seems the way to go.  Sufficient flexibility in the
indexing api's and core implementation(s) so that apps can specify
whether or not they want impact sorting, combined with similarly
flexibility in the query engine(s) to provide complete or incremental
partial retrieval, would achieve this.  Weighted-filter clauses could
require the impact-sorted index representation.

Chuck


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Doug Cutting <cu...@apache.org>.
Marvin Humphrey wrote:
> Can you show us some code or pseudo-code for a BooleanScorer that would 
> use impact-sorted posting lists?

Another way to interpret this proposal is index-only: the low-level 
indexing APIs should be general enough to permit impact-sorted posting 
lists, and perhaps an impact-sorted posting list index implementation 
could be provided in the core, but the existing search API's might not 
work well or at all with an impact-sorted index.  Perhaps they could 
interoperate at a "weighted filter" level.  There could be a separate 
search implementation for impact-sorted indexes, and it could provide 
output as a weighted filter, and the document-sorted search 
implementation could accept weighted-filter clauses.  Does that make 
sense?  It would be a little like span queries: a separate query 
resolving engine that interoperates with the standard engine, but does 
not replace it.

Ramblingly,

Doug

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Jan 11, 2007, at 8:37 PM, Ming Lei wrote:

> But practically, the approximation (as in my original
> post) should work well enough for large corpus and
> relevancy-driven retrieval.

> The saving on disk access for large corpus (implies
> very long posting list) will be huge by impact-sorted
> posting list.

For 'A OR B', or a simple TermQuery, absolutely.  But for anything  
else, I'm skeptical.  How about...

    'townshend OR (the AND who)'

You'll start with a small number of docs which have both 'the' and  
'who'.   And then, you'll vet them to see if they contain  
'townshend'; only a miniscule portion will, so you'll have to go  
redo... and redo... and redo...

All that redo-ing is going to be considerably less efficient than  
just plowing through the complete posting lists in the first place,  
right?  That's a lot of disk seeks... not to mention all those  
redundant VInt reads.

And each time you redo, you'll need to build an intersection using  
bitvectors or whatever, which requires RAM and processor above and  
beyond what's needed to drop a doc-score pair into a HitCollector.

And trying to tune those heuristics so that you can tell where the  
proper pruning threshold lies for a given clause in the middle of a  
complex boolean query... the scorers are already the hardest part of  
Lucene to grok.  Won't this add more complexity to the place where we  
already have more than enough?  I shudder to think how difficult it  
would become to uncover bugs in a pruning BooleanScorer.

I really want this to work out, because I can put it into KinoSearch  
0.20 if it does -- backwards compatibility is already out the  
window.  But I just don't see how to make it happen.

Can you show us some code or pseudo-code for a BooleanScorer that  
would use impact-sorted posting lists?

> I also see that a flexible framework to support
> multiple indexing scheme will make Lucene a general
> search framework and test bed for innovative search
> algorithms and gain further ground in research
> community.

Yes, that's the idea.  There are limits to the amount of flexibility  
we can offer, though.  With a unified postings file, especially with  
one file per field, changing the amount of information in each  
posting is reasonably straightforward.  Changing the sort order,  
OTOH, is not, because every component in the scoring apparatus  
assumes that it will be fed document numbers in ascending order.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Ming Lei <mi...@yahoo.com>.
Marvin,
Several posts back on this thread, I talked about an
algorithm of impact-sorted posting list for
conjunctive boolean query. Your concerns on
impact-sorting in boolean retrieval model is valid.
But practically, the approximation (as in my original
post) should work well enough for large corpus and
relevancy-driven retrieval.

The saving on disk access for large corpus (implies
very long posting list) will be huge by impact-sorted
posting list.

I also see that a flexible framework to support
multiple indexing scheme will make Lucene a general
search framework and test bed for innovative search
algorithms and gain further ground in research
community.

I would happy to put my efforts on this.

Michael Lei
Search Labs
Live Search, Microsoft Corp.

> That makes sense.  It would work well for Lucene
> queries that happen  
> to mimic pure vector queries: a simple TermQuery, or
> a BooleanQuery  
> consisting entirely of "should" clauses wrapping
> TermQueries.
> 
> Let's explore how it would work for other varieties
> of BooleanQuery...
> 
>    A -B
> 
> Not so good.  We need to iterate over all the docs
> nums for B.  We  
> could start by fetching only some of the docs for A,
> and then  
> iterating over all the docs for B and seeing whether
> we still have  
> enough docs after filtering. If we don't, and we
> have to go back, we  
> have to start over from scratch iterating over B. 
> Either that or we  
> need to save set B in a BitVector just in case. 
> Yuck.
> 
>    A +B
> 
> Hmm.  You start with the highest ranking docs for B.
>  You stop when  
> the impact of A has dropped low enough that no
> subsequent document  
> can displace a current doc in the HitQueue.  But
> what if B is a low- 
> scoring term compared to A, e.g. 'dinosaur +park' ? 
> You'll have to  
> go deep the list for 'park'.  And things just get
> really complicated  
> and murky.  I can't see how anything less than
> scoring all docs like  
> we do now will reliably produce decent precision.
> 
>    +A +B
> 
> Ouch.  This is just a slightly less severe version
> of the phrase  
> matching conundrum.  I don't see a good way to
> handle this at all.   
> Basically, you need to load two BitVectors and take
> the intersection,  
> then go back and score.
> 
> I think we can stop there.  I don't see any way to
> make an impact- 
> sorted posting list work efficiently with boolean
> logic.  It only  
> works with pure vector space.
> 
> The trick they used in Nutch wasn't to reorder the
> postings.  What  
> they did was sort the entire index so that documents
> were ordered by  
> descending document boost.  Say you want 10 results.
>  If you grab the  
> first, say, 100 hits, and sort them by score, the
> odds are pretty  
> good that you'll find most of the same docs you
> would have found  
> after crunching through your entire index.  Grab the
> first 1000 hits,  
> and the odds are even better.  (That's assuming that
> document boost  
> plays a dominant role in your scoring algorithm.) 
> It's a good  
> heuristic.  However, it doesn't coexist happily with
> incremental  
> indexing.
> 
> Marvin Humphrey
> Rectangular Research
> http://www.rectangular.com/
> 
> 
> 
>
---------------------------------------------------------------------
> To unsubscribe, e-mail:
> java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail:
> java-dev-help@lucene.apache.org
> 
> 



 
____________________________________________________________________________________
Bored stiff? Loosen up... 
Download and play hundreds of games for free on Yahoo! Games.
http://games.yahoo.com/games/front

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Jan 11, 2007, at 2:30 PM, jian chen wrote:

> It seems to me that the impacted-sorted list makes sense if you are  
> trying
> to do pure vector space based ranking. This is from what I have  
> read from
> the research papers. They all talk about how to optimize the vector  
> space
> model using this impact-sorted list approach.

That makes sense.  It would work well for Lucene queries that happen  
to mimic pure vector queries: a simple TermQuery, or a BooleanQuery  
consisting entirely of "should" clauses wrapping TermQueries.

Let's explore how it would work for other varieties of BooleanQuery...

   A -B

Not so good.  We need to iterate over all the docs nums for B.  We  
could start by fetching only some of the docs for A, and then  
iterating over all the docs for B and seeing whether we still have  
enough docs after filtering. If we don't, and we have to go back, we  
have to start over from scratch iterating over B.  Either that or we  
need to save set B in a BitVector just in case.  Yuck.

   A +B

Hmm.  You start with the highest ranking docs for B.  You stop when  
the impact of A has dropped low enough that no subsequent document  
can displace a current doc in the HitQueue.  But what if B is a low- 
scoring term compared to A, e.g. 'dinosaur +park' ?  You'll have to  
go deep the list for 'park'.  And things just get really complicated  
and murky.  I can't see how anything less than scoring all docs like  
we do now will reliably produce decent precision.

   +A +B

Ouch.  This is just a slightly less severe version of the phrase  
matching conundrum.  I don't see a good way to handle this at all.   
Basically, you need to load two BitVectors and take the intersection,  
then go back and score.

I think we can stop there.  I don't see any way to make an impact- 
sorted posting list work efficiently with boolean logic.  It only  
works with pure vector space.

The trick they used in Nutch wasn't to reorder the postings.  What  
they did was sort the entire index so that documents were ordered by  
descending document boost.  Say you want 10 results.  If you grab the  
first, say, 100 hits, and sort them by score, the odds are pretty  
good that you'll find most of the same docs you would have found  
after crunching through your entire index.  Grab the first 1000 hits,  
and the odds are even better.  (That's assuming that document boost  
plays a dominant role in your scoring algorithm.)  It's a good  
heuristic.  However, it doesn't coexist happily with incremental  
indexing.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by jian chen <ch...@gmail.com>.
I also got the same question. It seems it is very hard to efficiently do
phrase based query.

I think most search engines do phrase based query, or at least appear to be.
So, like in google, the query result must contain all the words user
searched on.

It seems to me that the impacted-sorted list makes sense if you are trying
to do pure vector space based ranking. This is from what I have read from
the research papers. They all talk about how to optimize the vector space
model using this impact-sorted list approach.

Unfortunately, the vector space model has serious drawbacks. It does not
take the inter-word relation into account. Thus, could result in a search
result where documents matching only some keywords ranked higher than
documents matching all of them.

I still yet to see whether the impact-sorted list approach could handle this
efficiently.

Cheers,

Jian

On 1/11/07, Marvin Humphrey <ma...@rectangular.com> wrote:
>
>
> On Jan 9, 2007, at 6:25 AM, Dalton, Jeffery wrote:
> > e. <impact, num_docs, (doc1,...docN)>
> > f. <impact, num_docs, ([doc1, freq ,<positions>],...[docN, freq
> > ,<positions>])
>
> How do you build an efficient PhraseScorer to work with an impact-
> sorted posting list?
>
> The way PhraseScorer currently works is: find a doc that contains all
> terms, then see if the terms occur consecutively in phrase order,
> then determine a score.  The TermDocs objects feeding PhraseScorer
> return doc_nums in  ascending order, so finding an intersection is
> easy.  But if the document numbers are returned in what looks to the
> PhraseScorer like random order... ??
>
> Marvin Humphrey
> Rectangular Research
> http://www.rectangular.com/
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>

Re: Beyond Lucene 2.0 Index Design

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Jan 9, 2007, at 6:25 AM, Dalton, Jeffery wrote:
> e. <impact, num_docs, (doc1,...docN)>
> f. <impact, num_docs, ([doc1, freq ,<positions>],...[docN, freq
> ,<positions>])

How do you build an efficient PhraseScorer to work with an impact- 
sorted posting list?

The way PhraseScorer currently works is: find a doc that contains all  
terms, then see if the terms occur consecutively in phrase order,  
then determine a score.  The TermDocs objects feeding PhraseScorer  
return doc_nums in  ascending order, so finding an intersection is  
easy.  But if the document numbers are returned in what looks to the  
PhraseScorer like random order... ??

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Grant Ingersoll <gr...@gmail.com>.
Hi Jeff,

Wondering if you (and/or others) would be interested in taking a look  
at https://issues.apache.org/jira/browse/LUCENE-662 and vetting the  
new interfaces, etc. to see if you could come up w/ a prototype  
implementation.  This would help move along 662 as it would sort out  
some of the issues that come up with the new interface based approach  
(I often find it takes at least two implementations to fully flesh  
out an abstraction like this)

-Grant

On Jan 9, 2007, at 9:25 AM, Dalton, Jeffery wrote:

> Hi,
>
> I wanted to start some discussion about possible future Lucene file /
> index formats.  This is an extension to the discussion on Flexible
> Lucene Indexing discussed on the wiki:
> http://wiki.apache.org/jakarta-lucene/FlexibleIndexing
>
> Note: Related sources are listed at the end.
>
> I would like to have the ability to create term frequency [Persin, et
> al. 1996] or "impact" sorted [Anh, Moffat 2001,2006] posting lists  
> (freq
> data) . A posting list sorted by Term frequency rather than  
> document id
> is straightforward (posting design below).  An Impact sorted list is
> relatively new (and perhaps unfamiliar).  An Impact is a single  
> integer
> value for a term in a document that is stored in the posting list  
> and is
> computed from the combination of the term frequency, document boost,
> field boost, length norms, and other arbitrary scoring features (word
> position, font, etc...) -- all local information.
>
> The driving motivation for this change is to avoid reading the entire
> posting list from disk for very long posting lists (it also leads to
> simplified query-time scoring because the tf, norms, and boosts are
> built into the impact).  This would address scalability issues with
> large collections that have been seen in the past; back in December  
> 2005
> there were two threads: "Lucene Performance Bottlenecks" (Lucene User)
> and "IndexOptimizer Re: Lucene Performance Bottlenecks" (Nutch Dev)
> where Doug and Andrzej addressed some speed concerns by sorting the
> Nutch index based on Document Boost (IndexSorter and a  
> TopDocsCollector)
> [inpsired by Long, Suel]. The goal is that an impact sorted posting  
> list
> would address these and other concerns in a generic manner.
>
> Allowing a frequency or impact sorted posting list format would  
> lead to
> a posting list with the following structure:
> (Frequency or impact could be used interchangeably in the structure.
> Lettering continued from Wiki)
>
> e. <impact, num_docs, (doc1,...docN)>
> f. <impact, num_docs, ([doc1, freq ,<positions>],...[docN, freq
> ,<positions>])
>
> The positions are delta encoded for compression.  Similarly, the
> document numbers for a given frequency/impact are delta encoded.   
> If you
> read Moffat and Persin, the papers show that this achieves compression
> comparable to, or even better than, a standard delta encoded docId
> sorted index.  The structure lends itself well to early termination,
> pruning, etc... where the entire posting list is not read from disk.
>
> This type of Impact sorted structure (or similar concept) seems to be
> becoming a "standard" solution described in a lot of new research /  
> text
> books on IR for large scale indexes.  It would be great if Lucene
> supported something like this someday ;-).
>
> Thanks,
>
> Jeff Dalton
>
> References:
> Anh, Moffat. Vector-Space Ranking with Effective Early Termination.
> 2001.
> Anh, Moffat. Impact Transformation: Effective and Efficient Web
> Retrieval. 2006.
> Anh, Moffat. Pruned Query Evaluation Using Pre-Computed Impacts. 2006.
> Long, Suel. Optimized Query Execution in Large Search Engine with  
> Global
> Page Ordering.
> Manning, Raghavan, Schutze. Introduction to Information Retrieval,
> Chapters 2,7.
> http://www-csli.stanford.edu/%7Eschuetze/information-retrieval- 
> book.html
>
> Persin, et al. Filtered Document Retrieval with Frequency-Sorted
> Indexes. 1996.
>
>
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>

------------------------------------------------------
Grant Ingersoll
http://www.grantingersoll.com/



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Jan 9, 2007, at 6:25 AM, Dalton, Jeffery wrote:

> e. <impact, num_docs, (doc1,...docN)>
> f. <impact, num_docs, ([doc1, freq ,<positions>],...[docN, freq
> ,<positions>])

Does the impact have any use after it's used to sort the postings?   
Can we leave it out of the index format and recalculate at merge-time?

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: Beyond Lucene 2.0 Index Design

Posted by Doron Cohen <DO...@il.ibm.com>.
Scoring today goes doc-at-a-time - all scorers and term-posting-readers
advance together; once a new doc is processed, scoring of previous docs is
known and final. This allows maintaining a finite size queue for collecting
best hits. Then, for huge collections, having to exhaustively scan all
posting lists becomes a scalability issue.

If I understand the proposal here correctly, it is suggested to order
posting lists by possible score contribution (frequency/impact) - in
particular, two different terms A and B both appearing in two docs X and Y
may have the docs in a different order - X Y for A and Y X for B. This
flexibility/granularity, while enabling early-terminataion and pruning,
would require a term-at-a-time scoring algorithm, which would be quite a
change in Lucene scoring.

The work sited seems less flexible - only a single value is maintained per
document - e.g. Page Rank - and then documents IDs are shuffled so that in
the resulted index the posting lists are still ordered - as today - by
docids, but sattify: rank(i) >= rank(i+1).

If the latter (single-value-per-doc) approach is taken, still needs to
decide when to sort - externally, when exporting the (large) index for
search, or internally, as part of merge. If done as part of merge, each
(result) segment is always ordered (by rank); merging would become more
tricky, since you don't want to exhaust memory while merging, but I think
it is doable.

"Dalton, Jeffery" <jd...@globalspec.com> wrote on 09/01/2007 06:25:33:

> Hi,
>
> I wanted to start some discussion about possible future Lucene file /
> index formats.  This is an extension to the discussion on Flexible
> Lucene Indexing discussed on the wiki:
> http://wiki.apache.org/jakarta-lucene/FlexibleIndexing
>
> Note: Related sources are listed at the end.
>
> I would like to have the ability to create term frequency [Persin, et
> al. 1996] or "impact" sorted [Anh, Moffat 2001,2006] posting lists (freq
> data) . A posting list sorted by Term frequency rather than document id
> is straightforward (posting design below).  An Impact sorted list is
> relatively new (and perhaps unfamiliar).  An Impact is a single integer
> value for a term in a document that is stored in the posting list and is
> computed from the combination of the term frequency, document boost,
> field boost, length norms, and other arbitrary scoring features (word
> position, font, etc...) -- all local information.
>
> The driving motivation for this change is to avoid reading the entire
> posting list from disk for very long posting lists (it also leads to
> simplified query-time scoring because the tf, norms, and boosts are
> built into the impact).  This would address scalability issues with
> large collections that have been seen in the past; back in December 2005
> there were two threads: "Lucene Performance Bottlenecks" (Lucene User)
> and "IndexOptimizer Re: Lucene Performance Bottlenecks" (Nutch Dev)
> where Doug and Andrzej addressed some speed concerns by sorting the
> Nutch index based on Document Boost (IndexSorter and a TopDocsCollector)
> [inpsired by Long, Suel]. The goal is that an impact sorted posting list
> would address these and other concerns in a generic manner.
>
> Allowing a frequency or impact sorted posting list format would lead to
> a posting list with the following structure:
> (Frequency or impact could be used interchangeably in the structure.
> Lettering continued from Wiki)
>
> e. <impact, num_docs, (doc1,...docN)>
> f. <impact, num_docs, ([doc1, freq ,<positions>],...[docN, freq
> ,<positions>])
>
> The positions are delta encoded for compression.  Similarly, the
> document numbers for a given frequency/impact are delta encoded.  If you
> read Moffat and Persin, the papers show that this achieves compression
> comparable to, or even better than, a standard delta encoded docId
> sorted index.  The structure lends itself well to early termination,
> pruning, etc... where the entire posting list is not read from disk.
>
> This type of Impact sorted structure (or similar concept) seems to be
> becoming a "standard" solution described in a lot of new research / text
> books on IR for large scale indexes.  It would be great if Lucene
> supported something like this someday ;-).
>
> Thanks,
>
> Jeff Dalton
>
> References:
> Anh, Moffat. Vector-Space Ranking with Effective Early Termination.
> 2001.
> Anh, Moffat. Impact Transformation: Effective and Efficient Web
> Retrieval. 2006.
> Anh, Moffat. Pruned Query Evaluation Using Pre-Computed Impacts. 2006.
> Long, Suel. Optimized Query Execution in Large Search Engine with Global
> Page Ordering.
> Manning, Raghavan, Schutze. Introduction to Information Retrieval,
> Chapters 2,7.
> http://www-csli.stanford.edu/%7Eschuetze/information-retrieval-book.html
>
> Persin, et al. Filtered Document Retrieval with Frequency-Sorted
> Indexes. 1996.
>
>
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org