research-article

Sketch-Based Fast and Accurate Querying of Time Series Using Parameter-Sharing LSTM Networks

Authors:

Krešimir Matković,

Helwig HauserAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 27, Issue 12

Pages 4495 - 4506

https://doi.org/10.1109/TVCG.2020.3002950

Published: 01 December 2021 Publication History

Abstract

Sketching is one common approach to query time series data for patterns of interest. Most existing solutions for matching the data with the interaction are based on an empirically modeled similarity function between the user’s sketch and the time series data with limited efficiency and accuracy. In this article, we introduce a machine learning based solution for fast and accurate querying of time series data based on a swift sketching interaction. We build on existing LSTM technology (long short-term memory) to encode both the sketch and the time series data in a network with shared parameters. We use data from a user study to let the network learn a proper similarity function. We focus our approach on perceived similarities and achieve that the learned model also includes a user-side aspect. To the best of our knowledge, this is the first data-driven solution for querying time series data in visual analytics. Besides evaluating the accuracy and efficiency directly in a quantitative way, we also compare our solution to the recently published Qetch algorithm as well as the commonly used dynamic time warping (DTW) algorithm.

References

[1]

M. Mannino and A. Abouzied, “Expressive time series querying with hand-drawn scale-free sketches,” in Proc. CHI Conf. Human Factors Comput. Syst., 2018, Art. no.

[2]

S. Ren, K. He, R. Girshick, and J. Sun, “Faster R-CNN: Towards real-time object detection with region proposal networks,” in Proc. Advances Neural Inf. Process. Syst., 2015, pp. 91–99.

[3]

A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Proc. Advances Neural Inf. Process. Syst., 2012, pp. 1097–1105.

[4]

Y. Shen, X. He, J. Gao, L. Deng, and G. Mesnil, “Learning semantic representations using convolutional neural networks for web search,” in Proc. 23rd Int. Conf. World Wide Web, 2014, pp. 373–374.

[5]

J. Mueller and A. Thyagarajan, “Siamese recurrent architectures for learning sentence similarity,” in Proc. 30th AAAI Conf. Artif. Intell., 2016, pp. 2786–2792.

[6]

Y. Bengio, P. Simard, and P. Frasconi, “Learning long-term dependencies with gradient descent is difficult,” IEEE Trans. Neural Netw., vol. 5, no. 2, pp. 157–166, Mar. 1994.

Digital Library

[7]

H. Sakoe and S. Chiba, “Dynamic programming algorithm optimization for spoken word recognition,” IEEE Trans. Acoust. Speech Signal Process., vol. 26, no. 1, pp. 43–49, Feb. 1978.

[8]

M. Novotnỳ and H. Hauser, “Similarity brushing for exploring multidimensional relations,” J. WSCG, vol. 14, pp. 105–112, 2006.

[9]

C. Fan and H. Hauser, “User-study based optimization of fast and accurate mahalanobis brushing in scatterplots,” in Proc. Conf. Vis. Model. Vis., 2017, pp. 77–84.

[10]

C. Fan and H. Hauser, “Fast and accurate CNN-based brushing in scatterplots,” in Computer Graphics Forum, vol. 37, no. 3. Hoboken, NJ, USA: Wiley, 2018, pp. 111–120.

[11]

C. Fan and H. Hauser, “Personalized sketch-based brushing in scatterplots,” IEEE Comput. Graph. Appl., vol. 39, no. 4, pp. 28–39, Jul./Aug. 2019.

[12]

C. Fan and H. Hauser, “On KDE-based brushing in scatterplots and how it compares to CNN-based brushing,” in Machine Learning Methods in Visualisation for Big Data. Aire-la-Ville, Switzerland: The Eurographics Association, 2019.

[13]

M. Wattenberg, “Sketching a graph to query a time-series database,” in Proc. Extended Abstracts Human Factors Comput. Syst., 2001, pp. 381–382.

[14]

C. Holz and S. Feiner, “Relaxed selection techniques for querying time-series graphs,” in Proc. 22nd Annu. ACM Symp. User Interface Softw. Technol., 2009, pp. 213–222.

[15]

M. Correll and M. Gleicher, “The semantics of sketch: Flexibility in visual query systems for time series data,” in Proc. IEEE Conf. Vis. Analytics Sci. Technol., 2016, pp. 131–140.

[16]

P. K. Muthumanickam, K. Vrotsou, M. Cooper, and J. Johansson, “Shape grammar extraction for efficient query-by-sketch pattern matching in long time series,” in Proc. IEEE Conf. Vis. Analytics Sci. Technol., 2016, pp. 121–130.

[17]

D. Q. Goldin and P. C. Kanellakis, “On similarity queries for time-series data: Constraint specification and implementation,” in Proc. Int. Conf. Princ. Practice Constraint Program., 1995, pp. 137–153.

[18]

H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. Keogh, “Querying and mining of time series data: experimental comparison of representations and distance measures,” Proc. VLDB Endowment, vol. 1, no. 2, pp. 1542–1552, 2008.

[19]

H. Hochheiser and B. Shneiderman, “Visual queries for finding patterns in time series data,” Comput. Sci. Dept., Univ. Maryland, 2002.

[20]

E. Keogh, H. Hochheiser, and B. Shneiderman, “An augmented visual query mechanism for finding patterns in time series data,” in Proc. Int. Conf. Flexible Query Answering Syst., 2002, pp. 240–250.

[21]

H. Hochheiser and B. Shneiderman, “Dynamic query tools for time series data sets: Timebox widgets for interactive exploration,” Inf. Vis., vol. 3, no. 1, pp. 1–18, 2004.

Digital Library

[22]

P. Buono, A. Aris, C. Plaisant, A. Khella, and B. Shneiderman, “Interactive pattern search in time series,” in Visualization and Data Analysis, vol. 5669. Bellingham, WA, USA: International Society for Optics and Photonics, 2005, pp. 175–187.

[23]

K. Ryall, N. Lesh, T. Lanning, D. Leigh, H. Miyashita, and S. Makino, “Querylines: approximate query for visual browsing,” in Proc. Extended Abstracts Human Factors Comput. Syst., 2005, pp. 1765–1768.

[24]

M. Gregory and B. Shneiderman, “Shape identification in temporal data sets,” in Expanding the Frontiers of Visual Analytics and Visualization. Berlin, Germany: Springer, 2012, pp. 305–321.

[25]

P. Eichmann and E. Zgraggen, “Evaluating subjective accuracy in time series pattern-matching using human-annotated rankings,” in Proc. 20th Int. Conf. Intell. User Interfaces, 2015, pp. 28–37.

[26]

D. D. Hoffman and M. Singh, “Salience of visual parts,” Cognition, vol. 63, no. 1, pp. 29–78, 1997.

[27]

E. J. Keogh and P. Smyth, “A probabilistic approach to fast pattern matching in time series databases,” in Proc. 3rd Int. Conf. Knowl. Discovery Data Mining, 1997, pp. 24–30.

[28]

N. Kong and M. Agrawala, “Perceptual interpretation of ink annotations on line charts,” in Proc. 22nd Annu. ACM Symp. User Interface Softw. Technol., 2009, pp. 233–236.

[29]

Y. Luo, X. Qin, N. Tang, G. Li, and X. Wang, “Deepeye: Creating good data visualizations by keyword search,” in Proc. Int. Conf. Manage. Data, 2018, pp. 1733–1736.

[30]

B. Saket, D. Moritz, H. Lin, V. Dibia, C. Demiralp, and J. Heer, “Beyond heuristics: Learning visualization design,” 2018,.

[31]

B. Saket, A. Endert, and Ç. Demiralp, “Task-based effectiveness of basic visualizations,” IEEE Trans. Vis. Comput. Graph., vol. 25, no. 7, pp. 2505–2512, Jul. 2019.

[32]

K. Hu, et al., “Viznet: Towards a large-scale visualization learning and benchmarking repository,” in Proc. CHI Conf. Human Factors Comput. Syst., 2019, pp. 1–12.

[33]

X. Qin, Y. Luo, N. Tang, and G. Li, “Making data visualization more efficient and effective: A survey,” VLDB J., vol. 29, pp. 93–117, 2020.

Digital Library

[34]

N. Tang, E. Wu, and G. Li, “Towards democratizing relational data visualization,” in Proc. Int. Conf. Manag. Data, 2019, pp. 2025–2030.

[35]

M. D. Zeiler and R. Fergus, “Visualizing and understanding convolutional networks,” in Proc. Eur. Conf. Comput. Vis., 2014, pp. 818–833.

[36]

S. Liu, X. Wang, M. Liu, and J. Zhu, “Towards better analysis of machine learning models: A visual analytics perspective,” Vis. Inform., vol. 1, no. 1, pp. 48–56, 2017.

[37]

F. M. Hohman, M. Kahng, R. Pienta, and D. H. Chau, “Visual analytics in deep learning: An interrogative survey for the next frontiers,” IEEE Trans. Vis. Comput. Graph., vol. 25, no. 8, pp. 2674–2693, Aug. 2018.

Digital Library

[38]

J. Han, J. Tao, and C. Wang, “Flownet: A deep learning framework for clustering and selection of streamlines and stream surfaces,” IEEE Trans. Vis. Comput. Graphics, vol. 26, no. 4, pp. 1732–1744, Apr. 2020.

[39]

B. Kim and T. Günther, “Robust reference frame extraction from unsteady 2D vector fields with convolutional neural networks,” Comput. Graph. Forum, vol. 38, no. 3, pp. 285–295, 2019.

[40]

K. Hu, M. A. Bakker, S. Li, T. Kraska, and C. Hidalgo, “Vizml: A machine learning approach to visualization recommendation,” in Proc. CHI Conf. Human Factors Comput. Syst., 2019, pp. 1–12.

[41]

V. Dibia and Ç. Demiralp, “Data2vis: Automatic generation of data visualizations using sequence-to-sequence recurrent neural networks,” IEEE Comput. Graph. Appl., vol. 39, no. 5, pp. 33–46, Sep./Oct. 2019.

Digital Library

[42]

Z. Chen, W. Zeng, Z. Yang, L. Yu, C.-W. Fu, and H. Qu, “Lassonet: Deep lasso-selection of 3D point clouds,” IEEE Trans. Vis. Comput. Graph., vol. 26, no. 1, pp. 195–204, Jan. 2020.

Digital Library

[43]

S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Comput., vol. 9, no. 8, pp. 1735–1780, 1997.

Digital Library

[44]

S. Chopra, R. Hadsell, Y. LeCun, et al., “Learning a similarity metric discriminatively, with application to face verification,” in Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit., 2005, pp. 539–546.

[45]

K. Schittkowski, “Easy-fit: A software system for data fitting in dynamical systems,” Structural Multidisciplinary Optim., vol. 23, no. 2, pp. 153–169, 2002.

Digital Library

[46]

R. Likert, “A technique for the measurement of attitudes,” Arch. Psychol., 1932.

Cited By

S Bhowmick SChen SSrivastava DBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Cognitive Psychology Meets Data Management: State of the Art and Future DirectionsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654682(590-596)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654682
Liu YXiao ZLu KGao LHuang ADu QWei QZhou Z(2024)Iptwins: visual analysis of injection-production correlations using digital twinsJournal of Visualization10.1007/s12650-024-00971-527:3(485-502)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s12650-024-00971-5
Tao ZYao BZhu J(2023)Exploring interval implicitization in real-valued time series classification and its applicationsThe Journal of Supercomputing10.1007/s11227-022-04792-x79:3(3373-3391)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s11227-022-04792-x
Show More Cited By

Index Terms

Sketch-Based Fast and Accurate Querying of Time Series Using Parameter-Sharing LSTM Networks

Index terms have been assigned to the content through auto-classification.

Recommendations

Expressive Time Series Querying with Hand-Drawn Scale-Free Sketches
CHI '18: Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems

We present Qetch, a tool where users freely sketch patterns on a scale-less canvas to query time series data without specifying query length or amplitude. We study how humans sketch time series patterns --- humans preserve visually salient perceptual ...
Querying by sketch geographical databases and ambiguities
DEXA'05: Proceedings of the 16th international conference on Database and Expert Systems Applications

This paper presents GSQL (Geographical Sketch Query Language), a sketch-based approach for querying geographical databases based on the GeoPQL query language. Geographic information is intrinsically spatial and can be conveniently represented using a bi-...
Sketch-based modeling
EG '16: Proceedings of the 37th Annual Conference of the European Association for Computer Graphics: Tutorials

Sketching is one of the most natural ways to exchange ideas. It has been used by human beings since prehistory. Research has shown that human beings have an inherent ability to understand sketches. This is why sketch-based interfaces for 3D modeling are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

1077-2626 © 2020 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 December 2021

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

S Bhowmick SChen SSrivastava DBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Cognitive Psychology Meets Data Management: State of the Art and Future DirectionsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654682(590-596)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654682
Liu YXiao ZLu KGao LHuang ADu QWei QZhou Z(2024)Iptwins: visual analysis of injection-production correlations using digital twinsJournal of Visualization10.1007/s12650-024-00971-527:3(485-502)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s12650-024-00971-5
Tao ZYao BZhu J(2023)Exploring interval implicitization in real-valued time series classification and its applicationsThe Journal of Supercomputing10.1007/s11227-022-04792-x79:3(3373-3391)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s11227-022-04792-x
Yan LXu NLi GBhowmick SChoi BXu J(2022)SENSORProceedings of the VLDB Endowment10.14778/3554821.355486615:12(3650-3653)Online publication date: 29-Sep-2022
https://dl.acm.org/doi/10.14778/3554821.3554866
Chung JKim WYoo KLee HAdar EChang M(2022)TaleBrush: Sketching Stories with Generative Pretrained Language ModelsProceedings of the 2022 CHI Conference on Human Factors in Computing Systems10.1145/3491102.3501819(1-19)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3491102.3501819

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents