Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

A Parallel Algorithm for Query Adaptive, Locality Sensitive Hash Search

Carraher, Lee A.

Abstract Details

2012, MS, University of Cincinnati, Engineering and Applied Science: Computer Science.
Nearest neighbor search is a fundamental requirement of many machine learning algorithms and is essential to fuzzy information retrieval. The utility of efficient database search and construction has broad utility in a variety of computing fields. Applications such as coding theory and compression for electronic communication systems as well as use in artificial intelligence for pattern and object recognition. In this thesis, a particular subset of nearest neighbors is consider, referred to as c-approximate k-nearest neighbors search. This particular variation relaxes the constraints of exact nearest neighbors by introducing a probability of finding the correct nearest neighbor c, which offers considerable advantages to the computational complexity of the search algorithm and the database overhead requirements. Furthermore, it extends the original nearest neighbors algorithm by returning a set of k candidate nearest neighbors, from which expert or exact distance calculations can be considered. Furthermore thesis extends the implementation of c-approximate k-nearest neighbors search so that it is able to utilize the burgeoning GPGPU computing field. The specific form of c-approximate k-nearest neighbors search implemented is based on the locality sensitive hash search from the E2LSH package of Indyk and Andoni [1]. In this paper, the authors utilize the exceptional properties of the Leech Lattice [2], as a subspace quantizer for the locality sensitive hash families. The Leech Lattice is unique in that it provides the closest lattice packing of equal sized spheres in 24 dimensional space. In addition, advances from coding theory provide a very favorable decoding algorithm for finding the nearest lattice center to a query point in euclidean 24 dimensional space [3] [4]. The multilevel construction of the Leech Lattice provides an excellent opportunity for parallelization as it contains the minimization of many independent sub-lattice decodings resulting from the lattices exceptional symmetry among lattices. These decodings are additionally highly floating point computationally intensive, and because of which suggest a favorable implementation on GPGPU architectures such as NVIDIAs CUDA based framework. Furthermore, the overall construction of a locality sensitive hash based, nearest neighbors search algorithm, is able to be parallelized fairly efficiently as the hash decodings are completely independent of one another. The goal of this thesis is to present a CUDA optimized parallel implementation of a bounded distance Leech Lattice decoder [4] for use in query optimized c-approximate k-nearest neighbors using the locality sensitive hash framework of E2LSH. The system will be applied to the approximate image retrieval of SIFT transformed [5] image vectors. [1] A. Andoni, Nearest Neighbor Search: the Old, the New, and the Impossible. INSTITUTE OF [2] J. Leech, “Notes on sphere packings,” [3] . J. Forney, G. D., “A bounded-distance decoding algorithm for the leech lattice, with generalizations,” [4] O. Amrani and Y. Beery, “Efficient bounded-distance decoding of the hexacode and associated decoders for the leech lattice and the golay code,” [5] D. G. Lowe, “Object recognition from local scale-invariant features,”
Fred Annexation, PhD (Committee Chair)
Kenneth Berman, PhD (Committee Member)
Yizong Cheng, PhD (Committee Member)
Anca Ralescu, PhD (Committee Member)
102 p.

Recommended Citations

Citations

  • Carraher, L. A. (2012). A Parallel Algorithm for Query Adaptive, Locality Sensitive Hash Search [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1337886738

    APA Style (7th edition)

  • Carraher, Lee. A Parallel Algorithm for Query Adaptive, Locality Sensitive Hash Search. 2012. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1337886738.

    MLA Style (8th edition)

  • Carraher, Lee. "A Parallel Algorithm for Query Adaptive, Locality Sensitive Hash Search." Master's thesis, University of Cincinnati, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1337886738

    Chicago Manual of Style (17th edition)