Computing the frequency of a pattern is one of the key operations in
data mining algorithms. We describe a simple yet powerful way of
speeding up any form of frequency counting satisfying the
monotonicity condition. Our method, the optimized segment support
map (OSSM), is a light-weight structure which partitions the
collection of transactions into m segments, so as to reduce the
number of candidate patterns that require frequency counting. We
study the following problems: (1) What is the optimal number of
segments to be used; and (2) Given a user-determined m, what is the
best segmentation/composition of the m segments? For Problem 1, we
provide a thorough analysis and a theorem establishing the minimum
value of m for which there is no accuracy lost in using the OSSM.
For Problem 2, we develop various algorrithms and heuristics, which
efficiently generate OSSMs that are compact and effective, to help
facilitate segmentation.