De Gan Filters, Bloom Filters, Peoples DNS, and CNS
posted: Apr 27, 2004 8:24:00 PM
Danny Ayers has an interesting post, De Gan Filters (also, some more background from Marc Canter) about Joel De Gan's De Gan Filter which extends the concept of Bloom Filters. These are interesting hash structures for highly compressed indexes with small, false-positive-only, error margins on lookups.
Joel is working on a PeoplesDNS project, and came up with this technique as a way to create an efficient index for people look-ups.
Danny's post has a P.S. which I almost totally agree with:
I [sic] just occurred to me that the big DB backing store needn't actually be local - it could just be the web itself. Shift everything down a step, so your local cache is an unreliable map of a whole section of the web (e.g. the FOAFworld). When you do a query, that map tells you if you've got a chance of the getting the result. If there is a chance, you rescutter the actual data of interest.
Part of the beauty of DNS is how it actually does both (centralized and decentralized / local and remote lookup databases). I think there is quite a model (distributed information) ecosystem between the root servers and all the distributed DNS servers. DNS servers can act peer-to-peer, but also have a recourse to higher-up / root servers as well.
I have tried to follow this model in my CNS development for the iCite net. There are trade-offs in having any of it centralized, but I think the positives (essentially third-party verification) outweigh the negatives (possibility for domain name registry exploitativeness).
Also though, I think it is important that DNS-type registries (like CNS) and search be kept autonomous. In other words, DNS registers the location of servers, CNS registers the location of "content", but a search service for looking up information on those servers or in that content functions in parallel to (and, actually, a layer above) the function of the DNS or CNS registries.
(I guess the main distinction is that the index and the query interface to the index can be operated as two automonous systems.)
permalink |
comments {5}
·
trackbacks {1}
also available as:
rss · rss2 · rdf · atom
Note: All comments and trackbacks are moderated. Spam is deleted. Other comments are approved as promptly as possible.
Note: Older posts no longer accept new comments or trackbacks.
« prev post
Site search added, and (unrelated) the semantic web search engine
» next post
OK, wow! new Sony LIBRIe e-Ink book
Comment by: Joel De Gan · http://blog.peoplesdns.com
posted: May 3, 2004 3:15:03 PM
Hey, I actually just updated a bit on the peoplesdns system to clarify some of the project goals.
"The pDNS system will be opensource, non-centralized and will be a series of independent servers operated by individuals and companies. PeoplesDNS.com will act as 'Node1' and distribute 'zone files' much the same way as the DNS system currently works."
This distributes load and allows us to integrate foaf between all "registrars" such as all the current social networking sites. This in effect acts as a bridge between all networks and really creates a system that displays the true nature of how people interact.
Anyway, good post.