Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)

[Oliver Bandel <oliver@first.in-berlin.de>]

On Wed, Nov 16, 2005 at 04:59:33PM -0800, Karl Zilles wrote:
> Oliver Bandel wrote:
> >I'm looking for indexing algorithms and especially - if
> >such a thing exists - mergeable/extendable indexing algorithms.
> >
> >So, say we have 10^6 texts that we want ot have an index for,
> >to retrieve the text according to some parts of the text
> >(keywords, substrings,...).
> >We want to make an index from these texts.
> >
> >After a while we get 10^5 new texts and want to extend
> >the exisiting index, so that the whole index not necessarily
> >must be created again, with the indexer-tool running on
> >all files (^10^6 + 10^5) again, but only have to index the new files,
> >but the big index can be extended with additional smaller indizes.
> >
> >Is there something like that already existing?
> >Or must the new index be created on all files again,
> >or must there be a workaround with the big and a small index-file,
> >where handling of both would be a solution we must provide by ourselfes?
> 
> I wrote a text indexing system a while ago in C++.  Pardon me if none of 
> the following is of interest:
[...]
 
> The B* file gets big, but the locations file gets huge.  Using this 
> methodology, you only ever modify the B* file, and never have to 
> reprocess your indexed documents.  Also you can continue to search the 
> index while documents are being indexed.

Wow, that is fine! :)

But mmap for example (you mentioned better/newer implementations)
can't be used for the whole index, because it definitely
will be larger than the available memory. So mmap and
such techniques can only be used for
parts of the index (but it may be a good choice to use it).

The update time was critical, but with indexes like you mentioned,
where reading while updating is possible (and when updating
is fast), this is very fine. :)


Best Regards, and Ciao,
                   Oliver