Tag Archives: geometrics

Some Progress

Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.

Near(est) Neighbor Problems in Hamming Space

1

Fully-Adaptive Non-Adaptive
Deterministical Randomized Deterministical Randomized
λ-ENN Ω(dlogn) for ploy
Ω(d/logn)[2] for poly
Ω(d/logsdn) [6]
λ-ENNS
ENNS
λ-ANN
Ω(dγ3/logsdn) [6]
Ω(dγ3/logswγ3nd) [9]
Θ(1) for poly
ω(1)[1] for sub-poly
Θ(1) for poly
ω(1)[1] for sub-poly
λ-ANNS Θ(1) for poly
Θ(1) for poly
LSH.11https://en.wikipedia.org/wiki/Locality-sensitive_hashing
s=O(dn+n1+ρ)
t=O(nρ)
ρ1/γ [4]
ρ=Θ(1/γ) [5]
ANNS
Θ(loglogdlogloglogd)[3] for poly
Ω(loglogd)[7] for linear
Ω(logn/γ2logswn) [8]
Θ(logdlogγ) for poly
Ω(logn/logswdnlogn) [8]
Continue reading