The "Square Root" Solution of Oblivious RAM Simulation I am reading the paper Software Protection and Simulation on Oblivious RAMs by Oded Goldreich and Rafail Ostrovsky. And I wonder about the description of the "Square Root" solution of oblivious RAM simulation at page 20. 

The algorithm seems simple: the aim is to 'simluate' the original RAM of size $m$ by an oblivious RAM of size $m+2\sqrt{m}$. So it uses the first $m+\sqrt{m}$ cells of the oblivious RAM to shuffle or to obscure,  and uses the last $\sqrt{m}$ cells as a cache (or shelter) in case of leaking information about access frequency. 

However, the first step to use the shelter reads 'first, we scan through the entire shelter and check whether the contents of the virtual word $i$ is in one of the shelter's words. '

Here, we want to simulate an original RAM access at location $i$ (for fetching the virtual word $i$) by using the shelter, and then comes the question : since we haven't known what the contents of virtual word $i$ actually was yet, how do we check whether it has been in the shelter or not?
Presumably, the shelter could store a bunch of pairs $(a,v)$ where $v$ is the contents of the virtual word at address $a$.  Then, to scan through the shelter to see whether it has the value of the virtual word at address $i$, you'd just check whether the shelter contains any pair $(a,v)$ where $a=i$.

I don't know whether this is actually what Goldreich and Ostrovsky do, but it seems like one natural candidate scheme that could be used.