Loading...
Please wait, while we are loading the content...
Similar Documents
Succinct summarization of transactional databases: an overlapped hyperrectangle scheme.
| Content Provider | CiteSeerX |
|---|---|
| Author | Jin, Ruoming Xiang, Yang Fuhry, David Dragan, Feodor F. |
| Abstract | Transactional data are ubiquitous. Several methods, including frequent itemsets mining and co-clustering, have been proposed to analyze transactional databases. In this work, we propose a new research problem to succinctly summarize transactional databases. Solving this problem requires linking the high level structure of the database to a potentially huge number of frequent itemsets. We formulate this problem as a set covering problem using overlapped hyperrectangles; we then prove that this problem and its several variations are NP-hard. We develop an approximation algorithm HY PER which can achieve a ln(k) + 1 approximation ratio in polynomial time. We propose a pruning strategy that can significantly speed up the processing of our algorithm. Additionally, we propose an efficient algorithm to further summarize the set of hyperrectangles by allowing false positive conditions. A detailed study using both real and synthetic datasets shows the effectiveness and efficiency of our approaches in summarizing transactional databases. Categories andSubjectDescriptors |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Transactional Data Succinct Summarization Overlapped Hyperrectangle Scheme Several Variation New Research Problem Several Method Approximation Ratio False Positive Condition Pruning Strategy High Level Structure Huge Number Polynomial Time Transactional Database Approximation Algorithm Hy Per Efficient Algorithm Detailed Study Synthetic Datasets Category Andsubjectdescriptors Frequent Itemsets |
| Content Type | Text |
