Loading...
Please wait, while we are loading the content...
Similar Documents
Approximate nearest neighbor (ANN) search in high dimensions
| Content Provider | Semantic Scholar |
|---|---|
| Author | Har-Peled, Sariel |
| Copyright Year | 2011 |
| Abstract | x 17.1 ANN on the Hypercube 17.1.1 Hypercube and Hamming distance Definition 17.1.1 The set of points H d = 0, 1 d is the d-dimensional hypercube. A point p = (p 1 ,. .. , p d) ∈ H d can be interpreted, naturally, as a binary string p 1 p 2. .. p d. The Hamming distance d H (p, q) between p, q ∈ H d , is the number of coordinates where p and q disagree. It is easy to verify that the Hamming distance comply with the triangle inequality, and is thus a metric. As we saw in previously, all we need to solve (1 + ε)-ANN efficiently, is to efficiently solve the approximate near neighbor problem. Namely, given a set P of n points in H d , a radius r > 0 and parameter ε > 0, we want to decide for a query point q whether d H Definition 17.1.2 For a set P of points, a data-structure D = D D ≈NearNbr (P, r, (1 + ε)r) solves the approximate near neighbor problem, if given a query point q, the data-structure works as follows. Given such a data-structure one can construct a data-structure that answers approximate nearest neighbor query using O log (log d)/ε queries using an approximate near-neighbor data-structure. Indeed, the desired distance d H (q, P) is an integer number in the range 0, 1,. .. , d. We can build a D D ≈NearNbr data-structure for distances (1+ε) |
| Starting Page | 269 |
| Ending Page | 277 |
| Page Count | 9 |
| File Format | PDF HTM / HTML |
| DOI | 10.1090/surv/173/20 |
| Alternate Webpage(s) | http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/18_lsh.pdf |
| Alternate Webpage(s) | https://doi.org/10.1090/surv%2F173%2F20 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
