None of the data generated while you wait in the checkout line at a grocery store, click through pages when browsing e-commerce websites, or participate in laboratory DNA sequencing exists in isolation. Within these sequences that carry inherent logical chronological order, the order of events holds the same informational value as the events themselves.
For decades, computer scientists have developed tools to process massive volumes of ordered data and extract valuable, meaningful patterns. The core field that underpins this line of research and development is sequential pattern mining. Though its name is dry and unremarkable, this field delivers extremely high practical value, and acts as the foundational support for tools powering product recommendation, fraud detection, smart energy, and medical analytics. Recently, Philippe Fournier-Viger’s team is set to systematically sort through and review decades of accumulated research in this field.
What Exactly Is a "Sequence," and Why Does Order Matter?
Imagine that there are 4 customers in a retail outlet. They spend money on each a number of visits – perhaps coffee and sugar on Monday, bread on Wednesday, cheese and crackers the next week. If the timing doesn't matter, you're left with a pile of groceries. However, if you pay attention to the sequence, you can begin asking some more sophisticated questions: Do customers who purchase coffee and sugar also tend to return for bread? Typically, which goes first when it comes to cheese and crackers: crackers or cheese?
This is the key idea of sequential pattern mining. Sequential pattern mining takes into consideration the time-line, unlike simple “things that are often bought together” analysis (the logic behind the classic “customers that bought this also bought that”). It sees data as a list of events (or more accurately, groups of events because a person could make 2 purchases in the same transaction). The idea is to discover subsequences that appear frequently in many customers, patients, or users more than just by chance.
This type of sequential thinking is useful in nearly all places where you have data that has a time series: word order in a sentence, mouse clicks on a website, gene activation in a sequence, etc. — even in the case of stock price fluctuations, you can apply the "up, down, up, down" pattern.
How Do You Actually Find These Patterns?
The problem is, it's not as easy as doing a single pass over a list to discover which subsequences are common. If one sequence is even a small list, the number of patterns that could be embedded in it grows very rapidly – doubling for each added item. There are more possible patterns in a sequence of 100 items than there are atoms in a grain of sand. A brute-force approach of checking all possible options would be too time consuming for anyone to wait.
So researchers have been working for more than 30 years up to now, on finding some smart hacks. The survey covers three major groups of techniques:
Building up a house layer by layer. The early algorithms, such as GSP, did this by computing all of the 1-item patterns, and then, every 2-item pattern, then every 3-item pattern, and so on, repeatedly scanning the whole database at every stage. It works, but extremely slowly and consumes a lot of memory — if you are adding another item to your grocery list, you have to create a new one again.
The strategy of indexing all in one go. SPADE algorithms turn on the side of the database. Rather than inquiring, "where is this customer buying from," they ask, "where is this particular item being bought? This allows the system to respond to pattern-frequency questions without having to scan the entire data set as many times as needed, similar to using a book's index to locate a topic rather than flipping through each page. Subsequent enhancements turned this indexing into binary coding (essentially strings of 1s and 0s), which made the entire process significantly faster – these were amongst the fastest of which, such as SPAM and CM-Spade, are now viewed as some of the quickest alternatives.
The "real leads only" strategy. The third family, represented by an algorithm called PrefixSpan, does something different: it repeatedly keeps stripping away data that isn't relevant, pruning the problem with every iteration, until it is small enough to determine if there are patterns that are real. This prevents the time spent on building patterns that may not be found in the data, but may require additional repetition of work, scanning ever smaller subsets of the data table.
It is interesting to note that there can only ever be one “right answer” for a given set of data and frequency threshold, and that every algorithm, no matter how they go about it will end up with the same final list of patterns. The differences only relate to speed and memory efficiency and not accuracy.
The Problem of "Too Much of a Good Thing"
Contrary to popular opinion, the difficulty with this trade is not that one can't find patterns, it is that one can find far too many. If you make your frequency too low, a dataset can output thousands, or even millions of patterns. No analyst has time to comb through that, and the algorithms themselves bog down to a crawl trying to create and store all of them.
The answer researchers came up with is simple and brilliant: rather than reporting each individual frequent pattern, report a smaller and more intelligent summary that has (or at least suggests) the same information. There are three variations of this insight that keep rearing their heads in the research:
If multiple patterns have the same frequency closed patterns hold just the "biggest" version of the pattern. Why list the shorter ones when the longer pattern is sufficient to tell you everything about them? This is called a lossless approach: any other pattern can be mathematically reconstructed from this reduced set.
Maximal patterns go further; they retain the largest patterns and ignore those that are just part of a larger pattern. This reduces the result list significantly, but gives some loss of detail – you would have to re-read the original data to get the exact number of times each frequency occurred.
When the smallest pattern has the same frequency as the longer pattern, generator patterns reverse the logic, and store the smallest pattern whenever it can. This proves to be particularly helpful for such tasks as creating prediction rules and boosting the accuracy of machine learning classification problems.
In one of the examples in the survey, a small customer sequence database (with only four customers) yielded a total of 29 frequent patterns, of which only 14 were "closed" and only 10 were "maximal. For a toy scale that's not a trivial savings and the savings only get bigger as the data grows larger.
Teaching the Algorithm What You Actually Care About
Another great idea is to let the user add his own requirements to the search instead of crunching through all this data and then filtering out the ones he doesn't want. Imagine you were to give a contractor the list of all the rooms that you don't need to work on, rather than the list of all the rooms and then taking some of them back out.
The "constraints" may be many: ignore patterns that take too long to play out; consider only patterns with certain products; limit how many items a pattern can contain; even specify the shape of a pattern, for instance with a fill-in-the-blank template (a regular expression). Properly integrated in the search algorithm, these rules allow the algorithm to remove vast amounts of irrelevant options that might otherwise be generated and then eliminated later in the algorithm frequently the key to getting a search to run in seconds rather than forever.
Beyond the Basics: Real-World Messiness
- In a plain sequential pattern mining, the world is assumed to be tidy, which means that the data is clean, yes/no to have or not have each item, and the analysis is one-and-done. Real life never works out as planned, so the field has developed a number of specialized subfields to deal with the messiness:
- Negative patterns seek out the lack of something that is valuable — in contrast to presence patterns, which seek out presence, they can be used to find customers who have a single purchase but don't make their next one, for example.
- All items are not equal important, thus weighted and high-utility mining. The pattern with the $2000 purchase is more interesting than the pattern with the pack of gum, although the latter may occur more frequently.
- Uncertain and fuzzy pattern mining work with data that are not perfect, such as values provided by noisy sensors, or objects that lie on a continuum (e.g. "somewhat sweet" versus "very sweet") between two discrete categories (in-or-out).
- Incremental and streaming algorithms are designed to deal with data that does not cease to arrive – such as live website traffic – and update existing patterns on the fly, rather than restarting the analysis from scratch each time new data is processed.
- The hard part of determining the correct cutoff frequency for the pattern is avoided in top-k mining, because it is user defined, rather than based on a statistical or abstract threshold.
- Patterns are linked to who is doing them, rather than what, through multi-dimensional mining layers in extra context such as age group or education level of a customer.
Practical Implications
These techniques aren't just academic artifacts; they're integral to systems we all deal with on a day-to-day basis. Retailers will time promotions and fill shelves based on the order that people usually purchase items, with the help of sequence-aware analysis. It is used by streaming sites and web pages to predict what the next click is likely to be. Bioinformatics scientists use it for recognizing patterns in the sequence of genes that are associated with disease. An ordered-event analysis is a method network security teams use to detect intrusion attempts that occur in a recognizable sequence of events. It is used in smart-home systems to learn the home's energy usage patterns and reduce energy consumption without compromising comfort. The survey also reveals that this research community has an open-source toolkit called SPMF that is freely available online with more than 100 of these algorithms already built, ready to be used by other researchers and developers without having to re-invent the wheel.
Conclusion
At its core, sequential pattern mining is a tale of respecting time. There is lots of data analysis that regards events as a random collection of facts, but there is so much in the sequence — what was first, what was next and to what degree does one thing follow from another — that makes human behavior, biology and digital activity so meaningful. This survey of the decades of research evidences a field that began with a simple, yet computationally “heavy” idea, and then slowly evolved to more clever, faster, and sophisticated means to make it useful for large-scale applications. As more and more of life gets documented as a "timelineclicks," purchases, sensor readings, genetic markers — the open questions the researchers cite next (messier data, smarter relevance measures, massive parallel systems) indicate that this is by no means over.