{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:52:42Z","timestamp":1759683162802,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T00:00:00Z","timestamp":1203033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0447966p"],"award-info":[{"award-number":["IIS-0447966p"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>\n            In the rank join problem, we are given a set of relations and a scoring function, and the goal is to return the join results with the top\n            <jats:italic>k<\/jats:italic>\n            scores. It is often the case in practice that the inputs may be accessed in ranked order and the scoring function is monotonic. These conditions allow for efficient algorithms that solve the rank join problem without reading all of the input. In this article, we present a thorough analysis of such rank join algorithms. A strong point of our analysis is that it is based on a more general problem statement than previous work, making it more relevant to the execution model that is employed by database systems. One of our results indicates that the well-known HRJN algorithm has shortcomings, because it does not stop reading its input as soon as possible. We find that it is NP-hard to overcome this weakness in the general case, but cases of limited query complexity are tractable. We prove the latter with an algorithm that infers provably tight bounds on the potential benefit of reading more input in order to stop as soon as possible. As a result, the algorithm achieves a cost that is within a constant factor of optimal.\n          <\/jats:p>","DOI":"10.1145\/1670243.1670249","type":"journal-article","created":{"date-parts":[[2010,2,16]],"date-time":"2010-02-16T20:51:06Z","timestamp":1266353466000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Optimal algorithms for evaluating rank joins in database systems"],"prefix":"10.1145","volume":"35","author":[{"given":"Karl","family":"Schnaitter","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neoklis","family":"Polyzotis","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,2,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.141"},{"volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases. VLDB Endowment, 475--486","author":"Bast H.","key":"e_1_2_1_2_1","unstructured":"Bast , H. , Majumdar , D. , Schenkel , R. , Theobald , M. , and Weikum , G . 2006. IO-Top-k: Index-Access optimized top-k query processing . In Proceedings of the 32nd International Conference on Very Large Data Bases. VLDB Endowment, 475--486 . Bast, H., Majumdar, D., Schenkel, R., Theobald, M., and Weikum, G. 2006. IO-Top-k: Index-Access optimized top-k query processing. In Proceedings of the 32nd International Conference on Very Large Data Bases. VLDB Endowment, 475--486."},{"volume-title":"Proceedings of the 18th International Conference on Data Engineering. IEEE Computer Society, 369--380","author":"Bruno N.","key":"e_1_2_1_3_1","unstructured":"Bruno , N. , Gravano , L. , and Marian , A . 2002. Evaluating top-k queries over Web-accessible databases . In Proceedings of the 18th International Conference on Data Engineering. IEEE Computer Society, 369--380 . Bruno, N., Gravano, L., and Marian, A. 2002. Evaluating top-k queries over Web-accessible databases. In Proceedings of the 18th International Conference on Data Engineering. IEEE Computer Society, 369--380."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564731"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233323"},{"volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases. Morgan Kaufmann","author":"Chaudhuri S.","key":"e_1_2_1_6_1","unstructured":"Chaudhuri , S. and Gravano , L . 1999. Evaluating top-k selection queries . In Proceedings of the 25th International Conference on Very Large Data Bases. Morgan Kaufmann , San Francisco, CA, 397--410. Chaudhuri, S. and Gravano, L. 1999. Evaluating top-k selection queries. In Proceedings of the 25th International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, CA, 397--410."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1600"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559890"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. VLDB Endowment, 950--961","author":"Ilyas I. F.","key":"e_1_2_1_11_1","unstructured":"Ilyas , I. F. , Aref , W. G. , and Elmagarmid , A. K . 2002. Joining ranked inputs in practice . In Proceedings of the 28th International Conference on Very Large Data Bases. VLDB Endowment, 950--961 . Ilyas, I. F., Aref, W. G., and Elmagarmid, A. K. 2002. Joining ranked inputs in practice. In Proceedings of the 28th International Conference on Very Large Data Bases. VLDB Endowment, 950--961."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0128-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189772"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007593"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780991_13"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142481"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066173"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. Morgan Kaufmann","author":"Natsev A.","key":"e_1_2_1_19_1","unstructured":"Natsev , A. , Chang , Y.-C. , Smith , J. R. , Li , C.-S. , and Vitter , J. S . 2001. Supporting incremental join queries on ranked inputs . In Proceedings of the 27th International Conference on Very Large Data Bases. Morgan Kaufmann , San Francisco, CA, 281--290. Natsev, A., Chang, Y.-C., Smith, J. R., Li, C.-S., and Vitter, J. S. 2001. Supporting incremental join queries on ranked inputs. In Proceedings of the 27th International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, CA, 281--290."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376924"},{"volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases. VLDB Endowment, 902--913","author":"Schnaitter K.","key":"e_1_2_1_21_1","unstructured":"Schnaitter , K. , Spiegel , J. , and Polyzotis , N . 2007. Depth estimation for ranking query optimization . In Proceedings of the 33rd International Conference on Very Large Data Bases. VLDB Endowment, 902--913 . Schnaitter, K., Spiegel, J., and Polyzotis, N. 2007. Depth estimation for ranking query optimization. In Proceedings of the 33rd International Conference on Very Large Data Bases. VLDB Endowment, 902--913."},{"volume-title":"Proceedings of the 21st International Conference on Very Large Data Bases. Morgan Kaufmann","author":"Yan W. P.","key":"e_1_2_1_22_1","unstructured":"Yan , W. P. and Larson , P . -A. 1995. Eager aggregation and lazy aggregation . In Proceedings of the 21st International Conference on Very Large Data Bases. Morgan Kaufmann , San Francisco, CA, 345--357. Yan, W. P. and Larson, P.-A. 1995. Eager aggregation and lazy aggregation. In Proceedings of the 21st International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, CA, 345--357."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1670243.1670249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:58Z","timestamp":1750250458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,15]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1670243.1670249"],"URL":"https:\/\/doi.org\/10.1145\/1670243.1670249","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2008,2,15]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}