{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:12Z","timestamp":1779174732776,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T00:00:00Z","timestamp":1548720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["GRF-621413, GRF-16211614, and GRF-16200415"],"award-info":[{"award-number":["GRF-621413, GRF-16211614, and GRF-16200415"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1251019, 1302663 and 1443046"],"award-info":[{"award-number":["1251019, 1302663 and 1443046"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61428204"],"award-info":[{"award-number":["61428204"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>\n            Joins are expensive, and online aggregation over joins was proposed to mitigate the cost, which offers users a nice and flexible tradeoff between query efficiency and accuracy in a continuous, online fashion. However, the state-of-the-art approach, in both internal and external memory, is based on ripple join, which is still very expensive and even needs unrealistic assumptions (e.g., tuples in a table are stored in random order). This article proposes a new approach, the\n            <jats:italic>wander join<\/jats:italic>\n            algorithm, to the online aggregation problem by performing random walks over the underlying join graph. We also design an optimizer that chooses the optimal plan for conducting the random walks without having to collect any statistics\n            <jats:italic>a priori<\/jats:italic>\n            . Compared with ripple join, wander join is particularly efficient for equality joins involving multiple tables, but also supports \u03b8-joins. Selection predicates and group-by clauses can be handled as well. To demonstrate the usefulness of wander join, we have designed and implemented XDB (approXimate DB) by integrating wander join into various systems including PostgreSQL, Spark, and a stand-alone plug-in version using PL\/SQL. The design and implementation of XDB has demonstrated wander join\u2019s practicality in a full-fledged database system. Extensive experiments using the TPC-H benchmark have demonstrated the superior performance of wander join over ripple join.\n          <\/jats:p>","DOI":"10.1145\/3284551","type":"journal-article","created":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T13:16:22Z","timestamp":1548767782000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Wander Join and XDB"],"prefix":"10.1145","volume":"44","author":[{"given":"Feifei","family":"Li","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, Utah, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Wu","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuoyue","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, Utah, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593667"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367533"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_6_1","volume-title":"Berger","author":"Casella George","year":"2001","unstructured":"George Casella and Roger L . Berger . 2001 . Statistical Inference. Duxbury Press . George Casella and Roger L. Berger. 2001. Statistical Inference. Duxbury Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276343"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807186"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915249"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687675"},{"key":"e_1_2_1_12_1","unstructured":"Aleksandar Dragojevic Dushyanth Narayanan Miguel Castro and Orion Hodson. 2014. FaRM: Fast remote memory. In NSDI. 401--414.   Aleksandar Dragojevic Dushyanth Narayanan Miguel Castro and Orion Hodson. 2014. FaRM: Fast remote memory. In NSDI. 401--414."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190660"},{"key":"e_1_2_1_14_1","volume-title":"Felix Martin Schuhknecht, and Jens Dittrich","author":"Gembalczyk David","year":"2017","unstructured":"David Gembalczyk , Felix Martin Schuhknecht, and Jens Dittrich . 2017 . An experimental analysis of different key-value stores and relational databases. In Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW\u201917), 17. Fachtagung des GI-Fachbereichs \u201cDatenbanken und Informationssysteme\u201d (DBIS) . David Gembalczyk, Felix Martin Schuhknecht, and Jens Dittrich. 2017. An experimental analysis of different key-value stores and relational databases. In Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW\u201917), 17. Fachtagung des GI-Fachbereichs \u201cDatenbanken und Informationssysteme\u201d (DBIS)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276334"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180918"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0345-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/646496.695465"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168652"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009835310546"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594545"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247667"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000828"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733064"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247560"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412335"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.106"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497428"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0095-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735485"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142579"},{"key":"e_1_2_1_37_1","volume-title":"ACM Symposium on Principles of Database Systems.","author":"Lipton R. J.","unstructured":"R. J. Lipton and J. F. Naughton . 1990. Query size estimation by adaptive sampling . In ACM Symposium on Principles of Database Systems. R. J. Lipton and J. F. Naughton. 1990. Query size estimation by adaptive sampling. In ACM Symposium on Principles of Database Systems."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.93611"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564721"},{"key":"e_1_2_1_40_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 1995. Randomized Algorithms . Cambridge University Press . Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556563"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1965724.1965751"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402748"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723719"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484874"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7132-8"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_49_1","volume-title":"International Conference on Very Large Data Bases.","author":"Wang Lu","year":"2016","unstructured":"Lu Wang , Robert Christensen , Feifei Li , and Ke Yi . 2016 . Spatial online sampling and aggregation . In International Conference on Very Large Data Bases. Lu Wang, Robert Christensen, Feifei Li, and Ke Yi. 2016. Spatial online sampling and aggregation. In International Conference on Very Large Data Bases."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150501"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687678"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807238"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386122"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463701"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2735381"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915240"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594532"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284551","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284551","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284551","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:45Z","timestamp":1750208505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284551"}},"subtitle":["Online Aggregation via Random Walks"],"short-title":[],"issued":{"date-parts":[[2019,1,29]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3284551"],"URL":"https:\/\/doi.org\/10.1145\/3284551","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,29]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}