{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:20:58Z","timestamp":1772205658021,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>A common analysis task over a stream of time series is to find all pairs of windows whose correlation is above a given threshold. For a large number of streams, doing so naively, i.e., checking the Cartesian product, is too expensive. In essence, finding correlated pairs in a non-naive way boils down to a high-dimensional similarity join in a Euclidean space. While there are similarity join algorithms, such as Quickjoin and \u03b5-kdB tree, they are inefficient for high-dimensional data. We propose CorrJoin, short for Correlation Join, that combines a complementary dimension reduction and transformation step with a subsequent double-filtering step. In the first step, we reduce the dimensionality of data stream windows by combining a fast but inaccurate method, Piecewise Aggregate Approximation (PAA), with an accurate and slow one, Singular Value Decomposition (SVD). Not only does SVD compensate for the weaknesses of PAA, it also transforms the data to make the first filter based on bucketing more effective. The second filter, which uses Euclidean distances, reduces the number of false positives before computing exact correlations. Our experiments reveal that in common settings, CorrJoin is an order of magnitude faster than state-of-the-art approaches (up to 20 times faster than Quickjoin).<\/jats:p>","DOI":"10.1145\/3626722","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Correlation Joins over Time Series Data Streams Utilizing Complementary Dimension Reduction and Transformation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7956-0075","authenticated-orcid":false,"given":"AmirReza","family":"Alizade Nikoo","sequence":"first","affiliation":[{"name":"University of Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3694-9026","authenticated-orcid":false,"given":"Michael H.","family":"B\u00f6hlen","sequence":"additional","affiliation":[{"name":"University of Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9666-1932","authenticated-orcid":false,"given":"Sven","family":"Helmer","sequence":"additional","affiliation":[{"name":"University of Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.11"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57301-1_5"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/12089867X"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-016-0122--9"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007636"},{"key":"e_1_2_2_6_1","volume-title":"Beyond one billion time series: Indexing and mining very large time series collections with iSAX2. Knowledge and Information Systems","author":"Camerra Alessandro","year":"2014","unstructured":"Alessandro Camerra, Jin Shieh, Themis Palpanas, Thanawin Rakthanmanon, and Eamonn Keogh. 2014. Beyond one billion time series: Indexing and mining very large time series collections with iSAX2. Knowledge and Information Systems (2014)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568520"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325903"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081966"},{"key":"e_1_2_2_10_1","volume-title":"Proc. VLDB Endow. (aug","author":"Sarma Akash Das","year":"2014","unstructured":"Akash Das Sarma, Yeye He, and Surajit Chaudhuri. 2014. ClusterJoin: A Similarity Joins Framework Using Map-Reduce. Proc. VLDB Endow. (aug 2014), 1059--1070."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454226"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the VLDB 2019 PhD Workshop, co-located with the 45th International Conference on Very Large Databases (VLDB","author":"Echihabi Karima","year":"2019","unstructured":"Karima Echihabi. 2019. Truly Scalable Data Series Similarity Search. In Proceedings of the VLDB 2019 PhD Workshop, co-located with the 45th International Conference on Very Large Databases (VLDB 2019), Los Angeles, California, USA, August 26--30, 2019 (CEUR Workshop Proceedings). CEUR-WS.org."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282498"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the Compression and Complexity of Sequences 1997 (SEQUENCES '97)","author":"Faloutsos C.","unstructured":"C. Faloutsos, H. Jagadish, A. Mendelzon, and T. Milo. 1997. A Signature Technique for Similarity-Based Queries. In Proceedings of the Compression and Complexity of Sequences 1997 (SEQUENCES '97). IEEE Computer Society, USA."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564734"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389751"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363819"},{"key":"e_1_2_2_19_1","unstructured":"Alfred Haar. [n. d.]. On the Theory of Orthogonal Function Systems. https:\/\/pdfs.semanticscholar.org\/3b08\/b61ba914626db518b6add5b73ac21d62f0c1.pdf."},{"key":"e_1_2_2_20_1","volume-title":"Jacox and Hanan Samet","author":"Edwin","year":"2008","unstructured":"Edwin H. Jacox and Hanan Samet. 2008. Metric Space Similarity Joins. ACM Trans. Database Syst. (jun 2008), 38 pages."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72524-4_57"},{"key":"e_1_2_2_22_1","volume-title":"Noise: A Flaw in Human Judgment. Little","author":"Kahnemann Daniel","year":"2021","unstructured":"Daniel Kahnemann, Olivier Sibony, and Cass Sunstein. 2021. Noise: A Flaw in Human Judgment. Little, Brown Spark, New York."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAI.1997.632306"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011669"},{"key":"e_1_2_2_25_1","volume-title":"Recovery of Missing Values using Matrix Decomposition Techniques. Ph.,D. Dissertation","author":"Khayati Mourad","unstructured":"Mourad Khayati. 2015. Recovery of Missing Values using Matrix Decomposition Techniques. Ph.,D. Dissertation. University of Zurich."},{"key":"e_1_2_2_26_1","volume-title":"Proceedings of the 15th International Conference on Data Engineering (ICDE '99)","author":"Chan Kin-Pong","year":"1999","unstructured":"Kin-Pong Chan and Ada Wai-Chee Fu. 1999. Efficient Time Series Matching by Wavelets. In Proceedings of the 15th International Conference on Data Engineering (ICDE '99). IEEE Computer Society, USA, 126."},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the VLDB Endowment (02","author":"Kondylakis Haridimos","year":"2018","unstructured":"Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas. 2018. Coconut: a scalable bottom-up approach for building data series indexes. Proceedings of the VLDB Endowment (02 2018), 677--690."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253332"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1996.492205"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556552"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190666"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.184"},{"key":"e_1_2_2_33_1","volume-title":"Proc. VLDB Endow. (sep","author":"Linardi Michele","year":"2018","unstructured":"Michele Linardi and Themis Palpanas. 2018. Scalable, Variable-Length Similarity Search in Data Series: The ULISSE Approach. Proc. VLDB Endow. (sep 2018), 2236--2248."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031203"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.52"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807188"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-33702-5_3"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083674"},{"key":"e_1_2_2_39_1","volume-title":"MESSI: In-Memory Data Series Indexing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 337--348","author":"Peng Botao","year":"2020","unstructured":"Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2020. MESSI: In-Memory Data Series Indexing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 337--348."},{"key":"e_1_2_2_40_1","first-page":"2151","article-title":"ParIS: Data Series Indexing on Multi-Core Architectures","volume":"33","author":"Peng Botao","year":"2021","unstructured":"Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2021. ParIS: Data Series Indexing on Multi-Core Architectures. IEEE Transactions on Knowledge and Data Engineering, Vol. 33, 5 (2021), 2151--2164.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994711"},{"key":"e_1_2_2_42_1","volume-title":"Francesco Fusco, and Mathieu Sinn.","author":"Qiu Han","year":"2018","unstructured":"Han Qiu, Hoang Thanh Lam, Francesco Fusco, and Mathieu Sinn. 2018. Learning Correlation Space for Time Series. https:\/\/arxiv.org\/pdf\/1802.03628.pdf. arxiv: 1802.03628 [cs.LG]"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1999.754957"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.68"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.chemolab.2013.10.012"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/645482.653448"},{"key":"e_1_2_2_47_1","volume-title":"Digital Signal Processing","author":"Oppenheim A. V.","unstructured":"A. V. Oppenheim und R. W. Schafer. 1975. Digital Signal Processing. Prentice Hall, Englewood Cliffs, New Jersey."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.snb.2012.01.074"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2007.07.002"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/238355.238365"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505746"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526177"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0580-z"},{"key":"e_1_2_2_55_1","volume-title":"Proceedings of 16th International Conference on Data Engineering. 13--22","author":"Sidiropoulos N. D.","unstructured":"B.. Yi, N. D. Sidiropoulos, T. Johnson, H. V. Jagadish, C. Faloutsos, and A. Biliris. 2000. Online data mining for co-evolving time sequences. In Proceedings of 16th International Conference on Data Engineering. 13--22."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/645926.671689"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00190"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978--155860869--6\/50039--1"},{"key":"e_1_2_2_59_1","volume-title":"ADS: The Adaptive Data Series Index. The VLDB Journal (Dec","author":"Zoumpatianos Kostas","year":"2016","unstructured":"Kostas Zoumpatianos, Stratos Idreos, and Themis Palpanas. 2016. ADS: The Adaptive Data Series Index. The VLDB Journal (Dec 2016), 843--866."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626722","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:00:22Z","timestamp":1755867622000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626722"],"URL":"https:\/\/doi.org\/10.1145\/3626722","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}