Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-11-27
2009-10-27
Lee, Wilson (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
07610284
ABSTRACT:
The present invention provides an effective data structure in finding frequent itemsets over data streams and finds necessary information using the data structure. The data structure proposed in the present invention is defined as a compressed prefix tree structure, and the compressed prefix tree merges or splits nodes during the mining operation by comparing the prefix tree structure applied to the conventional data mining to manage a plurality of items in a single node, thus dynamically and flexibly adjusting the tree size. Such dynamic adjustment function dynamically merges and splits nodes in the prefix tree, if the variation of itemsets that are most likely to be frequent itemsets due to the variation of the data stream, thus maximizing the accuracy of the mining result in a restricted memory space, i.e., the accuracy of frequent itemsets found.
REFERENCES:
patent: 6138117 (2000-10-01), Bayardo
patent: 6415287 (2002-07-01), Wang et al.
patent: 6473757 (2002-10-01), Garofalakis et al.
patent: 2003/0217055 (2003-11-01), Lee et al.
patent: 2004/0181519 (2004-09-01), Anwar
patent: 2006/0174024 (2006-08-01), Chi et al.
Charikar, et al., “Finding Frequent Items in Data Streams”, Proc. 29thInt'l Colloq. Automata, Language and Programming, pp. 1-11, (2002).
Brin, et al., “Dynamic Itemset Counting and Implication Rules for Market Basket Data”, Proc. ACM SIGMOD Int'l Conf. Management of Data (SIGMOD 97), pp. 255-264, (1997).
Chang, et al., “Finding Recent Frequent Itemsets Adaptively over Online Data Streams”, In Proc. Of the 9thACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining, Washington, DC, (CIKM 01), pp. 487-492, (2001).
Hafez, et al., “The Item-Set Tree: A Data Structure for Data Mining”, In Proc. Of 1stInt'l Conf on datawarehousing and knowledge discovery, pp. 183-192, (Aug. 1999).
Zaki, et al., “Generating Non-Redundant Association Rules”, Proc. 6thACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining (KDD 00), pp. 1-18, (2000).
Industry-Academic Cooperation Foundation - Yonsei University
Lee Wilson
LandOfFree
Compressed prefix trees and estDec+ method for finding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compressed prefix trees and estDec+ method for finding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed prefix trees and estDec+ method for finding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4072621