Bounded LSH for similarity search in peer-to-peer file systems

Yu Hua, Bin Xiao, Dan Feng, Bo Yu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

18 Citations (Scopus)

Abstract

Similarity search has been widely studied in peer-to-peer environments. In this paper, we propose the Bounded Locality Sensitive Hashing (Bounded LSH) method for similarity search in P2P file systems. Compared to the basic Locality Sensitive Hashing (LSH), Bounded LSH makes improvement on the space saving and quick query response in the similarity search, especially for high-dimensional data objects that exhibit non-uniform distribution property. We present simple and space-efficient Bounded-LSH to map non-uniform data space into load-balanced hash buckets that contain approximate number of objects. Load-balanced hash buckets in Bounded-LSH, in turn, require less number of hash tables while maintaining a high probability of returning the closest objects to requests. Our experiments based on synthetic and real-world datasets showed the feasibility, query and space efficiency of our proposed method.
Original languageEnglish
Title of host publicationProceedings - 37th International Conference on Parallel Processing, ICPP 2008
Pages644-651
Number of pages8
DOIs
Publication statusPublished - 17 Nov 2008
Event37th International Conference on Parallel Processing, ICPP 2008 - Portland, OR, United States
Duration: 9 Sep 200812 Sep 2008

Conference

Conference37th International Conference on Parallel Processing, ICPP 2008
CountryUnited States
CityPortland, OR
Period9/09/0812/09/08

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Cite this