Current object oriented programming languages (OOPLs) rely on mono-method dispatching. Recent research has identified multi-methods as a new, powerful feature to be added to OOPLs, and several experimental OOPLs now have multi-methods. Their ultimate success and impact in practice depends, among other things, on whether multi-method dispatching can be supported efficiently. We show that the multi-method dispatching problem can be transformed to a geometric problem on multi-dimensional integer grids, for which we then develop a data structure that uses near-linear space and has log-logarithmic query time. This gives a solution whose performance almost matches that of the best known algorithm for mono-method dispatching. Our geometric data structure has other applications as well, namely in two string matching problems: matching multiple rectangular patterns against a rectangular query text, and approximate dictionary matching with edit distance at most one. Our results for the former, long-standing open problem are substantially improved, near-linear time bounds. For the latter problem, which has applications in checking password security and the design of filtering tools, we obtain a near-linear solution as well.
|Original language||English (US)|
|Number of pages||9|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1999|
|Event||Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA|
Duration: May 1 1999 → May 4 1999
ASJC Scopus subject areas