Dynamic query tools for time series data sets: timebox widgets for interactive exploration

ABSTRACT

Timeboxes are rectangular widgets that can be used in direct-manipulation graphical user interfaces (GUIs) to specify query constraints on time series data sets. Timeboxes are used to specify simultaneously two sets of constraints: given a set of N time series profiles, a timebox covering time periods x1...x2 (x1<x2) and values y1...y2(y1≤y2) will retrieve only those n ∈N that have values y1≤y≤y2 during all times x1≤x≤x2. TimeSearcher is an information visualization tool that combines timebox queries with overview displays, query-by-example facilities, and support for queries over multiple time-varying attributes. Query manipulation tools including pattern inversion and 'leaders & laggards' graphical bookmarks provide additional support for interactive exploration of data sets. Extensions to the basic timebox model that provide additional expressivity include variable time timeboxes, which can be used to express queries with variability in the time interval, and angular queries, which search for ranges of differentials, rather than absolute values. Analysis of the algorithmic requirements for providing dynamic query performance for timebox queries showed that a sequential search outperformed searches based on geometric indices. Design studies helped identify the strengths and weaknesses of the query tools. Extended case studies involving the analysis of two different types of data from molecular biology experiments provided valuable feedback and validated the utility of both the timebox model and the TimeSearcher tool. Timesearcher is available at http://www.cs.umd.edu/hcil/timesearcher

REFERENCES

• 1: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 2: Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: Harry Hochheiser , Ben Shneiderman, Interactive Exploration of Time Series Data, Proceedings of the 4th International Conference on Discovery Science, p.441-446, November 25-28, 2001
• 6: 6 Bederson B Grosjean J Meyer J. Toolkit design for interactive structured graphic. Technical Report HCIL-2003-01,CS-TR-4432, and UMIACSTR-2003-03, University of Maryland, Human-Computer Interaction Lab, Department of Computer Science, and Institute for Advanced Computer Studies, 2003.
• 7: Chris North , Ben Shneiderman, Snap-together visualization: a user interface for coordinating visualizations via relational schemata, Proceedings of the working conference on Advanced visual interfaces, p.128-135, May 2000, Palermo, Italy [doi>10.1145/345513.345282]
• 8: Eamonn J. Keogh , Harry Hochheiser , Ben Shneiderman, An Augmented Visual Query Mechanism for Finding Patterns in Time Series Data, Proceedings of the 5th International Conference on Flexible Query Answering Systems, p.240-250, October 27-29, 2002
• 9: Helwig Hauser , Florian Ledermann , Helmut Doleisch, Angular Brushing of Extended Parallel Coordinates, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.127, October 28-29, 2002
• 10: 10 Winkler S. {WWW document} http://stats.math.uni-augsburg.de/CASSATT/index.html (accessed 14 May 2003).
• 11: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 12: Harry Hochheiser , Ben Shneiderman, Interactive graphical querying of time series and linear sequence data sets, 2003
• 13: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 14: 14 Shaft U, Goldstein J and Beyer K. Nearest neighbors query performance for unstable distributions. Technical Report TR1388, Computer Sciences Department, University of Wisconsin, October 1998.
• 15: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 16: 16 Hamadeh H and Afshari C. Gene chips and functional genomics. American Scientist, 2000; 8:508-515.
• 17: 17 DeRisi J, Iyer V and Brown P. Exploring the metabolic and genetic control of gene expression on a genomic scale. Science, 1997; 278: 680-686.
• 18: 18 Eisen M, Spellman P, Brown P, Botstein D. Cluster analysis and display of genome-wide expression patterns. Proceedings National Academies of Science USA, 1998; 95: 14863-14686.
• 19: Jinwook Seo , Ben Shneiderman, Interactively Exploring Hierarchical Clustering Results, Computer, v.35 n.7, p.80-86, July 2002 [doi>10.1109/MC.2002.1016905]
• 20: 20 Baehrecke E. How death shapes life during development. Nature Reviews Molecular Cell Biology, 2002; 3: 779-787.
• 21: 21 Lee C-Y Wendel D Reid P Lam P Thummel C and Baehrecke E. E93 directs steroid-triggered programmed cell death in Drosophila. Molecular Cell, 2000; 6: 433-443.
• 22: 22 Lee C-Y Clough E Yellon P Teslovich T Stephan D and Baehrecke E. Genome-wide analyses of steroid-and radiation-triggered programmed cell death in Drosophila. Current Biology, 2003; 13: 350-357.
• 23: 23 Baehrecke E. Steroid regulation of programmed cell death during Drosophila development. Cell Death and Differentiation, 2000; 7: 1057-1062.
• 24: 24 Clough E, Lee C-Y, Hochheiser H, Shneiderman B and Baehrecke E. Temporal analyses of gename-wide transcription during steroid-triggered programmed cell death in Drosophila. 2003, In preparation.
• 25: Chris North , Ben Shneiderman, Snap-together visualization: can users construct and operate coordinated visualizations?, International Journal of Human-Computer Studies, v.53 n.5, p.715-739, Nov. 2000 [doi>10.1006/ijhc.2000.0418]
• 26: 26 Baehrecke E Dang N Barbaria K Shneiderman B. Visualization and analysis of microarray and gene ontology data with treemap. 2003, In preparation.
• 27: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 28: 28 Fairbrother W, Yeh R, Sharp P, Burge C. Predictive identification of exonic splicing enhancers in human genes. Science, 2002; 297: 1007-1013.
• 29: 29 Mount S, Burks C, Hertz G, Stormo G, White O and Fields C. Splicing signals in Drosophila: intron size, information content, and consensus sequences. Nucleic Acids Research, 1992; 20: 4255-4262.
• 30: 30 Simpson C, Thow G, Clark G, Jennings S, Watters J and Brown J. Mutational analysis of a plant branchpoint and palypyrimidine tract required for constitutive splicing of a mini-exon. RNA, 2002; 8: 47-56.
• 31: Ed H. Chi , James Pitkow , Jock Mackinlay , Peter Pirolli , Rich Gossweiler , Stuart K. Card, Visualizing the evolution of Web ecologies, Proceedings of the SIGCHI conference on Human factors in computing systems, p.400-407, April 18-23, 1998, Los Angeles, California, United States [doi>10.1145/274644.274699]
• 32: 32 Keim D. Pixel-oriented visualization techniques for exploring very large databases. Journal of Computational and Statistical Graphics, 1996; 5: 58-77.
• 33: John V. Carlis , Joseph A. Konstan, Interactive visualization of serial periodic data, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.29-38, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288399]
• 34: 34 Roth W. MIMSY: a system for analyzing time series data in the stock market domain. Master's thesis, Department of Computer Science, University of Wisconsin, 1993.
• 35: Martin Wattenberg, Sketching a graph to query a time-series database, CHI '01 extended abstracts on Human factors in computing systems, March 31-April 05, 2001, Seattle, Washington [doi>10.1145/634067.634292]
• 36: 36 Spotfire. {WWW document} http://www.spotfire.com (accessed 14 May 2003).
• 37: Jeffrey P. Morrill, Distributed recognition of patterns in time series data, Communications of the ACM, v.41 n.5, p.45-51, May 1998 [doi>10.1145/274946.274955]
• 38: Ben Schneiderman, Dynamic Queries for Visual Information Seeking, IEEE Software, v.11 n.6, p.70-77, November 1994 [doi>10.1109/52.329404]
• 39: Allen R. Martin , Matthew O. Ward, High Dimensional Brushing for Interactive Exploration of Multivariate Data, Proceedings of the 6th conference on Visualization '95, p.271, October 29-November 03, 1995
• 40: 40 Girardin L and Brodbeck D. Interactive visualization of prices and earnings around the globe. In: Interactive Posters, IEEE Symposium on Information Visualization 2001, (San Diego, CA), October 22-23, 2001.
• 41: Alfred Inselberg , Tova Avidan, Classification and visualization for high-dimensional data, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.370-374, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347170]
• 42: Eamonn J. Keogh , Michael J. Pazzani, Relevance feedback retrieval of time series data, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.183-190, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312676]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
angular queries, bioinformatics, dynamic query, graphical user interfaces, temporal data, time series, timeboxes, timesearcher, visual query