Very fast frequent itemset mining: Simplicial complex methods (Extended abstract)
Tsau-Young Lin · 2016
Based on the concept of isomorphism of relations, a relation is turned into a simplicial complex, which is a combinatorial representation of a polyhedron. So frequent itemsets mining is transform turned into geometric traversal problem. By leveraging on geometric structure of simplicial complex, a very fast algorithm for traversal is found; it is based on a geometric concept, called sub-cone construction. It is not only very fast but also use much less memory than existing methods. For a real world medical database of 1257 columns with 65K rows, the new algorithm takes only 5 seconds to find all frequent itemsets, while FP-growth takes approximately 1000 seconds; so simplicial complex method is about 200 times faster. Moreover the memory usage is substantially less; see the data.