Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
ucin1337886738.pdf (1.48 MB)
ETD Abstract Container
Abstract Header
A Parallel Algorithm for Query Adaptive, Locality Sensitive Hash Search
Author Info
Carraher, Lee A.
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1337886738
Abstract Details
Year and Degree
2012, MS, University of Cincinnati, Engineering and Applied Science: Computer Science.
Abstract
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,”
Committee
Fred Annexation, PhD (Committee Chair)
Kenneth Berman, PhD (Committee Member)
Yizong Cheng, PhD (Committee Member)
Anca Ralescu, PhD (Committee Member)
Pages
102 p.
Subject Headings
Computer Science
Keywords
Locality Sensitive Hashing
;
Approximate Nearest Neighbors
;
CUDA GPU
;
Image Search
;
Distance Adaptive LSH
;
Parallel Computing
;
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
ucin1337886738
Download Count:
530
Copyright Info
© 2011, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.