AlphaSum: size-constrained table summarization using value lattices

ABSTRACT

Consider a scientist who wants to explore multiple data sets to select the relevant ones for further analysis. Since the visualization real estate may put a stringent constraint on how much detail can be presented to this user in a single page, effective table summarization techniques are needed to create summaries that are both sufficiently small and effective in communicating the available content. In this paper, we first argue that table summarization can benefit from knowledge about acceptable value clustering alternatives for clustering the values in the database. We formulate the problem of table summarization with the help of value lattices. We then provide a framework to express alternative clustering strategies and to account for various utility measures (such as information loss) in assessing different summarization alternatives. Based on this interpretation, we introduce three preference criteria, max-min-util (cautious), max-sum-util (cumulative), and pareto-util, for the problem of table summarization. To tackle with the inherent complexity, we rely on the properties of the fuzzy interpretation to further develop a novel ranked set cover based evaluation mechanism (RSC). These are brought together in an AlphaSum, table summarization system. Experimental evaluations showed that RSC improves both execution times and the summary qualities in AlphaSum, by pruning the search space more effectively than the existing solutions.

REFERENCES

• 1: G. Aggarwal, K. K. Tomas Feder, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. Approximation algorithms for k-anonymity. Journal of Privacy Technology, 2005.
• 2: R. Alfred and D. Kazakov. Data summarization approach to relational domain learning based on frequent pattern to support the development of decision making. ADMA, 2006.
• 3: Francesco Buccafurri , Filippo Furfaro , Domenico Sacca , Cristina Sirangelo, A quad-tree based multiresolution approach for two-dimensional summary data, Proceedings of the 15th International Conference on Scientific and Statistical Database Management, p.127-140, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214974]
• 4: Adam L. Buchsbaum , Donald F. Caldwell , Kenneth W. Church , Glenn S. Fowler , S. Muthukrishnan, Engineering the compression of massive tables: an experimental approach, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.175-184, January 09-11, 2000, San Francisco, California, United States
• 5: Adam L. Buchsbaum , Glenn S. Fowler , Raffaele Giancarlo, Improving table compression with combinatorial optimization, Journal of the ACM (JACM), v.50 n.6, p.825-851, November 2003 [doi>10.1145/950620.950622]
• 6: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Alfredo Cuzzocrea , Filippo Furfaro , Domenico Saccà, Hand-OLAP: A System for Delivering OLAP Services on Handheld Devices, Proceedings of the The Sixth International Symposium on Autonomous Decentralized Systems (ISADS'03), p.80, April 09-11, 2003
• 9: A. Cuzzocrea, D. Saccà, and P. Serafino. A hierarchy-driven compression technique for advanced olap visualization of multidimensional data cubes. In DaWaK, pages 106--119, 2006.
• 10: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 11: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 12: Benjamin C. M. Fung , Ke Wang , Philip S. Yu, Top-Down Specialization for Information and Privacy Preservation, Proceedings of the 21st International Conference on Data Engineering, p.205-216, April 05-08, 2005 [doi>10.1109/ICDE.2005.143]
• 13: Carlos A. Hurtado , Claudio Gutierrez , Alberto O. Mendelzon, Capturing summarizability with integrity constraints in OLAP, ACM Transactions on Database Systems (TODS), v.30 n.3, p.854-886, September 2005 [doi>10.1145/1093382.1093388]
• 14: Carlos A. Hurtado , Alberto O. Mendelzon, Reasoning about Summarizability in Heterogeneous Multidimensional Schemas, Proceedings of the 8th International Conference on Database Theory, p.375-389, January 04-06, 2001
• 15: Vijay S. Iyengar, Transforming data to satisfy privacy constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775089]
• 16: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 17: Ming-Ling Lo , Kun-Lung Wu , Philip S. Yu, TabSum: A Flexible and Dynamic Table Summarization Approach, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.628, April 10-13, 2000
• 18: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 19: M. Ercan Nergiz , Chris Clifton, Thoughts on k-anonymization, Data & Knowledge Engineering, v.63 n.3, p.622-645, December, 2007 [doi>10.1016/j.datak.2007.03.009]
• 20: Wee Keong Ng , Chinya V. Ravishankar, Relational Database Compression Using Augmented Vector Quantization, Proceedings of the Eleventh International Conference on Data Engineering, p.540-549, March 06-10, 1995
• 21: Hyoungmin Park , Kyuseok Shim, Approximate algorithms for K-anonymity, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247490]
• 22: Torben Bach Pedersen , Christian S. Jensen , Curtis E. Dyreson, Supporting Imprecision in Multidimensional Databases Using Granularities, Proceedings of the 11th International Conference on Scientific and Statistical Database Management, p.90, July 28-30, 1999 [doi>10.1109/SSDM.1999.787624]
• 23: R. Rada, H. Mili, E. Bicknell, and M. Blettner. Development and application of a metric on semantic nets. IEEE Transactions on Systems, Man and Cybernetics, 19(1), 1989.
• 24: P. Resnik. Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language. JAIR, Vol. 11, 1999.
• 25: R. Richardson and A. F. Smeaton. Using WordNet in an Knowledge-Based Approach to Information Retrieval. Working paper CA-1294, Dublin City Univ., Dublin, 1994.
• 26: Yan Qi , K. Selçuk Candan , Maria Luisa Sapino, FICSR: feedback-based inconsistency resolution and query processing on misaligned data sources, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247499]
• 27: Yan Qi , K. Selçuk Candan , Maria Luisa Sapino , Keith W. Kintigh, Integrating and querying taxonomies with quest in the presence of conflicts, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247639]
• 28: Yan Qi , K. Selçuk Candan , Junichi Tatemura , Songting Chen , Fenglin Liao, Supporting OLAP operations over imperfectly integrated taxonomies, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376703]
• 29: Régis Saint-Paul , Guillaume Raschia , Noureddine Mouaddib, General purpose database summarization, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 30: R. Saint-Paul, G. Raschia, and N. Mouaddib. Database summarization: The saintetiq system. ICDE 2007.
• 31: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193]
• 32: Kun-Lung Wu , Shyh-Kwei Chen , Philip S. Yu, Dynamic Refinement of Table Summarization or M-Commerce, Proceedings of the Fourth IEEE International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems (WECWIS'02), p.179, June 26-28, 2002
• 33: Maurizio Rafanelli , Arie Shoshani, STORM: A Statistical Object Representation Model, Proceedings of the 5th International Conference SSDBM on Statistical and Scientific Database Management, p.14-29, April 03-05, 1990