Show simple item record

dc.contributor.authorWong, Bernard
dc.contributor.authorSlivkins, Aleksandrs
dc.contributor.authorSirer, Emin Gun
dc.description.abstractKeyword 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.en_US
dc.description.sponsorshipThis work was supported in part by NSF-TRUST 0424422 and NSF-CAREER 0546568 grants.en_US
dc.subjectPeer to peeren_US
dc.subjectKeyword searchen_US
dc.titleApproximate Matching for Peer-to-Peer Overlays with Cubiten_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record