2005 | OriginalPaper | Chapter
Bit Zipper Rendezvous Optimal Data Placement for General P2P Queries
Authors : Wesley W. Terpstra, Stefan Behnel, Ludger Fiege, Jussi Kangasharju, Alejandro Buchmann
Published in: Current Trends in Database Technology - EDBT 2004 Workshops
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In many distributed applications, pairs of queries and values are evaluated by participating nodes. This includes keyword search for documents, selection queries on tuples, and publish-subscribe. These applications require that all values accepted by the query be evaluated. To carry out this evaluation we will present the peer-to-peer based Bit Zipper Rendezvous which partitions query-value pairs as opposed to values only. Even for problems that allow an efficient value-based partition, the Bit Zipper complements existing solutions with its generality. Where flooding to
N
nodes used to be the only fall-back, the Bit Zipper is a replacement needing only
$O(\sqrt{N})$
. For problems requiring that all pairs be evaluated, we will show that the Bit Zipper Rendezvous is optimal.