Efficient Algorithms for Managing the History of Evolving Databases.

@inproceedings{DBLP:conf/icdt/TsotrasG90,
  author    = {Vassilis J. Tsotras and
               B. Gopinath},
  editor    = {Serge Abiteboul and
               Paris C. Kanellakis},
  title     = {Efficient Algorithms for Managing the History of Evolving Databases},
  booktitle = {ICDT'90, Third International Conference on Database Theory, Paris,
               France, December 12-14, 1990, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {470},
  year      = {1990},
  isbn      = {3-540-53507-1},
  pages     = {141-174},
  ee        = {http://dx.doi.org/10.1007/3-540-53507-1_75},
  crossref  = {DBLP:conf/icdt/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

...

[2]

Miklós Ajtai, Michael L. Fredman, János Komlós: Hash Functions for Priority Queues. FOCS 1983: 299-303

[3]

Bernard Chazelle: How to Search in History. Information and Control 64(1-3): 77-99(1985)

[4]

Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan: Dynamic Perfect Hashing: Upper and Lower Bounds. FOCS 1988: 524-531

[5]

David P. Dobkin, J. Ian Munro: Efficient Uses of the Past. FOCS 1980: 200-206

[6]

Amos Fiat, Moni Naor: Implicit O(1) Probe Search. STOC 1989: 336-344

[7]

Amos Fiat, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, Alan Siegel: Storing and Searching a Multikey Table (Extended Abstract). STOC 1988: 344-353

[8]

Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel: Non-Oblivious Hashing (Extended Abstract). STOC 1988: 367-376

[9]

...

[10]

Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31(3): 538-544(1984)

[11]

Michael L. Fredman, Michael E. Saks: The Cell Probe Complexity of Dynamic Data Structures. STOC 1989: 345-354

[12]

Gaston H. Gonnet: Expected Length of the Longest Probe Sequence in Hash Code Searching. J. ACM 28(2): 289-304(1981)

[13]

...

[14]

J. Ian Munro: Searching a Two Key Table Under a Single Key. STOC 1987: 383-387

[15]

...

[16]

Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3

[17]

Marc Snir: On Parallel Searching. SIAM J. Comput. 14(3): 688-708(1985)

[18]

...

[19]

...

[20]

Leslie G. Valiant: Parallelism in Comparison Problems. SIAM J. Comput. 4(3): 348-355(1975)

[21]

Peter van Emde Boas, R. Kaas, E. Zijlstra: Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory 10: 99-127(1977)

[22]

Dan E. Willard: Log-Logarithmic Worst-Case Range Queries are Possible in Space Theta(N). Inf. Process. Lett. 17(2): 81-84(1983)

[23]

Andrew Chi-Chih Yao: Should Tables Be Sorted? J. ACM 28(3): 615-628(1981)