Sequential pattern mining studies how to discover frequent ordered behaviors from a sequence database, and it remains one of the most useful tasks in data mining because the patterns it reveals are both interpretable and practical. A sequence may represent customer purchases, browser clicks, biological events, or machine operations, and the aim is to find every subsequence that appears often enough to be considered significant. The difficulty is not in defining the task, but in doing it efficiently when the number of possible patterns is extremely large. As the minimum support threshold becomes smaller, the search space grows rapidly, and many classic algorithms become slow, memory-intensive, or impractical for interactive analysis.
The main weakness of earlier approaches is that they each pay a different kind of cost. Candidate-generation methods like GSP repeatedly produce and test large sets of possible patterns, which makes them expensive when the database is large. Projection-based methods such as PrefixSpan avoid explicit candidate generation, but they rely on projected databases that can become large and repetitive. Vertical methods like SPAM and CM-SPADE are often faster, yet they still require careful support counting over many pattern extensions and do not naturally support a “mine once, adjust later” workflow. These limitations are especially important in real use, where analysts rarely know the best support threshold in advance and often need to explore several values before deciding what is meaningful.
The motivation behind Tree-Miner is to remove the gap between compact representation and efficient sequential mining. In many data mining tasks, the database itself is not the main challenge; instead, the challenge is the number of times that the data must be revisited in different forms. If a method has to rebuild projections, re-scan the database, or recompute support from scratch every time the threshold changes, then its practical value becomes limited. Tree-Miner was designed to solve exactly this kind of repeated-cost problem.
Another important motivation is that sequential pattern mining is often exploratory. Analysts may not know whether they need a very low support threshold, a medium one, or a more restrictive one until they inspect the discovered patterns. A useful method should therefore support fast re-mining with the same structure. SP-Tree makes that possible because it stores the useful information once and keeps it accessible for many mining runs. This idea is important not only for speed, but also for usability.
SP-Tree Representation
Tree-Miner addresses these problems through SP-Tree, a compact tree representation of the complete sequence database. The central idea is simple but powerful: instead of storing the same prefixes again and again across many sequences, the database is organized so that shared prefixes are merged into single paths. This reduces storage and makes the data easier to traverse. At the same time, the tree keeps the information needed for sequential mining, including the order of items, their event positions, and the support counts of shared paths. The result is a representation that is not just smaller, but also directly useful for mining patterns.
SP-Tree is built in a way that preserves the order structure of the database while removing redundancy. Each node contains the item label, the event number, the count of sequences that share that prefix, next links to later occurrences in the subtree, and a parent mask that records which items appear in the same event. These fields are not decorative; each one supports a specific part of the mining process. The label identifies the item, the event number distinguishes whether an extension is sequential or within the same itemset, the count provides support information, the next links speed up traversal, and the parent mask helps validate itemset extensions quickly. In this sense, SP-Tree is a working structure for mining rather than just a compressed storage format.
The construction process of SP-Tree has three major advantages. First, common prefixes are merged, so sequences that begin in the same way are represented only once. This is especially effective for dense datasets, where many sequences share long common beginnings. Second, the tree keeps event positions explicitly, so the algorithm can distinguish between adding an item to the next event and adding an item to the current event. This distinction is critical in sequential pattern mining because order matters. Third, the next links and co-existing item information are computed in advance, so later mining steps do not need to search blindly. Instead of repeatedly scanning the raw database, Tree-Miner can move directly to the parts of the tree that are relevant to the current pattern.
Tree-Miner Algorithm
Tree-Miner mines SP-Tree using a node-list based strategy. A node list is the set of nodes where a pattern ends in the tree, and it is enough to compute the support of that pattern exactly. This is one of the most important ideas in the method because it removes the need to revisit the entire database for every extension. If the node list is known, then the support of a pattern is simply the sum of the counts of the nodes in that list. That makes support counting both exact and efficient. The algorithm then grows patterns in two ways: sequential extension adds a new event after the current one, and itemset extension adds a new item to the same event. These two operations cover the full structure of sequential pattern growth.
Efficiency comes from the pruning rules that guide this search. Tree-Miner uses a co-existing item table to remove items that do not occur often enough with the current pattern. It also uses list inheritance so that child patterns only consider extension items that are still valid after the parent has been expanded. A third pruning rule prevents unnecessary itemset exploration when a sequential extension already fails and the parent branch does not have enough support to justify more search. These rules are important because they reduce the number of branches that the algorithm must explore, but they do so without removing any frequent patterns. In other words, the pruning is safe, not approximate.
The algorithm also benefits from the way it separates extension types. Sequential extension grows patterns across events, while itemset extension grows patterns inside the same event. Because the tree records event numbers and same-event masks, both operations can be handled without ambiguity. This reduces the chance of repeated checks and simplifies the logic of the search. The result is a pattern-growth process that is both structured and efficient, which is a major reason why Tree-Miner can outperform earlier methods.
Experimental Results
The experimental results support this design clearly. On real datasets with different characteristics, Tree-Miner performs better than PrefixSpan, CM-SPAM, and CM-SPADE, especially when the minimum support is low. Low support is the hardest setting because it usually produces many frequent patterns, which means more search work and more opportunities for slowdowns. Tree-Miner remains fast in that setting because the tree structure reduces redundant work and the pruning rules stop many unproductive branches early. This makes the method useful not only for small demonstrations, but also for realistic data mining tasks where the support threshold is not fixed in advance.
Another important result is that the time needed to build SP-Tree is very small compared with the time needed to mine it. That matters because a structure that is expensive to build would lose much of its practical value. Tree-Miner avoids this problem by making construction a lightweight preprocessing step. Once the tree is built, it can be mined repeatedly with different thresholds. This is a strong advantage in exploratory analysis, where a user may want to compare several support settings before deciding what patterns are most useful.
The experiments also show that Tree-Miner works well on both sparse and dense data. Dense datasets benefit from prefix sharing because many sequences share long common starts. Sparse datasets benefit from the next links because they allow the algorithm to jump quickly to useful positions instead of scanning large branches. This means the method is not tuned only for one data type. It is designed in a general way that makes it practical across different data distributions, which is an important quality for real-world mining systems.
Tree-Miner also has a strong conceptual value because it changes how sequential pattern mining can be organized. Instead of treating the database as a static input that must be scanned repeatedly, the method turns the tree into the central object of computation. This makes the mining process more structured, more reusable, and easier to extend. The same framework can support future work on closed sequential patterns, top-k mining, high-utility pattern mining, and stream-based variants. These extensions are natural because the tree already stores the order information and support information needed to guide further analysis.
The method is especially well suited to applications where ordered behavior matters and the analyst needs efficient repeated mining. In recommendation systems, it can help find common purchase or click sequences. In bioinformatics, it can support the search for recurring event patterns in biological data. In web analytics, it can identify common user paths through a site. In machine monitoring, it can reveal repeated operational sequences before faults occur. Because it is both compact and exact, Tree-Miner is not just a theoretical improvement, but a practical one as well.
A further advantage is that the same SP-Tree structure can be reused in iterative experiments. Many mining workflows are not one-shot tasks; they involve trial, comparison, adjustment, and refinement. When the database representation supports that style of work, the entire analysis becomes smoother. That is why Tree-Miner has value beyond the specific benchmark results. It provides a usable framework for real analytical work, not just a specialized algorithm for a narrow test case.
Conclusion
Tree-Miner and SP-Tree provide a strong solution to the sequential pattern mining problem by combining a compact database representation with an efficient pattern-growth strategy. The tree reduces redundancy, the node-list method makes support counting exact, and the pruning rules keep the search focused. Unlike many earlier methods, Tree-Miner is designed for repeated mining and interactive use, which makes it more suitable for real analytical workflows. Its value lies not only in speed, but also in the clarity and reusability of its design. For these reasons, Tree-Miner is a solid foundation for future sequential mining systems and a useful method for practical data analysis.
The broader lesson from this work is that a better representation can improve both performance and usability. When the database is organized into a structure that preserves the necessary information while removing redundancy, the mining algorithm becomes simpler and faster. That is the main contribution of Tree-Miner: it shows that sequential mining can be both compact and exact at the same time. This balance is what makes the method strong for research and practical deployment alike.