Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    Two-dimensional point set pattern matching with horizontal scaling

    Sixth BCS-IRSG Symposium on Future Directions in Information Access (FDIA 2015)

    31 August - 4 September 2015, Thessaloniki, Greece


    Antti Laaksonen



    This paper focuses on two-dimensional point set pattern matching with horizontal scaling. Given a dataset S of n points and a pattern P of m points, the task is to find occurrences of P in S. The pattern may be horizontally scaled using a constant value. This problem is relevant in symbolic music information retrieval when each point is interpreted as a musical note and the pattern is a melody that is searched for. The best known general algorithm for the problem works in O(n2 m) time. In this paper we show that the 3SUM problem can be reduced to this problem, and present a new algorithm that works in O(n2) time on typical inputs.


    PDF file PDF Version of this Paper (486kb)