{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:00:32Z","timestamp":1774983632269,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"the National Key Research and Development Plan","award":["2021YFB3300500"],"award-info":[{"award-number":["2021YFB3300500"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3709699","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Largest Triangle Sampling for Visualizing Time Series in Database"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0112-8329","authenticated-orcid":false,"given":"Lei","family":"Rui","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6868-4045","authenticated-orcid":false,"given":"Xiangdong","family":"Huang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9503-2755","authenticated-orcid":false,"given":"Shaoxu","family":"Song","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1698-8992","authenticated-orcid":false,"given":"Chen","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6841-7943","authenticated-orcid":false,"given":"Jianmin","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4214-7858","authenticated-orcid":false,"given":"Zhao","family":"Cao","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co., Ltd, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. https:\/\/en.wikipedia.org\/wiki\/Triangle_wave."},{"key":"e_1_2_1_2_1","unstructured":"[n. d.]. https:\/\/github.com\/apache\/iotdb\/tree\/research\/LTS-visualization."},{"key":"e_1_2_1_3_1","unstructured":"[n. d.]. https:\/\/github.com\/LeiRui\/vis-triangle."},{"key":"e_1_2_1_4_1","unstructured":"[n. d.]. https:\/\/github.com\/LeiRui\/vis-triangle\/blob\/main\/supplement.pdf."},{"key":"e_1_2_1_5_1","unstructured":"[n. d.]. https:\/\/scikit-image.org\/docs\/stable\/api\/skimage.metrics.html."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--57301--1_5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0--85729-079--3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90072--3"},{"key":"e_1_2_1_9_1","volume-title":"Some Informational Aspects of Visual Perception. Psychological review 61, 3","author":"Attneave Fred","year":"1954","unstructured":"Fred Attneave. 1954. Some Informational Aspects of Visual Perception. Psychological review 61, 3 (1954), 183."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.FUTURE.2019.02.005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Matthew Boyd. 2016. NIST Weather Station for Photovoltaic and Building System Research. doi:10.6028\/NIST.TN.1913","DOI":"10.6028\/NIST.TN.1913"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/JAS.2019.1911747"},{"key":"e_1_2_1_15_1","volume-title":"Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, Yanping Chen, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, Gustavo Batista, and Hexagon-ML.","author":"Dau Hoang Anh","year":"2019","unstructured":"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\/."},{"key":"e_1_2_1_16_1","volume-title":"Overmars","author":"de Berg Mark","year":"2008","unstructured":"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","edition":"3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248548"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/VIS54172.2023.00013"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2304.00900"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-014-0368--8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10618-019-00619--1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/S41019-023-00236--5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ENGAPPAI.2007.04.009"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045--2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90020--3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4757--1904--8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732953"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594521"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1179\/caj.1995.32.2.121"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.29"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659460"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11390-024--2934-X"},{"key":"e_1_2_1_33_1","volume-title":"Foundations of multidimensional and metric data structures","author":"Samet Hanan","unstructured":"Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press."},{"key":"e_1_2_1_34_1","volume-title":"Downsampling time series for visual representation. Master's thesis","author":"Steinarsson Sveinn","unstructured":"Sveinn Steinarsson. 2013. Downsampling time series for visual representation. Master's thesis. University of Iceland."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1179\/caj.1993.30.1.46"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589775"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589290"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2003.819861"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709699","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709699","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:16:06Z","timestamp":1774980966000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709699"],"URL":"https:\/\/doi.org\/10.1145\/3709699","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}