JavaScript is disabled for your browser. Some features of this site may not work without it.
Approximate Matching for Peer-to-Peer Overlays with Cubit

Author
Wong, Bernard; Slivkins, Aleksandrs; Sirer, Emin Gun
Abstract
Keyword search is a critical component in most content retrieval systems. Despite the emergence of completely decentralized and
efficient peer-to-peer techniques for content distribution, there have not been similarly efficient, accurate, and decentralized mechanisms for content discovery based on approximate search keys. In this paper,
we present a scalable and efficient peer-to-peer system called Cubit with a new search primitive that can efficiently find the k data items with keys most similar to a given search key. The system works by creating a keyword metric space that encompasses both the nodes and the objects in the system, where the distance between two points is a measure of the similarity between the strings that the points represent. It provides a loosely-structured overlay that can efficiently navigate this space. We evaluate Cubit through both a real deployment as a search plugin for a popular BitTorrent client and a large-scale simulation and show that it provides an efficient, accurate and robust method to handle imprecise string search in filesharing applications.
Sponsorship
This work was supported in part by NSF-TRUST 0424422 and NSF-CAREER 0546568 grants.
Date Issued
2008-05-19Subject
Peer to peer; Keyword search
Type
technical report