{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:13:35Z","timestamp":1725484415455},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"},{"type":"electronic","value":"9783540454717"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45471-3_3","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T17:18:22Z","timestamp":1179767902000},"page":"20-29","source":"Crossref","is-referenced-by-count":3,"title":["Time and Space Efficient Multi-method Dispatching"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Alstrup","sequence":"first","affiliation":[]},{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"additional","affiliation":[]},{"given":"Inge","family":"Li G\u00f8rtz","sequence":"additional","affiliation":[]},{"given":"Theis","family":"Rauhe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"S. Alstrup, T. Husfeldt, and T. Rauhe. Marked ancestor problems (extended abstract). In IEEE Symposium on Foundations of Computer Science (FOCS), pages 534\u2013543, 1998.","DOI":"10.7146\/brics.v5i16.21956"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"D. G. Bobrow, L. G. DeMichiel, R. P. Gabriel, S. E. Keene, G. Kiczales, and D. A. Moon. Common LISP object system specification X3J13 document 88-002R. ACM SIGPLAN Notices, 23, 1988. Special Issue, September 1988.","DOI":"10.1145\/885631.885632"},{"key":"3_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BFb0053029","volume-title":"ECOOP\u2019 92, European Conference on Object-Oriented Programming, Utrecht, The Netherlands","author":"C. Chambers","year":"1992","unstructured":"Craig Chambers. Object-oriented multi-methods in Cecil. In Ole Lehrmann Madsen, editor, ECOOP\u2019 92, European Conference on Object-Oriented Programming, Utrecht, The Netherlands, volume 615 of Lecture Notes in Computer Science, pages 33\u201356. Springer-Verlag, New York, NY, 1992."},{"key":"3_CR4","unstructured":"Inc. Apple Computer. Dylan interim reference manual, 1994."},{"key":"3_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-51542-9_8","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures","author":"P. F. Dietz","year":"1989","unstructured":"P. F. Dietz. Fully persistent arrays. In F. Dehne, J.-R. Sack, and N. Santoro, editors, Proceedings of the Workshop on Algorithms and Data Structures, volume 382 of Lecture Notes in Computer Science, pages 67\u201374, Berlin, August 1989. Springer-Verlag."},{"key":"3_CR6","unstructured":"Paul F. Dietz and Rajeev Raman. Persistence, amortization and randomization. In Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 78\u201388, 1991."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. In 29th Annual Symposium on Foundations of Computer Science (FOCS), pages 524\u2013531. IEEE Computer Society Press, 1988.","DOI":"10.1109\/SFCS.1988.21968"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J. R. Driscoll","year":"1989","unstructured":"J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan. Making data structures persistent. J. Computer Systems Sci., 38(1):86\u2013124, 1989.","journal-title":"J. Computer Systems Sci."},{"key":"3_CR9","unstructured":"David Eppstein and S. Muthukrishnan. Internet packet filter manegement and rectangle geometry. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001."},{"key":"3_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/3-540-61680-2_50","volume-title":"European Symposium on Algorithms","author":"P. Ferragina","year":"1996","unstructured":"P. Ferragina and S. Muthukrishnan. Efficient dynamic method-lookup for object oriented languages. In European Symposium on Algorithms, volume 1136 of Lecture Notes in Computer Science, pages 107\u2013120, 1996."},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"P. Ferragina, S. Muthukrishnan, and M. de Berg. Multi-method dispatching: A geometric approach with applications to string matching problems. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 483\u2013491, New York, May 1\u20134 1999. ACM Press.","DOI":"10.1145\/301250.301378"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1142\/S0129054196000117","volume":"7","author":"R. Fleischer","year":"1996","unstructured":"R. Fleischer. A simple balanced search tree with O(1) worst-case update time. International Journal of Foundations of Computer Science, 7:137\u2013149, 1996.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopoulos","year":"1988","unstructured":"C. Levcopoulos and M. Overmars. A balanced search tree with O(1) worstcase update time. Acta Informatica, 26:269\u2013277, 1988.","journal-title":"Acta Informatica"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn and S. N\u00e4her. Bounded ordered dictionaries in O(loglogn) time and O(n) space. Information Processing Letters, 35:183\u2013189, 1990.","journal-title":"Information Processing Letters"},{"key":"3_CR15","unstructured":"S. Muthukrishnan and Martin M\u00fcller. Time and space efficient method-lookup for object-oriented programs (extended abstract). In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 42\u201351, Atlanta, Georgia, January 28\u201330 1996."},{"key":"3_CR16","unstructured":"R. Raman. Eliminating Amortization: On Data Structures with Guaranteed Response Time. PhD thesis, University of Rochester, Computer Science Department, October 1992. Technical Report TR439."},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669\u2013679, 1986.","journal-title":"Communications of the ACM"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1978","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6:80\u201382, 1978.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T06:42:18Z","timestamp":1556433738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438663","9783540454717"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}