Abstract
ubsumption is used in knowledge representation and ontology to describe the relationship between concepts. Concept A is subsumed by concept B if the extension of A is always a subset of the extension of B, irrespective of the interpretation. The subsumption relation is also useful in other data analysis tasks such as pattern recognition – for example in image analysis to detect objects in an image, and in spectral data analysis to detect the presence of a reference pattern in a given spectrum. Sometimes the subsumption relation may not be 100% true, so it is useful to quantify this relationship.
In this paper we study how to quantify subsumption for sequential patterns. We review existing work on subsumption, give an axiomatic characterisation of subsumption, and present one general approach to quantification in terms of set intersection operation over concept extension. Constructing the concept extension set explicitly is impossible without specifying the domain of discourse and the interpretation. Instead, we focus on concept intension for sequences as patterns and propose to represent concept intension of a sequence by its subsequences. We further consider different types of concept intension set – subsequence set, subsequence multiset, embedding set and embedding set with constraints such as warping and selection. We then present a general algorithmic framework for computing set intersections, and specific algorithms for computing different concept intension sets. We also present an experimental evaluation of these algorithms with regard to their runtime performance.
In this paper we study how to quantify subsumption for sequential patterns. We review existing work on subsumption, give an axiomatic characterisation of subsumption, and present one general approach to quantification in terms of set intersection operation over concept extension. Constructing the concept extension set explicitly is impossible without specifying the domain of discourse and the interpretation. Instead, we focus on concept intension for sequences as patterns and propose to represent concept intension of a sequence by its subsequences. We further consider different types of concept intension set – subsequence set, subsequence multiset, embedding set and embedding set with constraints such as warping and selection. We then present a general algorithmic framework for computing set intersections, and specific algorithms for computing different concept intension sets. We also present an experimental evaluation of these algorithms with regard to their runtime performance.
Original language  English 

Pages (fromto)  7999 
Journal  Theoretical Computer Science 
Volume  793 
Early online date  13 Jun 2019 
DOIs  
Publication status  Published  01 Nov 2019 
Keywords
 Subsumption characterisation
 Subsumption quantification
 Sequence and subsequence analysis
 Sequence similarity
 Grid algorithm
Fingerprint
Dive into the research topics of 'Quantifying sequential subsumption'. Together they form a unique fingerprint.Profiles

Zhiwei Lin
 School of Mathematics and Physics  Senior Lecturer
 Mathematical Sciences Research Centre
Person: Academic