IBSM: Interval-based sequence matching

Alexius Kotsifakos, Panagiotis Papapetrou, Vassilis Athitsos

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    Abstract

    Sequences of event intervals appear in several application domains including sign language, sensor networks, medicine, human motion databases, and linguistics. Such sequences comprise events that occur at time intervals and are time stamped at their start and end time. In this paper, we propose a new method, called IBSM, for comparing such sequences. IBSM performs full sequence matching using a vector-based representation of the original sequence. At, each time point an event vector is computed: hence, the original sequence is mapped to an ordered set of vectors, which we call event table. Given two sequences, their event tables are resized using bilinear interpolation, which ensures they are of the same size. The resulting event tables arc then compared using the Euclidean distance. In addition, we propose two techniques for reducing the computational cost of IBSM when performing nearest neighbor search in a large database. Extensive experiments on eight real datasets show that IBSM outperforms existing state-of-the-art methods by up to a factor of two in terms of nearest neighbor classification accuracy, and by up to two orders of magnitude in terms of runtime.

    Original languageEnglish
    Title of host publicationSIAM International Conference on Data Mining 2013, SMD 2013
    PublisherSociety for Industrial and Applied Mathematics Publications
    Pages596-604
    Number of pages9
    ISBN (Electronic)9781627487245
    DOIs
    Publication statusPublished - 2013
    MoE publication typeA4 Article in a conference publication
    EventSIAM International Conference on Data Mining - Austin, United States
    Duration: 2 May 20134 May 2013
    Conference number: 13

    Conference

    ConferenceSIAM International Conference on Data Mining
    Abbreviated titleSMD
    CountryUnited States
    CityAustin
    Period02/05/201304/05/2013

    Fingerprint Dive into the research topics of 'IBSM: Interval-based sequence matching'. Together they form a unique fingerprint.

  • Cite this

    Kotsifakos, A., Papapetrou, P., & Athitsos, V. (2013). IBSM: Interval-based sequence matching. In SIAM International Conference on Data Mining 2013, SMD 2013 (pp. 596-604). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611972832.66