Time and Space Efficient Multi-Method Dispatching

Stephen Alstrup, Gerth Stølting Brodal, Inge Li Gørtz, and Theis Rauhe

In Proc. 8th Scandinavian Workshop on Algorithm Theory, volume 2368 of Lecture Notes in Computer Science, pages 20-29. Springer Verlag, Berlin, 2002.


The dispatching problem for object oriented languages is the problem of determining the most specialized method to invoke for calls at run-time. This can be a critical component of execution performance. A number of recent results, including [Muthukrishnan and Müller SODA'96, Ferragina and Muthukrishnan ESA'96, Alstrup et al. FOCS'98], have studied this problem and in particular provided various efficient data structures for the mono-method dispatching problem. A recent paper of Ferragina, Muthukrishnan and de Berg [STOC'99] addresses the multi-method dispatching problem.

Our main result is a linear space data structure for binary dispatching that supports dispatching in logarithmic time. Using the same query time as Ferragina et al., this result improves the space bound with a logarithmic factor.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2002. All rights reserved.

Online version

swat02.pdf (148 Kb)




BIBTEX entry

  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Inge Li G{\o}rtz and Theis Rauhe",
  booktitle = "Proc. 8th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/3-540-45471-3_3",
  isbn = "978-3-540-43866-3",
  pages = "20-29",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Time and Space Efficient Multi-Method Dispatching",
  volume = "2368",
  year = "2002"

Other versions