You need a DHT that supports an efficient "partial match" primitive.
This is what we designed Cubit for:
http://www.cs.cornell.edu/~bwong/Cubit/
It's open-source, and you can take a look at the Azureus plug-in for
usage examples.
Enjoy!
- egs
On Thu, 2008-12-04 at 17:21 +0000, Will Morton wrote:
> Hello hackers;
>
> I have a large number of items, each with string metadata, that I want
> to search for. I want the search to be decentralised, so I'm going to
> use a DHT (although I'm happy to use another data structure if it's
> more optimal). I want to be able to search the items based on partial
> matches, so if an item has title 'foobarbaz', I want it to be returned
> when I search for 'foo', 'bar' or 'baz'.
>
> So when I am adding entries into the DHT, do I have to add keys for
> all possible substrings of the thing I am indexing (so with minimum
> search length 3, I need to add keys for 'foo', 'oob', 'oba', etc), or
> are there optimisations I can make? Presumably this is a well-studied
> area; can anyone point me at papers concerning this problem? Or else,
> describe how gnutella/edonkey do it?
>
> Thanks,
>
> Will
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers@lists.zooko.com
> http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
p2p-hackers@lists.zooko.com
http://lists.zooko.com/mailman/listinfo/p2p-hackers
