Bibliography

1

Free eBooks by Project Gutenberg.
Available from: http://www.gutenberg.org/ [cited 2011-10-12].

2

IEEE Standard for Floating-Point Arithmetic.
Technical report, Microprocessor Standards Committee of the IEEE Computer Society, 3 Park Avenue, New York, NY 10016-5997, USA, August 2008.
http://dx.doi.org/10.1109/IEEESTD.2008.4610935 doi:10.1109/IEEESTD.2008.4610935.

3

G. Adelson-Velskii and E. Landis.
An algorithm for the organization of information.
Soviet Mathematics Doklady, 3(1259-1262):4, 1962.

4

A. Aggarwal and J. S. Vitter.
The input/output complexity of sorting and related problems.
Communications of the ACM, 31(9):1116-1127, 1988.

5

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.

6

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.

7

A. Andersson.
General balanced trees.
Journal of Algorithms, 30(1):1-18, 1999.

8

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.

9

R. Bayer and E. M. McCreight.
Organization and maintenance of large ordered indexes.
In SIGFIDET Workshop, pages 107-141. ACM, 1970.

10

Bibliography on hashing.
Available from: http://liinwww.ira.uka.de/bibliography/Theory/hash.html [cited 2011-07-20].

11

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.

12

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.

13

A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, and R. Sedgewick.
Resizable arrays in optimal time and space.
In Dehne et al. [18], pages 37-48.

14

J. Carter and M. Wegman.
Universal classes of hash functions.
Journal of computer and system sciences, 18(2):143-154, 1979.

15

D. Comer.
The ubiquitous B-tree.
ACM Computing Surveys, 11(2):121-137, 1979.

16

C. Crane.
Linear lists and priority queues as balanced binary trees.
Technical Report STAN-CS-72-259, Computer Science Department, Stanford University, 1972.

17

S. Crosby and D. Wallach.
Denial of service via algorithmic complexity attacks.
In Proceedings of the 12th USENIX Security Symposium, pages 29-44, 2003.

18

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.

19

L. Devroye.
Applications of the theory of records in the study of random trees.
Acta Informatica, 26(1):123-130, 1988.

20

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.

21

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.

22

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.

23

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.

24

M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. M. auf der Heide, H. Rohnert, and R. E. Tarjan.
Dynamic perfect hashing: Upper and lower bounds.
SIAM J. Comput., 23(4):738-761, 1994.

25

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.

26

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.

27

M. Eytzinger.
Thesaurus principum hac aetate in Europa viventium (Cologne).
1590.
In commentaries, `Eytzinger' may appear in variant forms, including: Aitsingeri, Aitsingero, Aitsingerum, Eyzingern.

28

R. W. Floyd.
Algorithm 245: Treesort 3.
Communications of the ACM, 7(12):701, 1964.

29

M. Fredman, R. Sedgewick, D. Sleator, and R. Tarjan.
The pairing heap: A new form of self-adjusting heap.
Algorithmica, 1(1):111-129, 1986.

30

M. Fredman and R. Tarjan.
Fibonacci heaps and their uses in improved network optimization algorithms.
Journal of the ACM, 34(3):596-615, 1987.

31

M. L. Fredman, J. Komlós, and E. Szemerédi.
Storing a sparse table with 0 (1) worst case access time.
Journal of the ACM, 31(3):538-544, 1984.

32

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.

33

I. Galperin and R. 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.

34

A. Gambin and A. Malinowski.
Randomized meldable priority queues.
In SOFSEM’98: Theory and Practice of Informatics, pages 344-349. Springer, 1998.

35

M. T. Goodrich and J. G. Kloss.
Tiered vectors: Efficient dynamic arrays for rank-based sequences.
In Dehne et al. [18], pages 205-216.

36

G. Graefe.
Modern b-tree techniques.
Foundations and Trends in Databases, 3(4):203-402, 2010.

37

R. L. Graham, D. E. Knuth, and O. Patashnik.
Concrete Mathematics.
Addison-Wesley, 2nd edition, 1994.

38

L. 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.

39

C. A. R. Hoare.
Algorithm 64: Quicksort.
Communications of the ACM, 4(7):321, 1961.

40

J. E. Hopcroft and R. E. Tarjan.
Algorithm 447: Efficient algorithms for graph manipulation.
Communications of the ACM, 16(6):372-378, 1973.

41

J. E. Hopcroft and R. E. Tarjan.
Efficient planarity testing.
Journal of the ACM, 21(4):549-568, 1974.

42

HP-UX process management white paper, version 1.3, 1997.
Available from: http://h21007.www2.hp.com/portal/download/files/prot/files/STK/pdfs/proc_mgt.pdf [cited 2011-07-20].

43

M. S. Jensen and R. Pagh.
Optimality in external memory hashing.
Algorithmica, 52(3):403-411, 2008.

44

P. Kirschenhofer, C. Martinez, and H. Prodinger.
Analysis of an optimized search algorithm for skip lists.
Theoretical Computer Science, 144:199-220, 1995.

45

P. Kirschenhofer and H. Prodinger.
The path length of random skip lists.
Acta Informatica, 31:775-792, 1994.

46

D. Knuth.
Fundamental Algorithms, volume 1 of The Art of Computer Programming.
Addison-Wesley, third edition, 1997.

47

D. Knuth.
Seminumerical Algorithms, volume 2 of The Art of Computer Programming.
Addison-Wesley, third edition, 1997.

48

D. Knuth.
Sorting and Searching, volume 3 of The Art of Computer Programming.
Addison-Wesley, second edition, 1997.

49

C. Y. Lee.
An algorithm for path connection and its applications.
IRE Transaction on Electronic Computers, EC-10(3):346-365, 1961.

50

E. Lehman, F. T. Leighton, and A. R. Meyer.
Mathematics for Computer Science.
2011.
Available from: http://courses.csail.mit.edu/6.042/spring12/mcs.pdf [cited 2012-09-06].

51

C. Martínez and S. Roura.
Randomized binary search trees.
Journal of the ACM, 45(2):288-323, 1998.

52

E. F. Moore.
The shortest path through a maze.
In Proceedings of the International Symposium on the Theory of Switching, pages 285-292, 1959.

53

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.

54

Oracle.
The Collections Framework.
Available from: http://download.oracle.com/javase/1.5.0/docs/guide/collections/ [cited 2011-07-19].

55

R. Pagh and F. Rodler.
Cuckoo hashing.
Journal of Algorithms, 51(2):122-144, 2004.

56

T. Papadakis, J. I. Munro, and P. V. Poblete.
Average search and update costs in skip lists.
BIT, 32:316-332, 1992.

57

M. Ptracu 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.

58

M. Ptracu and M. Thorup.
The power of simple tabulation hashing.
Journal of the ACM, 59(3):14, 2012.

59

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].

60

W. Pugh.
Skip lists: A probabilistic alternative to balanced trees.
Communications of the ACM, 33(6):668-676, 1990.

61

Redis.
Available from: http://redis.io/ [cited 2011-07-20].

62

B. Reed.
The height of a random binary search tree.
Journal of the ACM, 50(3):306-332, 2003.

63

S. M. Ross.
Probability Models for Computer Science.
Academic Press, Inc., Orlando, FL, USA, 2001.

64

R. Sedgewick.
Left-leaning red-black trees, September 2008.
Available from: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf [cited 2011-07-21].

65

R. Seidel and C. Aragon.
Randomized search trees.
Algorithmica, 16(4):464-497, 1996.

66

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.

67

Z. Shao, J. H. Reppy, and A. W. Appel.
Unrolling lists.
In Proceedings of the 1994 ACM conference LISP and Functional Programming (LFP'94), pages 185-195, New York, 1994. ACM.

68

P. Sinha.
A memory-efficient doubly linked list.
Linux Journal, 129, 2005.
Available from: http://www.linuxjournal.com/article/6828 [cited 2013-06-05].

69

SkipDB.
Available from: http://dekorte.com/projects/opensource/SkipDB/ [cited 2011-07-20].

70

D. Sleator and R. 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.

71

S. P. Thompson.
Calculus Made Easy.
MacMillan, Toronto, 1914.
Project Gutenberg EBook 33283.
Available from: http://www.gutenberg.org/ebooks/33283 [cited 2012-06-14].

72

P. van Emde Boas.
Preserving order in a forest in less than logarithmic time and linear space.
Inf. Process. Lett., 6(3):80-82, 1977.

73

J. Vuillemin.
A data structure for manipulating priority queues.
Communications of the ACM, 21(4):309-315, 1978.

74

J. Vuillemin.
A unifying look at data structures.
Communications of the ACM, 23(4):229-239, 1980.

75

D. E. Willard.
Log-logarithmic worst-case range queries are possible in space $\Theta(N)$.
Inf. Process. Lett., 17(2):81-84, 1983.

76

J. Williams.
Algorithm 232: Heapsort.
Communications of the ACM, 7(6):347-348, 1964.