A High Spatial Efficiency Algorithm for Frequent Closed Items Mining with Compressed Adjacency Byte Table
Frequent closed items(FCI)is an effective data structure for expressing the relationships among things,which can overcome the defect of frequent items(FI)in information redundancy.The purpose of study in fre-quent closed items mining is to find all frequent closed items in the original dataset with higher spatiotemporal effi-ciency.Unfortunately,lots of studies focused on the time efficiency improving but lost sight of spatial optimization.We proposed a data structure(Cab-table:Compressed Adjacency Byte table)for data compression efficiently,which can compress item set and transaction set into byte table without zero.Furthermore,we proposed a FCI mining algorithm with Cab-table,called Cab-Miner.In the algorithm we designed one retrieve stack and one operation stack to realize the non-recursive FCI mining,which is different from most of other algorithms.Compared to the recursive algorithm,our algorithm's space efficiency is O(2N+M)instead of O(LN+M).Several experiments were carried out with public data and real data,then we proved that our algorithm has better space occupation performance in initial data set com-pression and operation memory consumption,especially when the data set is collected from real scenes.Additionally,Cab-Miner also consumes lower time process in some data set with special properties.
NETL
NSTL
万方数据
维普
