@book{a5bdd940be0d45388927d52d4dc65d92,
title = "Time and Space Efficient Multi-Method Dispatching",
abstract = "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¨ uller 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.",
keywords = "Dispatching problem, Object-oriented languages, Method invocation, Execution performance, Data structures",
author = "Stephen Alstrup and G{\o}rtz, \{Inge Li\} and Theis Rauhe and Gerth Brodal",
year = "2001",
month = oct,
language = "English",
series = "IT University Technical Report Series",
number = "TR-2001-8",
publisher = "IT-Universitetet i K{\o}benhavn",
address = "Denmark",
edition = "TR-2001-8",
}