Abstract mentions bloom filters directly so your analogy makes sense > Efficient discovery of information, based on partial knowledge, is a challenging problem

Abstract mentions bloom filters directly so your analogy makes sense > Efficient discovery of information, based on partial knowledge, is a challenging problem faced by many large scale distributed systems. This paper presents Plexus, a peer-to-peer search protocol that provides an efficient mechanism for advertising a bitsequence (pattern), and discovering it using any subset of its 1-bits. A pattern (e.g., Bloom filter) summarizes the properties (e.g., keywords, service description) associated with a shared object (e.g., document, service). But I think that paper is more about discovery than search. It would be good for a tagging system but I didn't read enough to know if it would be useful for a more general search index.