{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:31:16Z","timestamp":1765485076559},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>\n            One of the most common operations in analytic query processing is the application of an aggregate function to the result of a relational join. We describe an algorithm called the\n            <jats:italic>Sort-Merge-Shrink<\/jats:italic>\n            (SMS)\n            <jats:italic>Join<\/jats:italic>\n            for computing the answer to such a query over large, disk-based input tables. The key innovation of the SMS join is that if the input data are clustered in a statistically random fashion on disk, then at all times, the join provides an online, statistical estimator for the eventual answer to the query as well as probabilistic confidence bounds. Thus, a user can monitor the progress of the join throughout its execution and stop the join when satisfied with the estimate's accuracy or run the algorithm to completion with a total time requirement that is not much longer than that of other common join algorithms. This contrasts with other online join algorithms, which either do not offer such statistical guarantees or can only offer guarantees so long as the input data can fit into main memory.\n          <\/jats:p>","DOI":"10.1145\/1189769.1189775","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1382-1416","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["The Sort-Merge-Shrink join"],"prefix":"10.1145","volume":"31","author":[{"given":"Christopher","family":"Jermaine","sequence":"first","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alin","family":"Dobra","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subramanian","family":"Arumugam","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shantanu","family":"Joshi","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhijit","family":"Pol","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"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\/303976.303978"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1813"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_5_1","volume-title":"Sampling Techniques","author":"Cochran W.","unstructured":"Cochran , W. 1977. Sampling Techniques . John Wiley and Sons . Cochran, W. 1977. Sampling Techniques. John Wiley and Sons."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007646"},{"key":"e_1_2_1_7_1","volume-title":"VLDB Conference 299--310","author":"Dittrich J-P.","unstructured":"Dittrich , J-P. , Seeger , B. , Taylor , D. S. , and Widmayer , P . 2002. Progressive merge join: A generic and non-blocking sort-based join Algorithm . VLDB Conference 299--310 . Dittrich, J-P., Seeger, B., Taylor, D. S., and Widmayer, P. 2002. Progressive merge join: A generic and non-blocking sort-based join Algorithm. VLDB Conference 299--310."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773167"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065196"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564699"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233340"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1997.621151"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781635"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/308386.308455"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66933"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/115302.115300"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304209"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066222"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298540"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.93611"},{"key":"e_1_2_1_25_1","volume-title":"ICDE Conference 697--705","author":"Luo G.","unstructured":"Luo , G. , Naughton , J. F. , and Ellmann , C . 2002. A non-blocking parallel spatial join algorithm . ICDE Conference 697--705 . Luo, G., Naughton, J. F., and Ellmann, C. 2002. A non-blocking parallel spatial join algorithm. ICDE Conference 697--705."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564721"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564721"},{"key":"e_1_2_1_28_1","volume-title":"ICDE Conference 251--263","author":"Mokbel M. F.","unstructured":"Mokbel , M. F. , Lu , M. , and Aret , W. G . 2004. Hash-merge join: A non-blocking join algorithm for producing east and early join results . ICDE Conference 251--263 . Mokbel, M. F., Lu, M., and Aret, W. G. 2004. Hash-merge join: A non-blocking join algorithm for producing east and early join results. ICDE Conference 251--263."},{"key":"e_1_2_1_30_1","volume-title":"Mathematical Statistics","author":"Shao J.","unstructured":"Shao , J. 1999. Mathematical Statistics , Springer-Verlag . Shao, J. 1999. Mathematical Statistics, Springer-Verlag."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/6314.6315"},{"key":"e_1_2_1_32_1","first-page":"27","article-title":"XJoin: A reactively-scheduled pipelined join operator","volume":"23","author":"Urhan T.","year":"2000","unstructured":"Urhan , T. and Franklin , M. J. 2000 . XJoin: A reactively-scheduled pipelined join operator . IEEE Data Eng. Bull. 23 , 2, 27 -- 33 . Urhan, T. and Franklin, M. J. 2000. XJoin: A reactively-scheduled pipelined join operator. IEEE Data Eng. Bull. 23, 2, 27--33.","journal-title":"IEEE Data Eng. Bull."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:09:15Z","timestamp":1672261755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189775"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189775","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}