Discussion on Skiplists

Additional notes

Skiplists were introduced by PughW. Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668–676, 1990. who also presented a number of applications and extensions of skiplistsW. Pugh. A skip list cookbook. Technical report, Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland, College Park, 1989.. Since then they have been studied extensively. Several researchers have done very precise analysesP. Kirschenhofer, C. Martinez, and H. Prodinger. Analysis of an optimized search algorithm for skip lists. Theoretical Computer Science, 144:199–220, 1995. of the expected length and variance of the length of the search pathP. Kirschenhofer and H. Prodinger. The path length of random skip lists. Acta Informatica, 31:775–792, 1994. for the $i$th element in a skiplistT. Papadakis, J. I. Munro, and P. V. Poblete. Average search and update costs in skip lists. BIT, 32:316–332, 1992.. Deterministic versionsJ. I. Munro, T. Papadakis, and R. Sedgewick. Deterministic skip lists. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA’92), pages 367–375, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics., biasedA.Bagchi,A.L.Buchsbaum,andM.T.Goodrich.Biasedskiplists.In P. Bose and P. Morin, editors, Algorithms and Computation, 13th Inter- national Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer Science, pages 1–13. Springer, 2002. versionsF. Ergun, S. C. Sahinalp, J. Sharp, and R. Sinha. Biased dictionaries with fast insert/deletes. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 483–491, New York, NY, USA, 2001. ACM., and self-adjusting versionsP. Bose, K. Dou ̈ıeb, and S. Langerman. Dynamic optimality for skip lists and b-trees. In S.-H. Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20–22, 2008, pages 1106– 1114. SIAM, 2008. of skiplists have all been developed. Skiplist implementations have been written for various languages and frameworks and have been used in open-source database systemsRedis. URL: http://redis.io/ [cited 2011-07-20].. A variant of skiplists is used in the HP-UXHP-UX process management white paper, version 1.3, 1997. operating system kernel’s process management structures.