Hyperspaces for object clustering and approximate matching in peer-to-peer overlays Export

@inproceedings{citeulike:6074614, abstract = {Existing distributed hash tables provide efficient mechanisms for storing and retrieving a data item based on an exact key, but are unsuitable when the search key is similar, but not identical, to the key used to store the data item. In this paper, we present a scalable and efficient peer-to-peer system with a new search primitive that can efficiently find the k data items with keys closest to the search key. The system works via a novel assignment of virtual coordinates to each object in a high-dimensional, synthetic space such that the proximity between two points in the coordinate space is correlated with the similarity between the strings that the points represent. We examine the feasibility of this approach for efficient, peer-to-peer search on inexact string keys, and show that the system provides a robust method to handle key perturbations that naturally occur in applications, such as file-sharing networks, where the query strings are provided by users.}, address = {Berkeley, CA, USA}, author = {Wong, Bernard and Vigf\'{u}sson, Ymir and Sirer, Emin G.}, booktitle = {HOTOS'07: Proceedings of the 11th USENIX workshop on Hot topics in operating systems}, citeulike-article-id = {6074614}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1361397.1361405}, keywords = {dht, overlay-network, p2p, peer-to-peer, structured-overlay-network}, location = {San Diego, CA}, pages = {1--6}, posted-at = {2009-11-05 14:37:55}, priority = {2}, publisher = {USENIX Association}, title = {Hyperspaces for object clustering and approximate matching in peer-to-peer overlays}, url = {http://portal.acm.org/citation.cfm?id=1361397.1361405}, year = {2007} }

TY - CONF ID - citeulike:6074614 L3 - citeulike-article-id:6074614 N2 - Existing distributed hash tables provide efficient mechanisms for storing and retrieving a data item based on an exact key, but are unsuitable when the search key is similar, but not identical, to the key used to store the data item. In this paper, we present a scalable and efficient peer-to-peer system with a new search primitive that can efficiently find the k data items with keys closest to the search key. The system works via a novel assignment of virtual coordinates to each object in a high-dimensional, synthetic space such that the proximity between two points in the coordinate space is correlated with the similarity between the strings that the points represent. We examine the feasibility of this approach for efficient, peer-to-peer search on inexact string keys, and show that the system provides a robust method to handle key perturbations that naturally occur in applications, such as file-sharing networks, where the query strings are provided by users. CY - San Diego, CA AD - Berkeley, CA, USA EP - 6 TI - Hyperspaces for object clustering and approximate matching in peer-to-peer overlays PB - USENIX Association T2 - HOTOS'07: Proceedings of the 11th USENIX workshop on Hot topics in operating systems SP - 1 KW - dht KW - overlay-network KW - p2p KW - peer-to-peer KW - structured-overlay-network AU - Wong, Bernard AU - Vigfússon, Ymir AU - Sirer, Emin PY - 2007/// UR - http://portal.acm.org/citation.cfm?id=1361397.1361405 ER -