Cell-probe model

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.


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.[1][2]


In Andrew Yao's 1981 paper "Should Tables Be Sorted?",[3] Yao 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 definitionEdit

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  . [4]

Notable resultsEdit

Dynamic Partial SumsEdit

The dynamic partial sum problem defines two operations Update  which conceptually operation sets the value in an array   at index   to be  , and Sum  which returns the sum of the values in   at indices   through  . Such an implementation would take   time for Update and   time for Sum.[5]

Instead, if the values are stored as leaves in a tree whose inner nodes store the values of the subtree rooted at that node. In this structure Update requires   time to update each node in the leaf to root path, and Sum similarly requires   time to traverse the tree from leaf to root summing the values of all subtrees left of the query index.

Mihai Pătraşcu used the cell-probe model and an information transfer argument to show that the partial sums problem requires   time per operation.[1][2]

Approximate Nearest Neighbor SearchingEdit

The exact nearest neighbor search problem is to determine the closest in a set of input points to a given query point. An approximate version of this problem is often considered since many applications of this problem are in very high dimension spaces and solving the problem in high dimensions requires exponential time or space with respect to the dimension.[4]

Chakrabarti and Regev proved that the approximate nearest neighbor search problem on the Hamming cube using polynomial storage and   word size requires a worst-case query time of  . This proof used the cell-probe model and information theoretic techniques for communication complexity.

External linksEdit


  1. ^ a b Pătraşcu, Mihai; Demaine, Erik D. (2006). "Logarithmic lower bounds in the cell-probe model". SIAM Journal on Computing. 35 (4): 932–963. arXiv:cs/0502041. Bibcode:2005cs........2041P. doi:10.1137/s0097539705447256.
  2. ^ a b Pătraşcu, Mihai. "Lower Bounds for Dynamic Partial Sums" (PDF). Retrieved 9 April 2014.
  3. ^ Yao, Andrew Chi-Chih (July 1981). "Should Tables Be Sorted?". J. ACM. 28 (3): 615–628. doi:10.1145/322261.322274.
  4. ^ a b Chakrabarti, Amit; Regev, Oded (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.
  5. ^ Zatloukal, Kevin (November 10, 2010). "Notes on "Logarithmic Lower Bounds in the Cell-Probe Model"" (PDF). Retrieved 9 April 2014.