Approximate nearest neighbor and its many variants
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/82408 |
| _version_ | 1811068945750294528 |
|---|---|
| author | Mahabadi, Sepideh |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Mahabadi, Sepideh |
| author_sort | Mahabadi, Sepideh |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T08:03:16Z |
| format | Thesis |
| id | mit-1721.1/82408 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:03:16Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/824082022-01-13T07:54:01Z Approximate nearest neighbor and its many variants Mahabadi, Sepideh Piotr Indyk. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. Cataloged from PDF version of thesis. Includes bibliographical references (p. 53-55). This thesis investigates two variants of the approximate nearest neighbor problem. First, motivated by the recent research on diversity-aware search, we investigate the k-diverse near neighbor reporting problem. The problem is defined as follows: given a query point q, report the maximum diversity set S of k points in the ball of radius r around q. The diversity of a set S is measured by the minimum distance between any pair of points in S (the higher, the better). We present two approximation algorithms for the case where the points live in a d-dimensional Hamming space. Our algorithms guarantee query times that are sub-linear in n and only polynomial in the diversity parameter k, as well as the dimension d. For low values of k, our algorithms achieve sub-linear query times even if the number of points within distance r from a query q is linear in n. To the best of our knowledge, these are the first known algorithms of this type that offer provable guarantees. In the other variant, we consider the approximate line near neighbor (LNN) problem. Here, the database consists of a set of lines instead of points but the query is still a point. Let L be a set of n lines in the d dimensional euclidean space Rd. The goal is to preprocess the set of lines so that we can answer the Line Near Neighbor (LNN) queries in sub-linear time. That is, given the query point ... we want to report a line ... (if there is any), such that ... for some threshold value r, where ... is the euclidean distance between them. We start by illustrating the solution to the problem in the case where there are only two lines in the database and present a data structure in this case. Then we show a recursive algorithm that merges these data structures and solve the problem for the general case of n lines. The algorithm has polynomial space and performs only a logarithmic number of calls to the approximate nearest neighbor subproblem. by Sepideh Mahabadi. S.M. 2013-11-18T19:19:21Z 2013-11-18T19:19:21Z 2013 2013 Thesis http://hdl.handle.net/1721.1/82408 862112830 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 55 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Mahabadi, Sepideh Approximate nearest neighbor and its many variants |
| title | Approximate nearest neighbor and its many variants |
| title_full | Approximate nearest neighbor and its many variants |
| title_fullStr | Approximate nearest neighbor and its many variants |
| title_full_unstemmed | Approximate nearest neighbor and its many variants |
| title_short | Approximate nearest neighbor and its many variants |
| title_sort | approximate nearest neighbor and its many variants |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/82408 |
| work_keys_str_mv | AT mahabadisepideh approximatenearestneighboranditsmanyvariants |