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. The problem has two phases: the preprocessing phase and the query phase. The input to the first phase, the preprocessing phase, is a set of data from which to build some structure from memory cells. The input to the second phase, the query phase, is a query datum. The problem is to determine if the query datum was included in the original input data set. Operations are free except to access memory cells.
This model is useful in the analysis of data structures. In particular, the model clearly shows a minimum number of memory accesses to solve a problem in which there is stored data on which we would like to run some query. An example of such a problem is the dynamic partial sum problem.
History
In Andrew Yao's 1981 paper "Should Tables Be Sorted?", [1] Andrew described the cell-probe model and used it to give a minimum number of memory cell "probes" or accesses necessary to determine whether a given query datum exists within a table stored in memory.
Formal definition
Given a set of data construct a structure consisting of memory cells, each able to store bits. Then when given a query element determine whether with correctness by accessing memory cells. Such an algorithm is called an -error -probe algorithm using cells with word size . [2]
Notable results
Dynamic Partial Sums
Mihai Pătraşcu showed that the partial sums problem requires time per operation.[3][4]
TODO
Approximate Nearest Neighbor Searching
TODO [5]
See also
External links
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)