Approximate nearest neighbor problem in high dimensions
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2006
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/33106 |
| _version_ | 1826203723259445248 |
|---|---|
| author | Andoni, Alexandr |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Andoni, Alexandr |
| author_sort | Andoni, Alexandr |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005. |
| first_indexed | 2024-09-23T12:42:02Z |
| format | Thesis |
| id | mit-1721.1/33106 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:42:02Z |
| publishDate | 2006 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/331062019-04-10T13:59:02Z Approximate nearest neighbor problem in high dimensions Andoni, Alexandr Piotr Indyk. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005. Includes bibliographical references (p. 47-49). We investigate the problem of finding the approximate nearest neighbor when the data set points are the substrings of a given text T. The exact version of this problem is defined as follows. Given a text T of length n, we want to build a data structure that supports the following operation: given a pattern P, find the substring of T that is the closest to P. Since the exact version of this problem is surprisingly difficult, we address the approximate version, in which we are allowed to return a substring of T that is at most c times further than the actual closest substring of T. This problem occurs, for example, in computational biology [4, 5]. In particular, we study the case where the length of the pattern P, denoted by m, is not known in advance, which is the most natural scenario. We present a data structure that uses O(n1+1/c) space and has 0 (nl/c + mn⁰(l)) query time' when the distance between two strings is the Hamming distance. These bounds essentially match the earlier bounds of [12], which assumed that the pattern length m is fixed in advance. Furthermore, our data structure can be constructed in O (n1+1/c + n1+⁰(1)M1/3) time, where M is an upper bound for m. This time essentially matches the preprocessing time of [12] as long as the term O(n1+1/c) dominates the running time, which is the case when, for example, c < 3. We also extend our results to the case where the distances are measured according to the lI distance. The query time and the space bound are essentially the same, while the preprocessing time becomes 6 (n'+/c + nl+o(l)M2/3) (We use notation f(n) = O(g(n)) to denote f(n) = g(n) logO(1) g(n)). by Alexandr Andoni. M.Eng. 2006-06-19T17:41:05Z 2006-06-19T17:41:05Z 2005 2005 Thesis http://hdl.handle.net/1721.1/33106 62221782 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 49 p. 2357516 bytes 2358044 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Andoni, Alexandr Approximate nearest neighbor problem in high dimensions |
| title | Approximate nearest neighbor problem in high dimensions |
| title_full | Approximate nearest neighbor problem in high dimensions |
| title_fullStr | Approximate nearest neighbor problem in high dimensions |
| title_full_unstemmed | Approximate nearest neighbor problem in high dimensions |
| title_short | Approximate nearest neighbor problem in high dimensions |
| title_sort | approximate nearest neighbor problem in high dimensions |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/33106 |
| work_keys_str_mv | AT andonialexandr approximatenearestneighborprobleminhighdimensions |