Time and Space Efficient Multi-Method Dispatching

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

Technical Report, ITU-TR-2001-8, The IT University of Copenhagen, 13 pages, October 2001.


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

Copyright © 2001, The IT University of Copenhagen. All rights reserved.

Online version

itu-tr-01-8.pdf (114 Kb)

BIBTEX entry

  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Inge Li G{\o}rtz and Theis Rauhe",
  institution = "The IT University of Copenhagen",
  month = "October",
  number = "ITU-TR-2001-8",
  pages = "13",
  title = "Time and Space Efficient Multi-Method Dispatching",
  year = "2001"