From: MikkelFJ <mikkelfj-anti-spam@...>
Date: 2003-05-27T02:00:18+09:00
Subject: Re: Binary Tree vs. Hash


"Dave Thomas" <dave@pragprog.com> wrote in message
news:3ED21933.7080504@pragprog.com...
> Xiangrong Fang wrote:

> If you're looking for memory efficiency are are simply doing lookups,
> perhaps you should look at using a Bloom filter. You could pack a 90,000
> word dictionary into 64kb. By coincidence my latest Kata is about them:
>
> http://pragprog.com/pragdave/Practices/Kata/KataFive.rdoc,v

I also recently found some articly on non-loss storage for lookup only. I.e.
returns yes or no to match correctly.
The method is based on finite state machines.
It could be used with attached data at some additional complexity - it
requires you to track the seach path and use
bits from each branch to generate an index for the data reference.
I guess this is a fancy way of creating perfect hashes.

For multi word searching I also found an aritcle on using vector spaces.
Each document is given a vector and your query is also given a vector.
You enumerate all known words. Each word becomes a position in the vector.
The value in the vector is the number of word occurrences.
You locate the document with the smallest distance from the query vector
using some euclidian or other measure
of distance. This also handles inexact queries and is supposedly memory
efficient.
The query would now need to look up each word in some hashtable or similar
to locate the vector index.
The documents need not be stored in-memory, only their vector representation
(which can be compressed).
A dump implementation would now scan all document vectors against the query,
but I'm sure there is more clever way.
Perhaps this is an excercise for a new kata?


Mikkel