{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T02:40:53Z","timestamp":1755830453680,"version":"3.44.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No.62171155"],"award-info":[{"award-number":["No.62171155"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Stream join is a fundamental operation in stream processing and has attracted extensive research due to its large resource consumption and serious impact on system performance. As the theoretical basis of stream join systems, the stream join model greatly affects system performance. State-of-the-art stream join models either consume too much computing resources or too much storage resources, thus resulting in lower throughput or higher latency. In this paper, we propose a new stream join model for processing arbitrary join predicates, called CoModel, which offers a flexible trade-off between memory and computing resource consumption. More importantly, CoModel can achieve the minimum sum of the number of store operations and join operations among all existing join models, and thus can achieve the lowest latency and highest throughput when the overheads associated with the local stream join for each input tuple are approximately constant. We give a trade-off strategy for CoModel and theoretically prove its performance advantages based on queuing theory. Furthermore, we design and implement an adaptive distributed stream join system, CoStream, based on CoModel. CoStream can adaptively adjust its structure according to resource constraints and statistics of input data. We conduct extensive experiments for CoStream to evaluate its performance and adaptivity, and the results show that CoStream has the lowest latency and highest throughput in various scenarios.<\/jats:p>","DOI":"10.1145\/3654953","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1741-1300","authenticated-orcid":false,"given":"Qihang","family":"Wang","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8386-2858","authenticated-orcid":false,"given":"Decheng","family":"Zuo","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4578-6498","authenticated-orcid":false,"given":"Zhan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5196-1341","authenticated-orcid":false,"given":"Yanjun","family":"Shu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5756-0004","authenticated-orcid":false,"given":"Xin","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8646-5279","authenticated-orcid":false,"given":"Mingxuan","family":"He","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465272"},{"key":"e_1_2_2_2_1","first-page":"28","article-title":"Apache Flink#8482;: Stream and Batch Processing in a Single Engine","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink#8482;: Stream and Batch Processing in a Single Engine. IEEE Data Eng. Bull. , Vol. 38, 4 (2015), 28--38. http:\/\/sites.computer.org\/debull\/A15dec\/p28.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320217"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732281"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2947055"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-019--1940-x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0116-z"},{"volume-title":"Performance modeling and design of computer systems: queueing theory in action","author":"Harchol-Balter Mor","key":"e_1_2_2_8_1","unstructured":"Mor Harchol-Balter. 2013. Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366104"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229869"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260804"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746485"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3952"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2947618.2947620"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2977797.2977805"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TFUZZ.2019.2955056"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219622019500214"},{"key":"e_1_2_2_18_1","volume-title":"Low-latency Stream Join Architecture with Adjustable Ordering Precision. In 2016 USENIX Annual Technical Conference, USENIX ATC 2016","author":"Najafi Mohammadreza","year":"2016","unstructured":"Mohammadreza Najafi, Mohammad Sadoghi, and Hans-Arno Jacobsen. 2016. SplitJoin: A Scalable, Low-latency Stream Join Architecture with Adjustable Ordering Precision. In 2016 USENIX Annual Technical Conference, USENIX ATC 2016, Denver, CO, USA, June 22--24, 2016, , Ajay Gulati and Hakim Weatherspoon (Eds.). USENIX Association, 493--505. https:\/\/www.usenix.org\/conference\/atc16\/technical-sessions\/presentation\/najafi"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989423"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","unstructured":"Wendy Osborn. 2022. Shedding strategies for optimizing join processing in spatial data streams. In 17th International Conference on Future Networks and Communications \/ 19th International Conference on Mobile Systems and Pervasive Computing \/ 12th International Conference on Sustainable Energy Information Technology (FNC\/MobiSPC\/SEIT 2022) August 9--11 2022 Niagara Falls Ontario Canada (Procedia Computer Science Vol. 203) Elhadi M. Shakshuki (Ed.). Elsevier 149--156. https:\/\/doi.org\/10.1016\/J.PROCS.2022.07.021","DOI":"10.1016\/J.PROCS.2022.07.021"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2019.76"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732944"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ETFA46521.2020.9211958"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380576"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4257"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583678.3596891"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989389"},{"key":"e_1_2_2_28_1","unstructured":"TPC. 1993. The TPC-H benchmark. http:\/\/www.tpc.org\/tpch Retrieved October 1 2023 from"},{"key":"e_1_2_2_29_1","volume-title":"NEXMark - A Benchmark for Queries over Data Streams DRAFT. (09","author":"Tucker Pete","year":"2023","unstructured":"Pete Tucker, Kristin Tufte, Vassilis Papadimos, and David Maier. 2023. NEXMark - A Benchmark for Queries over Data Streams DRAFT. (09 2023)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS51616.2021.00017"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13222-022-00417-y"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50033-1"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007307"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223803"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00055"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00026"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452793"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385658.3385662"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00111"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:41:09Z","timestamp":1755787269000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654953"],"URL":"https:\/\/doi.org\/10.1145\/3654953","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}