lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael McCandless" <>
Subject Re: Eliminate postings hash (was Re: improve how IndexWriter uses RAM...)
Date Thu, 05 Apr 2007 15:54:58 GMT
"Marvin Humphrey" <> wrote:
> On Apr 5, 2007, at 3:58 AM, Michael McCandless wrote:
> > The one thing that still baffles me is: I can't get a persistent
> > Posting hash to be any faster.
> Don't use a hash, then.  :)
> KS doesn't.
>    * Give Token a "position" member.
>    * After you've got accumulated all the Tokens, calculate
>      position for each token from the position increment.
>    * Arrange the postings in an array sorted by position.
>    * Count the number of postings in a row with identical
>      text to get freq.
> Relevant code from KinoSearch::Analysis::TokenBatch below.

OOOOOH!  I like that approach!

So you basically do not "de-dup" by field+term on your first pass
through the tokens in the doc (which is "roughly" what that hash
does).  Instead, append all tokens in an array, then sort first by
field+text and second by position?  This is done for each document

This seems like it could be a major win!

Did you every compare this approach against hash (or other de-dup data
structure, letter trie or something) approach?

I guess it depends on how many total terms you have in the doc vs how
many unique terms you have in the doc.  Qsort is NlogN, and, the
comparison of 2 terms is somewhat costly.  With de-duping, you pay a
hash lookup/insert cost (plus cost of managing little int buffers to
hold positions/offsets/etc) per term, but then only qsort on the
number of unique terms.

Whereas with your approach you don't pay any deduping cost but your
qsort is on total # terms, not total # unique terms.  I bet your
approach is quite a bit faster for small to medium sized docs (by
far the "norm") but not faster for very large docs?  Or maybe it's
even faster for very large docs because qsort is so darned fast :)


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message