Efficient and effective explanation of change in hierarchical summaries

ABSTRACT

Dimension attributes in data warehouses are typically hierarchical (e.g., geographic locations in sales data, URLs in Web traffic logs). OLAP tools are used to summarize the measure attributes (e.g., total sales) along a dimension hierarchy, and to characterize changes (e.g., trends and anomalies) in a hierarchical summary over time. When thenumber of changes identified is large (e.g., total sales in many stores differed from their expected values), a parsimonious explanation of the most significant changes is desirable. In this paper, we propose a natural model of parsimonious explanation, as a composition of node weights along the root-to-leaf paths in a dimension hierarchy, which permits changes to be aggregated with maximal generalization along the dimension hierarchy. We formalize this model of explaining changes in hierarchical summaries and investigate the problem of identifying optimally parsimonious explanations on arbitrary rooted one dimensional tree hierarchies. We show that such explanations can be computed efficiently in time essentially proportional to the number of leaves and the depth of the hierarchy. Further, our method can produce parsimonious explanations from the output of any statistical model that provides predictions and confidence intervals, making it widely applicable. Our experiments use real data sets to demonstrate the utility and robustness of our proposed model for explaining significant changes, as well as its superior parsimony compared to alternatives.

REFERENCES

• 1: Charu C. Aggarwal, On Change Diagnosis in Evolving Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.587-600, May 2005 [doi>10.1109/TKDE.2005.78]
• 2: Edoardo Amaldi , Viggo Kann, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, v.209 n.1-2, p.237-260, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00115-1]
• 3: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 4: Dhiman Barman, Flip Korn, Divesh Srivastava, Dimitris Gunopulos, Neal E. Young, and Deepak Agarwal. Parsimonious Explanations of Change in Hierarchical Data. In Proc. of ICDE 2007.
• 5: Census (population vs. location), 2000-2004. http://www.census.gov/popest/datasets.htm.
• 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: Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Finding hierarchical heavy hitters in data streams, Proceedings of the 29th international conference on Very large data bases, p.464-475, September 09-12, 2003, Berlin, Germany
• 8: Graham Cormode and S. Muthukrishnan. What's new: Finding significant differences in network data streams. In Proc. of IEEE INFOCOM, pages 1534--1545, 2004.
• 9: Cristian Estan , Stefan Savage , George Varghese, Automatically inferring patterns of resource consumption in network traffic, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863972]
• 10: 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
• 11: Sudipto Guha, Space efficiency in synopsis construction algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Sudipto Guha , Boulos Harb, Approximation algorithms for wavelet transform coding of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.698-707, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109633]
• 13: Panagiotis Karras and Nikos Mamoulis. The Haar+ Tree: a Refined Synopsis Data Structure. In Proc. of the IEEE 23rd ICDE, April 2007.
• 14: Daniel Kifer , Shai Ben-David , Johannes Gehrke, Detecting change in data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.180-191, August 31-September 03, 2004, Toronto, Canada
• 15: Jon Kleinberg, Bursty and hierarchical structure in streams, 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.775061]
• 16: Laks V. S. Lakshmanan , Raymond T. Ng , Christine Xing Wang , Xiaodong Zhou , Theodore J. Johnson, The generalized MDL approach for summarization, Proceedings of the 28th international conference on Very Large Data Bases, p.766-777, August 20-23, 2002, Hong Kong, China
• 17: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 18: S. Muthukrishnan. Subquadratic algorithms for workload-aware Haar wavelet synopses. In Proc. of FSTTCS, 2005.
• 19: P. J. Harrison. Exponential smoothing and short-term sales forecasting. Management Science, 13(11):821--842, 1967.
• 20: Frederick Reiss , Minos Garofalakis , Joseph M. Hellerstein, Compact histograms for hierarchical identifiers, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 21: Sunita Sarawagi, Explaining Differences in Multidimensional Aggregates, Proceedings of the 25th International Conference on Very Large Data Bases, p.42-53, September 07-10, 1999
• 22: Sunita Sarawagi , Rakesh Agrawal , Nimrod Megiddo, Discovery-Driven Exploration of OLAP Data Cubes, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.168-182, March 23-27, 1998
• 23: Sudarshan S. Chawathe, Differencing Data Streams, Proceedings of the 9th International Database Engineering & Application Symposium, p.273-284, July 25-27, 2005 [doi>10.1109/IDEAS.2005.21]
• 24: S. Hill, D. Agarwal, R. Bell, and C. Volinsky. Building an effective representation for dynamic graphs. Journal of Computational and Graphical Statistics, 15:584--608, 2006.
• 25: WorldCup 1998. http://ita.ee.lbl.gov/html/contrib/WorldCup.html.
• 26: Yin Zhang , Sumeet Singh , Subhabrata Sen , Nick Duffield , Carsten Lund, Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028802]
• 27: Yunyue Zhu , Dennis Shasha, Efficient elastic burst detection in data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956789]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
OLAP, change, hierarchical summary, parsimonious explanations, statistical model