CS 573: Topics in Analysis of Algorithms (Spring 2006)
Advanced Data Structures

Main PageSchedule and Lecture NotesHomework and ProjectsAdministrivia


References

Pointers to free electronic papers were mined from CiteSeer, Google Scholar, and authors' personal web pages. Papers from the ACM Digital Library and most journals require a subscription, and thus may be inaccessible from off-campus; I will only link to these if no free version is available. *Stars indicate authors who (as far as I know) were graduate students when the paper was published. **Double stars indicate undergraduate authors. [No pressure!]

Surveys and monographs

[AE99]
Pankaj K. Agarwal and Jeff Erickson. Geometric range seraching and its relatives. Advances in Discrete and Computational Geometry (Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors), 1-56, 1999. Contemporary Mathematics 223, AMS Press.
[G05]
Leonidas Guibas. Kinetic data structures. Chapter 23 of Handbook of Data Structures and Applications (Dinesh P. Mehta and Sartaj Sahni, eds.), 23-1–23-18. Chapman and Hall/CRC, 2005.
[M99]
Peter Bro Miltersen. Cell probe complexity: A survey. Manuscript, 1999. [Powerpoint slides]
[O83]
Mark H. Overmars. The Design of Dynamic Data Structures. Lecture Notes in Computer Science 156, Spring-Verlag, 1983.
[T83]
Robert E. Tarjan. Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics 44, SIAM, 1983.

Papers

[AH97]
Susanne Albers* and Torben Hagerup. Improved parallel integer sorting without concurrent writing. Information and Computation 136:25-51, 1997.
[AHLT05]
Stephen Alstrup, Jacob Holm*, Kristian de Lichtenberg*, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms 1(2):243-264, 2005.
[A89]
Arne Anderson. Improving partial rebuilding by using simple balance criteria. Proc. Workshop on Algorithms and Data Structures, 393-402. Lecture Notes in Computer Science 382, Springer-Verlag, 1989.
[A99]
Arne Anderson. General balanced trees. J. Algorithms 30:1-28, 1999.
[AHNR98]
Arne Anderson, Torben Hagerup, Stefan Nilsson*, and Rajeev Raman. Sorting in linear time? J. Computer and System Sciences 57(1): 74-93, 1998.
[AV96]
Lars Arge* and Jeffrey S. Vitter. Optimal dynamic interval management in external memory. Proc. 37th IEEE Symposium on Foundations of Computer Science, 560-569, 1996.
[BGH99]
Julien Basch*, Leonidas Guibas, and John Hershberger. Data structures for mobile data. J. Algorithms 31(1):1-28, 1999.
[BGR03]
Julien Basch*, Leonidas Guibas, and G. D. Ramkumar*. Reporting red-blue intersections between two sets of conencted line segments. Algorithmica 35:1-20, 2003.
[BF02]
Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences 65(1):38-72, 2002.
[BW80]
Jon L. Bentley and Herman Maurer. Efficient worst-case data structures for range searching. Acta Informatica 13:155-168, 1980.
[BS80]
Jon L. Bentley and James B. Saxe*. Decomposable searching problems: 1. Static-to-dynamic transformations. J. Algorithms 1:301-358, 1980.
[BW80]
Jon L. Bentley and Derick Wood. An optimal algorithm for reporting intersections of rectangles. IEEE Trans. Computers C-29:571-577, 1980.
[C86]
Bernard Chazelle. Filtering search: A new approach to query answering. SIAM J. Comput. 15:703-724, 1986.
[CG86a]
Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica 1:133-162, 1986. [ Technical report version]
[CG86b]
Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: II. Applications. Algorithmica 1:163-191, 1986. [ Technical report version]
[DSW05]
Jonathan Derryberry*, Daniel D. Sleator, and Chengwen Chris Wang*. A lower bound framework for binary search trees with rotations. Technical Report CMU-CS-05-187, Carnegie Mellon University, November 22, 2005.
[DHIP04]
Erik D. Demaine, Dion Harmon*, John Iacono, and Mihai Pătraşcu**. Dynamic Optimality—Almost. Proc. 45th IEEE Symposium on Foundations of Computer Science, 484--490, 2004. Full version to appear in SIAM J. Computing
[E75]
Peter van Emde Boas. Preserving order in a forest in less than logarithmic time. Proc. 16th IEEE Symposium on Foundations of Computer Science, 75-84, 1975.
[E83a]
Herbert Edelsbrunner A new approach to rectangle intersections, Part I. Int. J. Computer Mathematics 13:209-219, 1983.
[E83b]
Herbert Edelsbrunner A new approach to rectangle intersections, Part II. Int. J. Computer Mathematics 13:221-229, 1983.
[EM81]
Herbert Edelsbrunner* and Herman A. Maurer. On the intersection of orthogonal objects. Information Processing Letters 13:177-181, 1981.
[FF02]
Guilherme D. da Fonseca* and Celina M. H. de Figueiredo. Kinetic heap-ordered trees: tight analysis and faster algorithms. Information Processing Letters 85(3):165-169, 2002.
[F97]
Greg Frederickson. A data structure for dynamically maintaining rooted trees. J. Algorithms 24:37-65, 1997.
[FW93]
Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. J. Computer and System Sciences 47(3):424-436, 1993. Originally entitled "BLASTING Through The Information Theoretic Barrier With FUSION TREES!!!1!11!!!eleven!!MCXI!!"
[GR93]
Igal Galperin* and Ronald L. Rivest. Scapegoat trees. Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 165-174, 1993. [ACM Digital Library]
[HS74]
Juris Hartmanis and Janos Simon*. On the power of multiplication in random access machines. Proc. 15th IEEE Symposium on Switching and Automata Theory, 13-23, 1974.
[HK99]
Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46:502-516, 1999.
[HLT01]
Jacob Holm*, Kristian de Lichtenberg*, Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of thhe ACM 48(4):723-760, 2001. [ACM Digital Library] See also technical reports DIKU-TR-97/17 and DIKU-TR-97/26, University of Copenhagen, September 1997.
[I05]
John Iacono. Key independent optimality. Algorithmica, 42:3--10, 2005.
[KR84]
David G Kirkpatrick and Stefan Reisch*. Upper bounds for sorting on random access machines. Theoretical Computer Science 28:263-276, 1984.
[M85]
Edward M. McCreight. Priority search trees. SIAM J. Comput. 14(2):257-276, 1985.
[OL81]
Mark H. Overmars* and Jan van Leeuwen. Maintenance of configurations in the plane. J. Computer and System Sciences 23:166-204, 1981.
[OL81a]
Mark H. Overmars* and Jan van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problems. Information Processing Letters 12(4):168-173, 1981.
[PD06]
Mihai Pătraşcu** and Erik Demaine. Logarithmic lower bounds in the cell-probe model. To appear in SIAM J. Computing.
[PT06]
Mihai Pătraşcu** and Mikkel Thorup. Time-space trade-offs for predecessor search. To appear in Proc. 38th ACM Symposium on Theory of Computing, 2006.
[ST83]
Daniel D. Sleator* and Robert E. Tarjan. A data structure for dynamic trees. J. Computer and System Sciences 26:362-391, 1983.
[ST85]
Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees. J. ACM 32:652-686, 1985. [HTML demo and C code]
[TW05]
Robert E. Tarjan and Renato Werneck*. Self-adjusting top trees. Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 813--822, 2005.
[WDS06]
Chengwen Chris Wang*. Jonathan Derryberry*, and Daniel D. Sleator. O(loglog n)-competitive binary search trees. Proc. 17th ACM-SIAM Symposium on Discrete Algorithms, 374-383, 2006.
[W87]
Robert E. Wilber*. Lower bounds for accessing binary search trees with rotations. SIAM J. Computing 18(1):56-67, 1987.
[W83]
Dan E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(n). Information Processing Letters 17(2):81-84 (1983).

See also these web pages for other advanced data structure courses:

Main PageSchedule and Lecture NotesHomework and ProjectsAdministrivia