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

Paolo Ferragina, S. Muthukrishnan, Mark de Berg

    Research output: Contribution to journalConference articlepeer-review


    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 - 1999
    EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
    Duration: May 1 1999May 4 1999

    ASJC Scopus subject areas

    • Software


    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