{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T09:15:20Z","timestamp":1781082920183,"version":"3.54.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T00:00:00Z","timestamp":1651708800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We present a constant-round algorithm in the massively parallel computation\n(MPC) model for evaluating a natural join where every input relation has two\nattributes. Our algorithm achieves a load of $\\tilde{O}(m\/p^{1\/\\rho})$ where\n$m$ is the total size of the input relations, $p$ is the number of machines,\n$\\rho$ is the join's fractional edge covering number, and $\\tilde{O}(.)$ hides\na polylogarithmic factor. The load matches a known lower bound up to a\npolylogarithmic factor. At the core of the proposed algorithm is a new theorem\n(which we name the \"isolated cartesian product theorem\") that provides fresh\ninsight into the problem's mathematical structure. Our result implies that the\nsubgraph enumeration problem, where the goal is to report all the occurrences\nof a constant-sized subgraph pattern, can be settled optimally (up to a\npolylogarithmic factor) in the MPC model.<\/jats:p>","DOI":"10.46298\/lmcs-18(2:6)2022","type":"journal-article","created":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T15:32:23Z","timestamp":1651851143000},"source":"Crossref","is-referenced-by-count":2,"title":["A Near-Optimal Parallel Algorithm for Joining Binary Relations"],"prefix":"10.46298","volume":"Volume 18, Issue 2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4032-0709","authenticated-orcid":false,"given":"Bas","family":"Ketsman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2022,5,5]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9436\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9436\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:18:47Z","timestamp":1687292327000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/6944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,5]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(2:6)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2011.14482v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2011.14482v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2011.14482","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2011.14482","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,5]]},"article-number":"6944"}}