Largest Triangle Sampling for Visualizing Time Series in Database
Authors: 
Lei Rui, Xiangdong Huang, Shaoxu Song, Chen Wang, Jianmin Wang, Zhao CaoAuthors Info & Claims
Article No.: 49, Pages 1 - 26
Abstract
In time series visualization, sampling is used to reduce the number of points while retaining the visual features of the raw time series. Area-based Largest Triangle Sampling (LTS) excels at preserving perceptually critical points. However, the heuristic solution to LTS by sequentially sampling points with the locally largest triangle area (a.k.a. Largest-Triangle-Three-Buckets, LTTB) suffers from suboptimal solution and query inefficiency. We address the shortcomings by contributing a novel Iterative Largest Triangle Sampling (ILTS) algorithm with convex hull acceleration. It refines the sampling results iteratively, capturing a broader perspective by integrating more points in each iteration. Remarkably, we prove that the largest triangle can always be found in the precomputed convex hulls, making the iterative sampling still efficient. Experiments demonstrate increased visual quality over state-of-the-art baselines and significant speedups over the brute force approach.
References
[1]
[n. d.]. https://en.wikipedia.org/wiki/Triangle_wave.
[2]
[n. d.]. https://github.com/apache/iotdb/tree/research/LTS-visualization.
[3]
[n. d.]. https://github.com/LeiRui/vis-triangle.
[4]
[n. d.]. https://github.com/LeiRui/vis-triangle/blob/main/supplement.pdf.
[5]
[n. d.]. https://scikit-image.org/docs/stable/api/skimage.metrics.html.
[6]
Rakesh Agrawal, Christos Faloutsos, and Arun N. Swami. 1993. Efficient Similarity Search In Sequence Databases. In Foundations of Data Organization and Algorithms, 4th International Conference, FODO'93, Chicago, Illinois, USA, October 13--15, 1993, Proceedings (Lecture Notes in Computer Science, Vol. 730), David B. Lomet (Ed.). Springer, 69--84.
[7]
Wolfgang Aigner, Silvia Miksch, Heidrun Schumann, and Christian Tominski. 2011. Visualization of Time-Oriented Data. Springer.
[8]
Alex M. Andrew. 1979. Another Efficient Algorithm for Convex Hulls in Two Dimensions. Inf. Process. Lett. 9, 5 (1979), 216--219.
[9]
Fred Attneave. 1954. Some Informational Aspects of Visual Perception. Psychological review 61, 3 (1954), 183.
[10]
Joseph Azar, Abdallah Makhoul, Mahmoud Barhamgi, and Raphaël Couturier. 2019. An energy efficient IoT data compression approach for edge machine learning. Future Gener. Comput. Syst. 96 (2019), 168--175.
[11]
C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. 1996. The Quickhull Algorithm for Convex Hulls. ACM Trans. Math. Softw. 22, 4 (1996), 469--483.
[12]
Matthew Boyd. 2016. NIST Weather Station for Photovoltaic and Building System Research.
[13]
Timothy M. Chan. 1996. Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions. Discret. Comput. Geom. 16, 4 (1996), 361--368.
[14]
Hoang Anh Dau, Anthony J. Bagnall, Kaveh Kamgar, Chin-Chia Michael Yeh, Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, and Eamonn J. Keogh. 2019. The UCR time series archive. IEEE CAA J. Autom. Sinica 6, 6 (2019), 1293--1305.
[15]
Hoang Anh Dau, Eamonn Keogh, Kaveh Kamgar, Chin-Chia Michael Yeh, Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, Yanping Chen, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, Gustavo Batista, and Hexagon-ML. 2019. The UCR Time Series Classification Archive. https://www.cs.ucr.edu/~eamonn/time_series_data_2018/.
[16]
Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer. https://www.worldcat.org/oclc/227584184
[17]
Janez Demsar. 2006. Statistical Comparisons of Classifiers over Multiple Data Sets. J. Mach. Learn. Res. 7 (2006), 1--30. https://jmlr.org/papers/v7/demsar06a.html
[18]
Jeroen Van Der Donckt, Jonas Van Der Donckt, Michaël Rademaker, and Sofie Van Hoecke. 2023. MinMaxLTTB: Leveraging MinMax-Preselection to Scale LTTB. In 2023 IEEE Visualization and Visual Analytics (VIS), Melbourne, Australia, October 21--27, 2023. IEEE, 21--25.
[19]
Jonas Van Der Donckt, M. Jeroen Van Der Donckt, Michaël Rademaker, and Sofie Van Hoecke. 2023. Data Point Selection for Line Chart Visualization: Methodological Assessment and Evidence-Based Guidelines. CoRR abs/2304.00900 (2023). arXiv:2304.00900
[20]
Frank Eichinger, Pavel Efros, Stamatis Karnouskos, and Klemens Böhm. 2015. A time-series compression technique and its application to the smart grid. VLDB J. 24, 2 (2015), 193--218.
[21]
Hassan Ismail Fawaz, Germain Forestier, Jonathan Weber, Lhassane Idoumghar, and Pierre-Alain Muller. 2019. Deep learning for time series classification: a review. Data Min. Knowl. Discov. 33, 4 (2019), 917--963.
[22]
Abdur Rahim Mohammad Forkan, Yong-Bin Kang, Felip Martí Carrillo, Abhik Banerjee, Chris McCarthy, Hadi Ghaderi, Breno G. S. Costa, Anas Dawod, Dimitrios Georgakopoulos, and Prem Prakash Jayaraman. 2024. AIoT-CitySense: AI and IoT-Driven City-Scale Sensing for Roadside Infrastructure Maintenance. Data Sci. Eng. 9, 1 (2024), 26--40.
[23]
Tak-Chung Fu, Korris Fu-Lai Chung, Robert Wing Pong Luk, and Chak-man Ng. 2008. Representing financial time series based on data point importance. Eng. Appl. Artif. Intell. 21, 2 (2008), 277--300.
[24]
Ronald L. Graham. 1972. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Inf. Process. Lett. 1, 4 (1972), 132--133.
[25]
Ray A. Jarvis. 1973. On the Identification of the Convex Hull of a Finite Set of Points in the Plane. Inf. Process. Lett. 2, 1 (1973), 18--21.
[26]
Ian T. Jolliffe. 1986. Principal Component Analysis. Springer.
[27]
Uwe Jugel, Zbigniew Jerzak, Gregor Hackenbroich, and Volker Markl. 2014. M4: A Visualization-Oriented Time Series Data Aggregation. Proc. VLDB Endow. 7, 10 (2014), 797--808.
[28]
Xenophon Kitsios, Panagiotis Liakos, Katia Papakonstantinopoulou, and Yannis Kotidis. 2023. Sim-Piece: Highly Accurate Piecewise Linear Approximation through Similar Segment Merging. Proc. VLDB Endow. 16, 8 (2023), 1910--1922.
[29]
Zhilin Li. 1995. An Examination of Algorithms for the Detection of Critical Points on Digital Cartographic Lines. The Cartographic Journal 32, 2 (1995), 121--125.
[30]
Xiaoyan Liu, Zhenjiang Lin, and Huaiqing Wang. 2008. Novel Online Methods for Time Series Segmentation. IEEE Trans. Knowl. Data Eng. 20, 12 (2008), 1616--1626.
[31]
Stavros Maroulis, Vassilis Stamatopoulos, George Papastefanatos, and Manolis Terrovitis. 2024. Visualization-aware Time Series Min-Max Caching with Error Bound Guarantees. Proc. VLDB Endow. 17, 8 (2024), 2091--2103. https://www.vldb.org/pvldb/vol17/p2091-maroulis.pdf
[32]
Manuel Milling, Shuo Liu, Andreas Triantafyllopoulos, Ilhan Aslan, and Björn W. Schuller. 2024. Audio Enhancement for Computer Audition - An Iterative Training Paradigm Using Sample Importance. J. Comput. Sci. Technol. 39, 4 (2024), 895--911.
[33]
Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press.
[34]
Sveinn Steinarsson. 2013. Downsampling time series for visual representation. Master's thesis. University of Iceland.
[35]
Mahes Visvalingam and J. Duncan Whyatt. 1993. Line Generalisation by Repeated Elimination of Points. Cartographic Journal 30 (1993), 46--51. https://api.semanticscholar.org/CorpusID:54049050
[36]
Chen Wang, Jialin Qiao, Xiangdong Huang, Shaoxu Song, Haonan Hou, Tian Jiang, Lei Rui, Jianmin Wang, and Jiaguang Sun. 2023. Apache IoTDB: A Time Series Database for IoT Applications. Proc. ACM Manag. Data 1, 2 (2023), 195:1--195:27.
[37]
Yunhai Wang, Yuchun Wang, Xin Chen, Yue Zhao, Fan Zhang, Eugene Wu, Chi-Wing Fu, and Xiaohui Yu. 2023. OM3: An Ordered Multi-level Min-Max Representation for Interactive Progressive Visualization of Time Series. Proc. ACM Manag. Data 1, 2 (2023), 145:1--145:24.
[38]
Zhou Wang, Alan C. Bovik, Hamid R. Sheikh, and Eero P. Simoncelli. 2004. Image quality assessment: from error visibility to structural similarity. IEEE Trans. Image Process. 13, 4 (2004), 600--612.
Index Terms
- Largest Triangle Sampling for Visualizing Time Series in Database
Recommendations
Interpolatory quad/triangle subdivision schemes for surface design
Recently the study and construction of quad/triangle subdivision schemes have attracted attention. The quad/triangle subdivision starts with a control net consisting of both quads and triangles and produces finer and finer meshes with quads and ...
Incremental subdivision for triangle meshes
We introduce incremental subdivision as a new adaptive subdivision method for triangle meshes. While regular (global) subdivisions produce a smooth surface from a given polygon mesh by refining all of its faces, adaptive subdivision produces a surface ...
Constructing Hierarchies for Triangle Meshes
We present a method to produce a hierarchy of triangle meshes that can be used to blend different levels of detail in a smooth fashion. The algorithm produces a sequence of meshes ${\cal M}_0, {\cal M}_1, {\cal M}_2, ..., {\cal M}_n,$ where each mesh ${\...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2025
2261 pages
Copyright © 2025 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 February 2025
Published in PACMMOD Volume 3, Issue 1
Author Tags
Qualifiers
- Research-article
Funding Sources
- the National Key Research and Development Plan
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 69Total Downloads
- Downloads (Last 12 months)69
- Downloads (Last 6 weeks)69
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in