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

Paolo Ferragina, Shan Muthukrishnan, Mark de Berg

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)483-491
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Multi-method dispatching: A geometric approach with applications to string matching problems'. Together they form a unique fingerprint.

Cite this