Cell-Probe Model data structure problem: f:X×Y→☑ query x∈X f(x,y) database algorithm A: CPU y∈Y (decision tree) t adaptive table cell-probes code T w bits T:Y→∑s s cells (words) where∑={0,1}w protocol:the pair (A,T) (s,w,t)-cell-probing scheme
code T table query x 2 X t adaptive cell-probes Cell-Probe Model } w bits ( s cells (words) algorithm A: ⌃ = {0, 1}w where (decision tree) protocol: the pair (A, T) database y 2 Y T : Y ! ⌃s f : X ⇥ Y ! Z data structure problem: (s, w, t)-cell-probing scheme f(x, y)
Lower Bounds for Hamming NNS Hamming space={0,1]4 database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized exact approx
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn time: t cell-probes; space: s cells, each of w bits
Lower Bounds for Hamming NNS Hamming space={0,1)4 database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized t=(o) [Miltersen et al1995] exact approx
Lower Bounds for Hamming NNS deterministic randomized exact approx. Hamming space X = {0, 1}d database y 2 Xn t = ⌦ ⇣ d log s ⌘ [Miltersen et al.1995] time: t cell-probes; space: s cells, each of w bits
Lower Bounds for Hamming NNS Hamming spaceX={0,1}a database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized t=(io) Milersena5] t=(ioua) Barkol Rabani 2000] exact t=() [Liu2004 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 s ⌘ t = ⌦ ⇣ d log s ⌘ [Miltersen et al.1995] [Barkol Rabani 2000] [Liu 2004] time: t cell-probes; space: s cells, each of w bits
Lower Bounds for Hamming NNS Hamming space={0,1)d database y∈Xn time:t cell-probes; space:s cells,each of w bits deterministic randomized =() Milersena5] 1=() [Barkol Rabani 2000] exact t=() [Liu2004 t=6 log log d log log iog d for s=poly(n) [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 s ⌘ t = ⌦ ⇣ d log s ⌘ [Miltersen et al.1995] [Barkol Rabani 2000] [Liu 2004] [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 ⌘