Cell-probe model

This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template. In computer science, the cell-probe model is a model of computation in which cost is only associated with memory access.

TODO

Formal definition

TODO^[1]

Notable results

Dynamic Partial Sums

Mihai Pătraşcu showed that the partial sums problem requires $\Omega \left(\log n\right)$ time per operation.^[2] ^[3]

TODO

Approximate Nearest Neighbor Searching

TODO ^[4]

External links

NIST's Dictionary of Algorithms and Data Structures entry on the cell probe model

References

^ Yao, Andrew Chi-Chih (July 1981). "Should Tables Be Sorted?". J. ACM. 28 (3): 615–628. doi:10.1145/322261.322274.
^ Pătraşcu, Mihai (2006). "Logarithmic lower bounds in the cell-probe model". SIAM Journal on Computing. 35 (4): 932–963. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Pătraşcu, Mihai. "Lower Bounds for Dynamic Partial Sums" (PDF). Retrieved 9 April 2014.
^ Chakrabarti, Amit (2004). "An optimal randomised cell probe lower bound for approximate nearest neighbour searching". Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science: 473–482. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[1] Yao, Andrew Chi-Chih (July 1981). "Should Tables Be Sorted?". J. ACM. 28 (3): 615–628. doi:10.1145/322261.322274.

[2] Pătraşcu, Mihai (2006). "Logarithmic lower bounds in the cell-probe model". SIAM Journal on Computing. 35 (4): 932–963. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[3] Pătraşcu, Mihai. "Lower Bounds for Dynamic Partial Sums" (PDF). Retrieved 9 April 2014.

[4] Chakrabarti, Amit (2004). "An optimal randomised cell probe lower bound for approximate nearest neighbour searching". Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science: 473–482. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[1]

[2]

[3]

[4]