A. Andersson.
Improving partial rebuilding by using simple balance criteria.
In F. K. H. A. Dehne, J.-R. Sack, and N. Santoro, editors, Algorithms and Data Structures, Workshop WADS '89, Ottawa, Canada, August
17-19, 1989, Proceedings, volume 382 of Lecture Notes in Computer
Science, pages 393-402. Springer, 1989.
A. Andersson.
Balanced search trees made simple.
In F. K. H. A. Dehne, J.-R. Sack, N. Santoro, and S. Whitesides,
editors, Algorithms and Data Structures, Third Workshop, WADS '93,
Montréal, Canada, August 11-13, 1993, Proceedings, volume 709 of Lecture Notes in Computer Science, pages 60-71. Springer, 1993.
A. Bagchi, A. L. Buchsbaum, and M. T. Goodrich.
Biased skip lists.
In P. Bose and P. Morin, editors, Algorithms and Computation,
13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November
21-23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer
Science, pages 1-13. Springer, 2002.
J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway.
UMAC: Fast and secure message authentication.
In M. J. Wiener, editor, Advances in Cryptology - CRYPTO '99,
19th Annual International Cryptology Conference, Santa Barbara, California,
USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in
Computer Science, pages 79-79. Springer, 1999.
P. 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.
F. K. H. A. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, editors.
Algorithms and Data Structures, 6th International Workshop, WADS
'99, Vancouver, British Columbia, Canada, August 11-14, 1999, Proceedings,
volume 1663 of Lecture Notes in Computer Science. Springer, 1999.
P. Dietz and J. Zhang.
Lower bounds for monotonic list labeling.
In J. R. Gilbert and R. G. Karlsson, editors, SWAT 90, 2nd
Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 11-14, 1990,
Proceedings, volume 447 of Lecture Notes in Computer Science, pages
173-180. Springer, 1990.
M. Dietzfelbinger.
Universal hashing and $ k$-wise independent random variables via
integer arithmetic without primes.
In C. Puech and R. Reischuk, editors, STACS 96, 13th Annual
Symposium on Theoretical Aspects of Computer Science, Grenoble, France,
February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in
Computer Science, pages 567-580. Springer, 1996.
M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger.
Polynomial hash functions are reliable.
In W. Kuich, editor, Automata, Languages and Programming, 19th
International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992,
Proceedings, volume 623 of Lecture Notes in Computer Science, pages
235-246. Springer, 1992.
M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen.
A reliable randomized algorithm for the closest-pair problem.
Journal of Algorithms, 25(1):19-51, 1997.
M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide,
H. Rohnert, and R. E. Tarjan.
Dynamic perfect hashing: Upper and lower bounds.
SIAM Journal on Computing, 23(4):738-761, 1994.
A. Elmasry.
Pairing heaps with
$ O(\log\log n)$ decrease cost.
In Proceedings of the twentieth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 471-476. Society for Industrial and Applied
Mathematics, 2009.
F. 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.
M. Eytzinger.
Thesaurus principum hac aetate in Europa viventium (Cologne).
1590.
In commentaries, `Eytzinger' may appear in variant forms, including:
Aitsingeri, Aitsingero, Aitsingerum, Eyzingern.
M. L. Fredman and D. E. Willard.
Surpassing the information theoretic bound with fusion trees.
Journal of computer and system sciences, 47(3):424-436, 1993.
I. Galperin and R.L. Rivest.
Scapegoat trees.
In Proceedings of the fourth annual ACM-SIAM Symposium on
Discrete algorithms, pages 165-174. Society for Industrial and Applied
Mathematics, 1993.
L.J. Guibas and R. Sedgewick.
A dichromatic framework for balanced trees.
In 19th Annual Symposium on Foundations of Computer Science, Ann
Arbor, Michigan, 16-18 October 1978, Proceedings, pages 8-21. IEEE Computer
Society, 1978.
P. Kirschenhofer, C. Martinez, and H. Prodinger.
Analysis of an optimized search algorithm for skip lists.
Theoretical Computer Science, 144:199-220, 1995.
J. 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.
M. P{\v{a\/}}\kern.05emtra{\c{s\/}}cu and M. Thorup.
Randomization does not help searching predecessors.
In N. Bansal, K. Pruhs, and C. Stein, editors, Proceedings of
the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007,
New Orleans, Louisiana, USA, January 7-9, 2007, pages 555-564. SIAM, 2007.
W. Pugh.
A skip list cookbook.
Technical report, Institute for Advanced Computer Studies, Department
of Computer Science, University of Maryland, College Park, 1989.
Available from: ftp://ftp.cs.umd.edu/pub/skipLists/cookbook.pdf [cited 2011年07月20日].
H. H. Seward.
Information sorting in the application of electronic digital
computers to business operations.
Master's thesis, Massachusetts Institute of Technology, Digital
Computer Laboratory, 1954.
D.D. Sleator and R.E. Tarjan.
Self-adjusting binary trees.
In Proceedings of the 15th Annual ACM Symposium on Theory of
Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 235-245.
ACM, ACM, 1983.