Pruning attribute values from data cubes with diamond dicing

ABSTRACT

Data stored in a data warehouse are inherently multidimensional, unlike most data-pruning techniques (such as iceberg and top-k queries). However, analysts need to issue multidimensional queries. For example, an analyst may need to select not just the most profitable stores or---separately---the most profitable products, but simultaneous sets of stores and products fulfilling some profitability constraints. To fill this need, we propose a new operator, the diamond dice. Because of the interaction between dimensions, the computation of diamonds is challenging. We present the first diamond-dicing experiments on large data sets. Our external memory algorithm avoids potentially expensive random accesses. Experiments show that we can compute diamond cubes over fact tables containing 100 million facts and 500,000 distinct attribute values in less than an hour using a single-core PC.

REFERENCES

• 1: C. Anderson. The long tail. Hyperion, 2006.
• 2: K. Aouiche, D. Lemire, and R. Godin. Collaborative OLAP with tag clouds: Web 2.0 OLAP formalism and experimental evaluation. In WEBIST'08, 2008.
• 3: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 4: Riadh Ben Messaoud , Omar Boussaid , Sabine Loudcher Rabaséda, Efficient multidimensional data representations based on multiple correspondence analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150484]
• 5: J. Bennett and S. Lanning. The Netflix prize. In KDD Cup and Workshop 2007, 2007.
• 6: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 7: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 8: Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Diamond in the rough: finding Hierarchical Heavy Hitters in multi-dimensional data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007588]
• 9: Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005 [doi>10.1145/1061318.1061325]
• 10: Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, The cgmCUBE project: Optimizing parallel data cube generation for ROLAP, Distributed and Parallel Databases, v.19 n.1, p.29-62, January 2006 [doi>10.1007/s10619-006-6575-6]
• 11: J. O. Engene. Five decades of terrorism in Europe: The TWEED dataset. Journal of Peace Research, 44(1):109--121, 2007.
• 12: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 13: Venkatesh Ganti , Mong-Li Lee , Raghu Ramakrishnan, ICICLES: Self-Tuning Samples for Approximate Query Answering, Proceedings of the 26th International Conference on Very Large Data Bases, p.176-187, September 10-14, 2000
• 14: R. Godin, R. Missaoui, and H. Alaoui. Incremental concept formation algorithms based on Galois (concept) lattices. Computational Intelligence, 11:246--267, 1995.
• 15: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 16: S. Hettich and S. D. Bay. The UCI KDD archive. http://kdd.ics.uci.edu (checked 2008-04-28), 2000.
• 17: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceedings of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 18: Daniel Lemire , Owen Kaser, Hierarchical bin buffering: Online local moments for dynamic external memory arrays, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-31, March 2008 [doi>10.1145/1328911.1328925]
• 19: Cuiping Li , Beng Chin Ooi , Anthony K. H. Tung , Shan Wang, DADA: a data cube for dominant relationship analysis, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142547]
• 20: Zheng Xuan Loh , Tok Wang Ling , Chuan-Heng Ang , Sin Yeung Lee, Adaptive Method for Range Top- k Queries in OLAP Data Cubes, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.648-657, September 02-06, 2002
• 21: Zheng Xuan Loh , Tok Wang Ling , Chuan Heng Ang , Sin Yeung Lee, Analysis of pre-computed partition top method for range top-k queries in OLAP data cubes, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584806]
• 22: Michael Morse , Jignesh M. Patel , H. V. Jagadish, Efficient skyline computation over low-cardinality domains, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: Thomas P. Nadeau , Toby J. Teorey, A Pareto Model for OLAP View Size Estimation, Information Systems Frontiers, v.5 n.2, p.137-147, April 2003 [doi>10.1023/A:1022693305401]
• 24: Netflix, Inc. Nexflix prize. http://www.netflixprize.com (checked 2008-04-28), 2007.
• 25: J. Pei, M. Cho, and D. Cheung. Cross table cubing: Mining iceberg cubes from data warehouses. In SDM'05, 2005.
• 26: D. N. Politis, J. P. Romano, and M. Wolf. Subsampling. Springer, 1999.
• 27: P. Krishna Reddy , Masaru Kitsuregawa, An Approach to Relate the Web Communities through Bipartite Graphs, Proceedings of the Second International Conference on Web Information Systems Engineering (WISE'01) Volume 1, p.301, December 03-06, 2001
• 28: H. Webb. Properties and applications of diamond cubes. In ICSOFT 2007 -- Doctoral Consortium, 2007.
• 29: H. Webb, O. Kaser, and D. Lemire. Pruning attribute values from data cubes with diamond dicing. Technical Report TR-08-011, Computer Science and Applied Statistics, University of New Brunswick Saint John, 2008. available from http://http://arxiv.org/abs/0805.0747.
• 30: Dong Xin , Jiawei Han , Xiaolei Li , Benjamin W. Wah, Star-cubing: computing iceberg cubes by top-down and bottom-up integration, Proceedings of the 29th international conference on Very large data bases, p.476-487, September 09-12, 2003, Berlin, Germany
• 31: K. Yang. Information retrieval on the web. Annual Review of Information Science and Technology, 39:33--81, 2005.
• 32: Man Lung Yiu , Nikos Mamoulis, Efficient processing of top-k dominating queries on multi-dimensional data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

General Terms:
Design, Languages

Keywords:
OLAP, algorithms, data warehouses, diamond cube, information retrieval, multidimensional queries