A framework for diagnosing changes in evolving data streams

ABSTRACT

In recent years, the progress in hardware technology has made it possible for organizations to store and record large streams of transactional data. This results in databases which grow without limit at a rapid rate. This data can often show important changes in trends over time. In such cases, it is useful to understand, visualize and diagnose the evolution of these trends. When the data streams are fast and continuous, it becomes important to analyze and predict the trends quickly in online fashion. In this paper, we discuss the concept of velocity density estimation, a technique used to understand, visualize and determine trends in the evolution of fast data streams. We show how to use velocity density estimation in order to create both temporal velocity profiles and spatial velocity profiles at periodic instants in time. These profiles are then used in order to predict three kinds of data evolution: dissolution, coagulation and shift. Methods are proposed to visualize the changing data trends in a single online scan of the data stream, and a computational requirement which is linear in the number of data points. In addition, batch processing techniques are proposed in order to identify combinations of dimensions which show the greatest amount of global evolution. The techniques discussed in this paper can be easily extended to spatio-temporal data, changes in data snapshots at fixed instances in time, or any other data which has a temporal component during its evolution.

REFERENCES

• 1: N. Andrienko, G. Andrienko, P. Gatalsky. Towards Exploratory Visualization of Spatio-Temporal Data. Third AGILE Conference on Geographical Information Science, pages 137--142, May 25--27, 2000.
• 2: Dan Bonachea , Kathleen Fisher , Anne Rogers , Frederick Smith, Hancock: a language for processing very large-scale data, Proceedings of the 2nd conference on Domain-specific languages, p.163-176, October 03-06, 1999, Austin, Texas, United States
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 5: David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996
• 6: Corinna Cortes , Kathleen Fisher , Daryl Pregibon , Anne Rogers, Hancock: a language for extracting signatures from data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.9-17, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347094]
• 7: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 8: Dynamic Histograms: Capturing Evolving Data Sets, Proceedings of the 16th International Conference on Data Engineering, p.86, February 28-March 03, 2000
• 9: R. Feldman, Y. Aumann, A. Amir, H. Mannila. Efficient Algorithms for Discovering Frequent Sets in Incremental Databases. DMKD Workshop Proceedings, 1997.
• 10: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507517]
• 11: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 12: Wilburt Labio , Hector Garcia-Molina, Efficient Snapshot Differential Algorithms for Data Warehousing, Proceedings of the 22th International Conference on Very Large Data Bases, p.63-74, September 03-06, 1996
• 13: B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.
• 14: John F. Roddick , Lina Al-Jadir , Leopoldo Bertossi , Marlon Dumas , Florida Estrella , Heidi Gregersen , Kathleen Hornsby , Jens Lufter , Federica Mandreoli , Tomi Männistö , Enric Mayol , Lex Wedemeijer, Evolution and change in data management — issues and directions, ACM SIGMOD Record, v.29 n.1, p.21-25, March 2000 [doi>10.1145/344788.344789]
• 15: John F. Roddick , Myra Spiliopoulou, A bibliography of temporal, spatial and spatio-temporal data mining research, ACM SIGKDD Explorations Newsletter, v.1 n.1, p.34-38, June 1999 [doi>10.1145/846170.846173]
• 16: Timos K. Sellis, Research Issues in Spatio-temporal Database Systems, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.5-11, July 20-23, 1999
• 17: S. Thomas, S. Bodagala, K. Alsabti, S. Ranka. An Efficient Algorithm for the Incremental Updating of Association Rules in Large Databases. ACM KDD Conference Proceedings, 1997.
• 18: Online Data Mining for Co-Evolving Time Sequences, Proceedings of the 16th International Conference on Data Engineering, p.13, February 28-March 03, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

General Terms:
Algorithms, Design