2008 SuccinctSummarizationofTransact

• (Xiang et al., 2008) ⇒ Yang Xiang, Ruoming Jin, David Fuhry, and Feodor F. Dragan. (2008). “Succinct Summarization of Transactional Databases: An Overlapped Hyperrectangle Scheme.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401981

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Succinct+summarization+of+transactional+databases%3A+an+overlapped+hyperrectangle+scheme%22+2008
• http://portal.acm.org/citation.cfm?doid=1401890.1401981&preflayout=flat#citedby

Quotes

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 HYPER 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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 SuccinctSummarizationofTransact	Ruoming Jin Yang Xiang David Fuhry Feodor F. Dragan			Succinct Summarization of Transactional Databases: An Overlapped Hyperrectangle Scheme		KDD-2008 Proceedings		10.1145/1401890.1401981		2008