From: John Carter <john.carter@...>
Date: 2001-07-23T08:24:13+09:00
Subject: [ruby-talk:18307] Re: Effecient indexing algorithm

On Sun, 22 Jul 2001, Joe Graham wrote:

> But basically here are my constraints.  I want to store and retrieve large
> volumes of information.  I want to access this information via an index that
> is not (necessarily) constrained by hard and fast limitations such as a 32
> bit integer.  So would this exclude hashing?  Assume for the sake of
> argument it is every genomic combination in existence for humans including
> proteins and a few random peptic combinations.

Hmm. It depends on whether this is a indexing and rapid update /
rapid retrieval situation or a data mining exercise. If the data is
static, update everything once, datamine at leisure. If is a data
transaction environment, life is very different.

In the data mining environment I would suggest don't index! Build up a
suite of filters that allow you shift linearly through the data.

There are several implementations of this paradigm (I did it once in C++).

See "nosql" http://www.linux.it/~carlos/nosql/ for a good example.

I know from my experience and pain of writing iterators in C++ that Ruby
with its "yield" operator is absolutely ideal for this paradigm.

You can then do "data plumbing" where you simply connect data streams into
a pipe comprising of the filter objects and then suck on the far side...

It was a pain to program the filter iterator in C++ but blissfully easy to
use once the pain had been paid. In Ruby with "yield" there would be no
pain, just sweet bliss.

With this paradigm you get all the power of SQL for searching and its
faster as it doesn't need to handle the update problem. Furthermore it
integrates with the rest of your program far far better than a messy SQL
interface.

If you need some help / ideas as to what sort of filter objects are useful
and the API for them I can just borrow the ideas straight off my C++
stuff. (I have dropped the C++ stuff, I spent 95% of my time fighting the
language, Ruby helps you, C++ fights you.)

Some filter objects I created (off the top of my head) were...
Greps,
Summarise to lists,
Lists to rows,
Sort,
Uniq,
Count,
Transpose,
Join (tee join two streams)
Sources (CSV, dbm, ...)
Sinks (CVS, GNUplot, dbm...)
etc.
etc.


John Carter                             Phone : (64)(3) 358 6639
Tait Electronics                        Fax   : (64)(3) 359 4632
PO Box 1645 Christchurch                Email : john.carter@tait.co.nz
New Zealand

I'm becoming less and less convinced of humans as rational beings.
I suspect we are merely meme collectors, and the reason meme is only
kept on to help count our change.