Leveraging Edit Distance to Reveal Hidden Patterns in Sequences of Sets

Abstract In this paper, we analyze the edit-distance-based approach to classification of sequences of sets. Our goal is to push the edit distance measure to its limits to see just how weak a signal it can detect when applied to sequences of sets. It is a thorough experimental study exploring various aspects of the measure in isolation. To achieve this, we needed precise control over the characteristics of the experimental data. That is why we also propose a flexible dataset generator capable of controlling the main properties of the sequences of sets model, which we make publicly available as an online tool. To give our analysis better context, in each experiment we evaluate the edit distance approach against a standard bag of words approach. Our study uncovers a vast range of findings (from trivial to surprising), which we thoroughly discuss in the paper and, based on them, provide general guidelines on the classification of sequences of sets. Among others, we find that edit distance is in fact able to successfully capture all the main characteristics of sequences of sets --- even the most subtle ones! Moreover, the proposed dataset generator proved to be a very powerful tool with much broader applications than the scope of this paper and can be used to create benchmarks for any data processing algorithms involving sequences of sets.