I. Abraham, J. Aspnes, and J. Yuan, Skip B-Trees, Proc. of the 9th Annual International Conference on Principles of Distributed Systems (OPODIS), p.366, 2006.
DOI : 10.1109/TNET.2002.808407

U. A. Acar, G. E. Blelloch, R. Harper, J. L. Vittes, and S. L. Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.531-540, 2004.

A. Aggarwal and J. S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, vol.31, issue.9, pp.1116-1127, 1988.
DOI : 10.1145/48529.48535
URL : https://hal.archives-ouvertes.fr/inria-00075827

O. Amble and D. E. Knuth, Ordered hash tables, The Computer Journal, vol.17, issue.2, pp.135-142, 1974.
DOI : 10.1093/comjnl/17.2.135

A. Andersson and T. Ottmann, Faster uniquely represented dictionaries, [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp.642-649, 1991.
DOI : 10.1109/SFCS.1991.185430

C. R. Aragon and R. G. Seidel, Randomized search trees, Proc. of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.540-545, 1989.

L. Arge, D. Eppstein, and M. T. Goodrich, Skip-webs, Proceedings of the twenty-fourth annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , PODC '05, pp.69-76, 2005.
DOI : 10.1145/1073814.1073827

J. Aspnes and G. Shah, Skip graphs, ACM Transactions on Algorithms, vol.3, issue.4, p.37, 2007.
DOI : 10.1145/1290672.1290674

S. Bajaj, A. Chakraborti, and R. Sion, The foundations of history independence. arXiv preprint, 2015.

S. Bajaj and R. Sion, Ficklebase: Looking into the future to erase the past, 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp.86-97, 2013.
DOI : 10.1109/ICDE.2013.6544816

S. Bajaj and R. Sion, HIFS, Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, CCS '13, pp.1285-1296, 2013.
DOI : 10.1145/2508859.2516724

M. A. Bender, R. Cole, and R. Raman, Exponential Structures for Efficient Cache-Oblivious Algorithms, Proc. of the 29th Annual International Colloquium on Automata, Languages, and Programming (ICALP), pp.195-207, 2002.
DOI : 10.1007/3-540-45465-9_18

M. A. Bender, E. D. Demaine, and M. Farach-colton, Cache-Oblivious B-Trees, SIAM Journal on Computing, vol.35, issue.2, pp.341-358, 2005.
DOI : 10.1137/S0097539701389956

M. A. Bender, Z. Duan, J. Iacono, and J. Wu, A locality-preserving cache-oblivious dynamic dictionary, Journal of Algorithms, vol.53, issue.2, pp.115-136, 2004.
DOI : 10.1016/j.jalgor.2004.04.014

M. A. Bender, M. Farach-colton, and B. C. , Cache-oblivious string B-trees, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '06, pp.233-242, 2006.
DOI : 10.1145/1142351.1142385

M. A. Bender, J. T. Fineman, S. Gilbert, and B. C. , Concurrent cache-oblivious b-trees, Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures , SPAA'05, pp.228-237, 2005.
DOI : 10.1145/1073970.1074009

M. A. Bender and H. Hu, An adaptive packed-memory array, ACM Transactions on Database Systems, vol.32, issue.4, p.26, 2007.
DOI : 10.1145/1292609.1292616

J. Bethencourt, D. Boneh, and B. Waters, Cryptographic methods for storing ballots on a voting machine, Proc. of the 14th Network and Distributed System Security Symposium (NDSS), 2007.

G. E. Blelloch and D. Golovin, Strongly History-Independent Hashing with Applications, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp.272-282, 2007.
DOI : 10.1109/FOCS.2007.36

G. E. Blelloch, D. Golovin, and V. Vassilevska, Uniquely Represented Data Structures for Computational Geometry, Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT), pp.17-28, 2008.
DOI : 10.1007/978-3-540-69903-3_4

G. S. Brodal, R. Fagerberg, and R. Jacob, Cache Oblivious Search Trees via Binary Trees of Small Height, Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.39-48, 2002.
DOI : 10.7146/brics.v8i36.21696

N. Buchbinder and E. Petrank, Lower and upper bounds on obtaining history independence, Advances in Cryptology, pp.445-462, 2003.

J. Bulánek, M. Kouck-`-kouck-`-y, and M. Saks, Tight lower bounds for the online labeling problem, Proc. of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp.1185-1198, 2012.

P. Callahan, M. T. Goodrich, and K. Ramaiyer, Topology B-trees and their applications, Proc. of the 4th International Workshop on Algorithms and Data Structures (WADS), pp.381-392, 1995.
DOI : 10.1007/3-540-60220-8_78

V. Ciriani, P. Ferragina, F. Luccio, and S. Muthukrishnan, Static optimality theorem for external memory string access, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp.219-227, 2002.
DOI : 10.1109/SFCS.2002.1181945

L. Devroye, A limit theory for random skip lists. The Annals of Applied Probability, pp.597-609, 1992.

M. Fomitchev and E. Ruppert, Lock-free linked lists and skip lists, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, pp.50-59, 2004.
DOI : 10.1145/1011767.1011776

M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-oblivious algorithms, Proc. of the 40th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), pp.285-298, 1999.

M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-oblivious algorithms, ACM Transactions on Algorithms, vol.8, issue.1, p.4, 2012.

D. Golovin, Uniquely Represented Data Structures with Applications to Privacy, 2008.

D. Golovin, B-Treaps: A Uniquely Represented Alternative to B-Trees, Proc. of the 36th Annual International Colloquium on Automata, Languages, and Programming (ICALP), pp.487-499, 2009.
DOI : 10.1007/978-3-642-02927-1_41

D. Golovin, The B-skip-list: A simpler uniquely represented alternative to B-trees. arXiv preprint, 2010.

M. T. Goodrich and R. Tamassia, Efficient authenticated dictionaries with skip lists and commutative hashing, p.15, 2000.

J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul et al., Lest we remember, Communications of the ACM, vol.52, issue.5, pp.91-98, 2009.
DOI : 10.1145/1506409.1506429

J. D. Hartline, E. S. Hong, A. E. Mohr, W. R. Pentney, and E. C. Rocke, Characterizing History Independent Data Structures, Algorithmica, vol.42, issue.1, pp.57-74, 2005.
DOI : 10.1007/s00453-004-1140-z

M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit, A Simple Optimistic Skiplist Algorithm, Proc. of the 14th Annual Colloquium on Structural Information and Communication Complexity (SIROCCO), p.124, 2007.
DOI : 10.1007/978-3-540-72951-8_11

A. Itai, A. Konheim, and M. Rodeh, A sparse table implementation of priority queues, Proc. of the 8th Annual International Colloquium on Automata, Languages, and Programming (ICALP), pp.417-431, 1981.
DOI : 10.1007/3-540-10843-2_34

R. Jacob, A. Richa, C. Scheideler, S. Schmid, and H. Täubig, A distributed polylogarithmic time algorithm for self-stabilizing skip graphs, Proceedings of the 28th ACM symposium on Principles of distributed computing, PODC '09, pp.131-140, 2009.
DOI : 10.1145/1582716.1582741

Z. Kasheff, Cache-oblivious dynamic search trees, 2004.

P. Kirschenhofer and H. Prodinger, The path length of random skip lists, Acta Informatica, vol.43, issue.42, pp.31775-792, 1994.
DOI : 10.1007/BF01178735

D. Micciancio, Oblivious data structures, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.456-464, 1997.
DOI : 10.1145/258533.258638

D. Molnar, T. Kohno, N. Sastry, and D. Wagner, Tamper-evident, history-independent, subliminal-free data structures on PROM storage -or- how to store ballots on a voting machine, 2006 IEEE Symposium on Security and Privacy (S&P'06), 2006.
DOI : 10.1109/SP.2006.39

T. Moran, M. Naor, and G. Segev, Deterministic History-Independent Strategies for Storing Information on Write-Once Memories, Proc. of the 34th International Colloquium on Automata, Languages and Programming (ICALP), 2007.
DOI : 10.1007/978-3-540-73420-8_28

M. Naor, G. Segev, and U. Wieder, History-Independent Cuckoo Hashing, Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp.631-642, 2008.
DOI : 10.1007/978-3-540-70583-3_51

M. Naor and V. Teague, Anti-persistence: history independent data structures, Proc. of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp.492-501, 2001.

J. Nievergelt and E. M. Reingold, Binary Search Trees of Bounded Balance, SIAM Journal on Computing, vol.2, issue.1, pp.33-43, 1973.
DOI : 10.1137/0202005

R. Oshman and N. Shavit, The SkipTrie, Proceedings of the 2013 ACM symposium on Principles of distributed computing, PODC '13, pp.23-32, 2013.
DOI : 10.1145/2484239.2484270

T. Papadakis, J. I. Munro, and P. V. Poblete, Analysis of the expected search cost in skip lists, Proc. of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT), pp.160-172, 1990.
DOI : 10.1007/3-540-52846-6_86

H. Prokop, Cache oblivious algorithms Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology [52] W. Pugh. Incremental computation and the incremental evaluation of functional programs, 1988.

W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, vol.33, issue.6, pp.668-676, 1990.
DOI : 10.1145/78973.78977

W. Pugh and T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages , POPL '89, pp.315-328, 1989.
DOI : 10.1145/75277.75305

N. Rahman, R. Cole, and R. Raman, Optimised Predecessor Data Structures for Internal Memory, Proc. of the 5th International Workshop on Algorithm Engineering (WAE), pp.67-78, 2001.
DOI : 10.1007/3-540-44688-5_6

D. S. Roche, A. J. Aviv, and S. G. Choi, Oblivious secure deletion with bounded history independence, 2015.

N. Shavit and I. Lotan, Skiplist-based concurrent priority queues, Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000, pp.263-268, 2000.
DOI : 10.1109/IPDPS.2000.845994

J. Shun and G. E. Blelloch, Phase-concurrent hash tables for determinism, Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, SPAA '14, pp.96-107, 2014.
DOI : 10.1145/2612669.2612687

L. Snyder, On uniquely represented data strauctures, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pp.142-146, 1977.
DOI : 10.1109/SFCS.1977.22

R. Sundar and R. E. Tarjan, Unique binary search tree representations and equality-testing of sets and sequences, Proc. of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp.18-25, 1990.

T. Tzouramanis, History-independence, Proceedings of the 27th Annual ACM Symposium on Applied Computing, SAC '12, pp.7-12, 2012.
DOI : 10.1145/2245276.2245279

J. S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software, vol.11, issue.1, pp.37-57, 1985.
DOI : 10.1145/3147.3165

D. E. Willard, Inserting and deleting records in blocked sequential files, 1981.

D. E. Willard, Maintaining dense sequential files in a dynamic environment, Proc. of the 14th Annual ACM Symposium on Theory of Computing (STOC), pp.114-121, 1982.

D. E. Willard, Good worst-case algorithms for inserting and deleting records in dense sequential files, ACM SIGMOD Record, vol.15, issue.2, pp.251-260, 1986.
DOI : 10.1145/16856.16879

D. E. Willard, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Information and Computation, vol.97, issue.2, pp.150-204, 1992.
DOI : 10.1016/0890-5401(92)90034-D