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 similar to the Random-access machine, except that all operations are free except memory access. This model is useful for proving lower bounds of algorithms for data structure problems.

Overview

The cell-probe model is a minor modification of the Random-access machine model, itself a minor modification of the Counter machine model, in which computational cost is only assigned to accessing units of memory called cells.

In this model, computation is framed as a problem of querying a set of memory cells.

History

Andrew Yao wrote a paper entitled "Should Tables Be Sorted?" in 1981^[1] which the number of memory cell "probes" or accesses are necessary to determine whether a given query datum exists within a table stored in memory.

Formal definition

Given a set of data $S$ construct a structure consisting of $c$ memory cells, each able to store $w$ bits. Then when given a query element $s$ determine whether $s\in S$ with correctness $1-\varepsilon$ by accessing $t$ memory cells. Such an algorithm is called an $\varepsilon$ -error $t$ -probe algorithm using $c$ cells with word size $w$ . ^[2]

Notable results

Dynamic Partial Sums

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

TODO

Approximate Nearest Neighbor Searching

TODO ^[5]

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.
^ 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)
^ 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] 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)

[3] 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)

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

[5] 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]

[5]