FSSM: Fast construction of the optimized segment support map

Computing the frequency of a pattern is one of the key operations in data mining algorithms. Recently, the Optimized Segment Support Map (OSSM) was introduced as a simple but powerful way of speeding up any form of frequency counting satisfying the monotonicity condition. However, the construction cost to obtain the ideal OSSM is high, and makes it less attractive in practice. In this paper, we propose the FSSM, a novel algorithm that constructs the OSSM quickly using a FP-Tree. Given a user-defined segment size, the FSSM is able to construct the OSSM at a fraction of the time required by the algorithm previously proposed. More importantly, this fast construction time is achieved without compromising the quality of the OSSM. Our experimental results confirm that the FSSM is a promising solution for constructing the best OSSM within user given constraints. © Springer-Verlag Berlin Heidelberg 2003.