caa a22 4500 445871318 CHVBK 20180317145512.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s10618-010-0203-9 doi (NATIONALLICENCE)springer-10.1007/s10618-010-0203-9 Summarizing transactional databases with overlapped hyperrectangles [Elektronische Daten] [Yang Xiang, Ruoming Jin, David Fuhry, Feodor Dragan] Transactional data are ubiquitous. Several methods, including frequent itemset 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 (a concept generally regarded as tile according to some existing papers); we then prove that this problem and its several variations are NP-hard, and we further reveal its relationship with the compact representation of a directed bipartite graph. We develop an approximation algorithm Hyper which can achieve a logarithmic approximation ratio in polynomial time. We propose a pruning strategy that can significantly speed up the processing of our algorithm, and we also propose an efficient algorithm Hyper+ to further summarize the set of hyperrectangles by allowing false positive conditions. Additionally, we show that hyperrectangles generated by our algorithms can be properly visualized. A detailed study using both real and synthetic datasets shows the effectiveness and efficiency of our approaches in summarizing transactional databases. The Author(s), 2010 Hyperrectangle nationallicence Tile nationallicence Set cover nationallicence Summarization nationallicence Transactional database nationallicence Frequent itemset mining nationallicence Xiang Yang Department of Biomedical Informatics, The Ohio State University, 43210, Columbus, OH, USA aut Jin Ruoming Department of Computer Science, Kent State University, 44242, Kent, OH, USA aut Fuhry David Department of Computer Science and Engineering, The Ohio State University, 43210, Columbus, OH, USA aut Dragan Feodor Department of Computer Science, Kent State University, 44242, Kent, OH, USA aut Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 23/2(2011-09-01), 215-251 1384-5810 23:2<215 2011 23 10618 https://doi.org/10.1007/s10618-010-0203-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10618-010-0203-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Xiang Yang Department of Biomedical Informatics, The Ohio State University, 43210, Columbus, OH, USA aut NATIONALLICENCE 700 1- Jin Ruoming Department of Computer Science, Kent State University, 44242, Kent, OH, USA aut NATIONALLICENCE 700 1- Fuhry David Department of Computer Science and Engineering, The Ohio State University, 43210, Columbus, OH, USA aut NATIONALLICENCE 700 1- Dragan Feodor Department of Computer Science, Kent State University, 44242, Kent, OH, USA aut NATIONALLICENCE 773 0- Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 23/2(2011-09-01), 215-251 1384-5810 23:2<215 2011 23 10618 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer