Multi-method dispatching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-method dispatching: a geometric approach with applications to string matching problems

Full text

Pdf (885 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 483 - 491

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Paolo Ferragina	Dipartimento di Informatica, Università di Pisa, Italy
S. Muthukrishnan	Mathematical Science Center, Bell Labs, Murray Hill, NJ
Mark de Berg	Department of Computer Science, Utrecht University, the Netherlands

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 27, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301378 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	A91	Rakesh Agrawal , Linda G. Demichiel , Bruce G. Lindsay, Static type checking of multi-methods, Conference proceedings on Object-oriented programming systems, languages, and applications, p.113-128, October 06-11, 1991, Phoenix, Arizona, United States
	AC75	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	AD96	Eric Amiel , Eric Dujardin, Supporting Explicit Disambiguation of Multi-Methods, Proceedings of the 10th European Conference on Object-Oriented Programming, p.167-188, July 08-12, 1996
	ADS96	E. Amiel, E. Dujaxdin and E. Simon. Fast algorithms for compressed muiti-method dispatch tables generation. Technical Report # 2977, INRIA, Sept. 1996.
	AF92	Amihood Amir , Martin Farach, Two-dimensional dictionary matching, Information Processing Letters, v.44 n.5, p.233-239, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90206-B]
	AFILS92	Amihood Amir , Martin Farach , Ramana M. Idury , Johannes A. La Poutré , Alejandro A. Schäffer, Improved dynamic dictionary matching, Information and Computation, v.119 n.2, p.258-282, June 1995 [doi>10.1006/inco.1995.1090]
	Ap94	Apple Computer. Dylan Interim Reference Manual, June, 1994.
	BN96	Ricardo A. Baeza-Yates , Gonzalo Navarro, A Faster Algorithm for Approximate String Matching, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.1-23, June 10-12, 1996
	BN97a	Ricardo A. Baeza-Yates , Gonzalo Navarro, Multiple Approximate String Matching, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.174-184, August 06-08, 1997
	B78	T.P. Baker. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Uomp., 7:533-541, I978.
	BK+97	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	BD+88	Daniel G. Bobrow , Linda G. DeMichiel , Richard P. Gabriel , Sonya E. Keene , Gregor Kiczales , David A. Moon, Common Lisp Object System specification, ACM SIGPLAN Notices, v.23 n.SI, p.1-142, September 1988 [doi>10.1145/885631.885632]
	BK+86	Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
	BG96	Gerth Stølting Brodal , Leszek Gasieniec, Approximate Dictionary Queries, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.65-74, June 10-12, 1996
	BC96	John Boyland , Giuseppe Castagna, Parasitic methods: an implementation of multi-methods for Java, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.66-76, October 05-09, 1997, Atlanta, Georgia, United States
	BC+95	Kim Bruce , Luca Cardelli , Giuseppe Castagna , Gary T. Leavens , Benjamin Pierce, On binary methods, Theory and Practice of Object Systems, v.1 n.3, p.221-242, Fall 1995
	CL95	Giuseppe Castagna , Gary T. Leavens, Foundations of Object-Oriented Languages: 2nd Workshop report, ACM SIGPLAN Notices, v.30 n.2, p.5-11, Feb. 1995 [doi>10.1145/199873.607638]
	Ch92	Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
	Ch96	Craig Chambers, Synergies Between Object-Oriented Programming Language Design and Implementation Research, Proceedings of the Second JSSST International Symposium on Object Technologies for Advanced Software, p.250-259, March 11-15, 1996
	ChL95	Craig Chambers , Gary T. Leavens, Typechecking and modules for multimethods, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.6, p.805-843, Nov. 1995 [doi>10.1145/218570.218571]
	C86	Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
	C97	Giuseppe Castagna, Object-oriented programming: a unified foundation, Birkhauser Boston Inc., Cambridge, MA, 1997
	CG86	B. Chazelle and L. J. Guibas. Fractional Cascading I: A data structuring technique. Algorithmica, 133-162, 1986.
	CTK94	Weimin Chen , Volker Turau , Wolfgang Klas, Efficient Dynamic Look-Up Strategy for Multi-Methods, Proceedings of the 8th European Conference on Object-Oriented Programming, p.408-431, July 04-08, 1994
	D93	K. Driesen. Method lookup strategies in dynamically-typed object-oriented programming languages. Master's thesis, Vrije Universiteit Brussel, 1993.
	D96	E. Dujaxdin. Effcient dispatch of multimethods in constant time using dispatch trees. Technical Report # 2892, INRIA, May 1996.
	EKC98	Michael Ernst , Craig Kaplan , Craig Chambers, Predicate Dispatching: A Unified Theory of Dispatch, Proceedings of the 12th European Conference on Object-Oriented Programming, p.186-211, July 20-24, 1998
	EM81	H. Edelsbrunner and H. Maurer. On the intersection of orthogonal objects. Information Processing Letters 13, 177-181, 1981.
	FM96	Paolo Ferragina , S. Muthukrishnan, Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.107-120, September 25-27, 1996
	GBT84	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	G93	Rafaele Giancarlo, The Suffix of a square matrix, with applications, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.402-411, January 25-27, 1993, Austin, Texas, United States
	GB91	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	IS93	Ramana M. Idury , Alejandro A. Schäffer, Multiple matching of rectangular patterns, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.81-90, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167116]
	LM98	Gary T. Leavens , Todd D. Millstein, Multiple dispatch as dispatch on Tuples, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.374-387, October 18-22, 1998, Vancouver, British Columbia, Canada
	MW94	Udi Manber , Sun Wu, An algorithm for approximate membership checking with application to password security, Information Processing Letters, v.50 n.4, p.191-197, May 25, 1994 [doi>10.1016/0020-0190(94)00032-8]
	Mc85	E.M. McCreight. Priority Search Trees. SteAM Journal of Computing, 14(2):257-276, 1985.
	Mehl84	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	MHH91	Warwick B. Mugridge , John Hamer , John G. Hosking, Multi-Methods in a Statically-Typed Programming Language, Proceedings of the European Conference on Object-Oriented Programming, p.307-324, July 15-19, 1991
	M95	M. Mfiller. Method dispatch in dynamicallytyped object-oriented languages. M~ster's thesis, University of New Mexico Albuquerque, 1995.
	MM96a	Robert Muth , Udi Manber, Approximate Multiple Strings Search, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.75-86, June 10-12, 1996
	MM96b	S. Muthukrishnan , Martin Müller, Time and space efficient method-lookup for object-oriented programs, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.42-51, January 28-30, 1996, Atlanta, Georgia, United States
	Mye94	G. Myers. A sublinear algorithm for approximate key word searching. Algorithmica, 12(4/5):345- 374, 1994.
	N97	G. Navarro. Multiple approximate string matching by counting. Proc. South American Workshop on String Processing, 95-111, 1997.
	O88b	Mark H. Overmars, Efficient data structures for range searching on a grid, Journal of Algorithms, v.9 n.2, p.254-275, June 1988 [doi>10.1016/0196-6774(88)90041-7]
	PW95	P.A. Pevzner and M. S. Waterman. MultAple filtration and approximate pattern matching,. Algorithmica, 13(112):135-154, January 1995.
	V82	V.K. Vashnaivi. Computing point enclosures. IEEE Trans. Comp., 22-29, 1982.
	V95	J. Vitek. Compact dispatch tables for dynamically-typed object-oriented languages. Research thesis, University of British Columbia, Vancouver, 1995.
	YY95	Andrew C. Yao , Frances F. Yao, Dictionary look-up with one error, Journal of Algorithms, v.25 n.1, p.194-202, Oct. 1997 [doi>10.1006/jagm.1997.0875]
	W83	D.E. WJ}lard: Log-Logarithmic worst-case range queries are possible in space O(N). Information Processing Letters, 17(2): 81-84, 1983.

CITED BY 5

	David Eppstein , S. Muthukrishnan, Internet packet filter management and rectangle geometry, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.827-835, January 07-09, 2001, Washington, D.C., United States
	Yoav Zibin , Joseph Yossi Gil, Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Mikkel Thorup, Space efficient dynamic stabbing with fast queries, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Richard Cole , Lee-Ad Gottlieb , Moshe Lewenstein, Dictionary matching and indexing with errors and don't cares, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Lorenzo Bettini , Sara Capecchi , Betti Venneri, Double dispatch in C++, Software—Practice & Experience, v.36 n.6, p.581-613, May 2006