Lower Bounds for Hamming NNS Hamming spaceX={0,1]d database y∈Xm time:t cell-probes; space:s cells,each of w bits deterministic randomized t=2 [Miltersen et al.1995] t=2 () [Barkol Rabani 2000] exact t=n(og=)[Patascu Thorup2006t=(ioe=）】 [Patrascu Thorup 2006] t=2 [Liu2004) t=日 log log d log log1ogd丿 for s=poly(n) t=o[Patrascu Thorup 2006] [Chakrabarti Regev 2004] approx
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ [Miltersen et al.1995] [Pătraşcu Thorup 2006] [Barkol Rabani 2000] [Pătraşcu Thorup 2006] [Liu 2004] [Pătraşcu Thorup 2006] [Chakrabarti Regev 2004] for s = poly(n) time: t cell-probes; space: s cells, each of w bits t = ⇥ ⇣ log log d log log log d ⌘
Lower Bounds for Hamming NNS Hamming spaceX={0,1]d database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized t= () [Miltersen et al1995] t=2 [Barkol Rabani 2000] exact [Patrascu'Thorup 20061 [Patrascu Thorup 2006 t=2 [Liu2004] t=( log log d log log log d for s=poly(n) approx. =o [Patrascu Thorup 2006] [Chakrabarti Regev 2004] t=n() [Panigrahy Talwar Wieder 2008,2010]
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ log n log sw n ⌘ [Miltersen et al.1995] [Pătraşcu Thorup 2006] [Barkol Rabani 2000] [Pătraşcu Thorup 2006] [Liu 2004] [Pătraşcu Thorup 2006] [Panigrahy Talwar Wieder 2008, 2010] [Chakrabarti Regev 2004] for s = poly(n) time: t cell-probes; space: s cells, each of w bits t = ⇥ ⇣ log log d log log log d ⌘
Lower Bounds for Hamming NNS Hamming spaceX={0,1]d database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized t=2 [Miltersen et al1995] t=2 o) [Barkol Rabani 2000] exact =o[Patrascu Thorup2006] t=(每） [Patrascu Thorup 2006] t=2 (o) [Wang Y.2014] t=2 [iu2004 t= log log d log log log d for s=poly(n) =o[Patrascu Thorup 2006] [Chakrabarti Regev 2004] approx. t=(器) [Wang Y.2014] t=n() [Panigrahy Talwar Wieder 2008,2010]
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ log n log sw n ⌘ [Miltersen et al.1995] [Pătraşcu Thorup 2006] [Barkol Rabani 2000] [Pătraşcu Thorup 2006] [Liu 2004] [Pătraşcu Thorup 2006] [Panigrahy Talwar Wieder 2008, 2010] [Chakrabarti Regev 2004] for s = poly(n) time: t cell-probes; space: s cells, each of w bits t = ⌦ [Wang Y. 2014] ⇣ d log sw nd ⌘ [Wang Y. 2014] t = ⌦ ⇣ d log sw nd ⌘ t = ⇥ ⇣ log log d log log log d ⌘
Lower Bounds for Hamming NNS Hamming spaceX={0,1]d database y∈Xm time:t cell-probes; space:s cells,each of w bits deterministic randomized t= [Miltersen et al1995] t=2 o) [Barkol Rabani 2000] exact =o[Patrascu Thorup2006] t=2() ）Patrascu Thorup2006 t=2 (o) [Wang Y.2014] t=2 [iu2004 t-O loglog d logloglog d for s=poly(n) t=[Patrascu Thorup 2006] [Chakrabarti Regev 2004] approx. for search problem t=(s) [Wang Y.2014] t=(品器) [Panigrahy Talwar Wieder 2008,2010]
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ log n log sw n ⌘ [Miltersen et al.1995] [Pătraşcu Thorup 2006] [Barkol Rabani 2000] [Pătraşcu Thorup 2006] [Liu 2004] [Pătraşcu Thorup 2006] [Panigrahy Talwar Wieder 2008, 2010] [Chakrabarti Regev 2004] for s = poly(n) time: t cell-probes; space: s cells, each of w bits t = ⌦ [Wang Y. 2014] ⇣ d log sw nd ⌘ [Wang Y. 2014] t = ⌦ ⇣ d log sw nd ⌘ t = ⇥ ⇣ log log d log log log d ⌘ for search problem
Lower Bounds for Hamming NNS Hamming spaceX={0,1]d database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized t=2 [Miltersen et al1995] t=2 o) [Barkol Rabani 2000] exact =o[Patrascu Thorup2006] t=(每） [Patrascu Thorup 2006] t=2 (o) [Wang Y.2014] t=2 [iu2004 t= log log d log log log d for s=poly(n) =o[Patrascu Thorup 2006] [Chakrabarti Regev 2004] approx. t=(器) [Wang Y.2014] t=n() [Panigrahy Talwar Wieder 2008,2010]
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ d log s ⌘ t = ⌦ ⇣ d log sw n ⌘ t = ⌦ ⇣ log n log sw n ⌘ [Miltersen et al.1995] [Pătraşcu Thorup 2006] [Barkol Rabani 2000] [Pătraşcu Thorup 2006] [Liu 2004] [Pătraşcu Thorup 2006] [Panigrahy Talwar Wieder 2008, 2010] [Chakrabarti Regev 2004] for s = poly(n) time: t cell-probes; space: s cells, each of w bits t = ⌦ [Wang Y. 2014] ⇣ d log sw nd ⌘ [Wang Y. 2014] t = ⌦ ⇣ d log sw nd ⌘ t = ⇥ ⇣ log log d log log log d ⌘