Always when I read about any efficient persistent data structures they use pointer computational model. I'm wondering if you know any efficient implementation which uses power of RAM model?
Add a comment
|
$\begingroup$
$\endgroup$
Paul F. Dietz's "Fully Persistent Arrays" uses a variant on van Emde Boas trees, which rely on arrays and also on integers being represented as words.
Brodal et al.'s "Fully Persistent B-Trees" relies on arrays.
Davoodi et al.'s "Cache-Oblivious Persistence" applies a persistence transform to data structures that don't necessarily work in the pointer model.
The Bentley-Saxe logarithmic method, also known as cache-oblivious lookahead arrays is naturally partially persistent, and relies on arrays for the insert time to be $o(\log_B n)$ in an external-memory setting.
