{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:23Z","timestamp":1750307903151,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>\n            This article studies optimizing top-\n            <jats:italic>k<\/jats:italic>\n            queries in middlewares. While many assorted algorithms have been proposed, none is generally applicable to a wide range of possible scenarios. Existing algorithms lack both the \u201cgenerality\u201d to support a wide range of access scenarios and the systematic \u201cadaptivity\u201d to account for runtime specifics. To fulfill this critical lacking, we aim at taking a cost-based optimization approach: By runtime search over a space of algorithms, cost-based optimization is\n            <jats:italic>general<\/jats:italic>\n            across a wide range of access scenarios, yet\n            <jats:italic>adaptive<\/jats:italic>\n            to the specific access costs at runtime. While such optimization has been taken for granted for relational queries from early on, it has been clearly lacking for ranked queries. In this article, we thus identify and address the barriers of realizing such a unified framework. As the first barrier, we need to define a \u201ccomprehensive\u201d space encompassing all possibly optimal algorithms to search over. As the second barrier and a conflicting goal, such a space should also be \u201cfocused\u201d enough to enable efficient search. For SQL queries that are explicitly composed of relational operators, such a space, by definition, consists of schedules of relational operators (or \u201cquery plans\u201d). In contrast, top-\n            <jats:italic>k<\/jats:italic>\n            queries do not have\n            <jats:italic>logical tasks<\/jats:italic>\n            , such as relational operators. We thus define the logical tasks of top-\n            <jats:italic>k<\/jats:italic>\n            queries as building blocks to identify a comprehensive and focused space for top-\n            <jats:italic>k<\/jats:italic>\n            queries. We then develop efficient search schemes over such space for identifying the optimal algorithm. Our study indicates that our framework not only unifies, but also outperforms existing algorithms specifically designed for their scenarios.\n          <\/jats:p>","DOI":"10.1145\/1206049.1206054","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"5","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Optimizing top-k queries for middleware access"],"prefix":"10.1145","volume":"32","author":[{"given":"Seung-won","family":"Hwang","sequence":"first","affiliation":[{"name":"Pohang University of Science and Technology, Gyungbuk, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin Chen-chuan","family":"Chang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,3]]},"reference":[{"volume-title":"Proceedings of the International Conference on Cooperative Information System (CoopIS).","author":"Balke W.","key":"e_1_2_1_1_1","unstructured":"Balke , W. , Guentzer , U. , and Kiessling , W . 2002. On real-time top-k querying for mobile services . In Proceedings of the International Conference on Cooperative Information System (CoopIS). Balke, W., Guentzer, U., and Kiessling, W. 2002. On real-time top-k querying for mobile services. In Proceedings of the International Conference on Cooperative Information System (CoopIS)."},{"volume-title":"Proceedings of the International Conference on Cooperative Information System (ICDE).","author":"Bruno N.","key":"e_1_2_1_2_1","unstructured":"Bruno , N. , Gravano , L. , and Marian , A . 2002. Evaluating top-k queries over web-accessible databases . In Proceedings of the International Conference on Cooperative Information System (ICDE). Bruno, N., Gravano, L., and Marian, A. 2002. Evaluating top-k queries over web-accessible databases. In Proceedings of the International Conference on Cooperative Information System (ICDE)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253302"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","author":"Carey M. J.","key":"e_1_2_1_4_1","unstructured":"Carey , M. J. and Kossmann , D . 1998. Reducing the braking distance of an SQL query engine . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Carey, M. J. and Kossmann, D. 1998. Reducing the braking distance of an SQL query engine. In Proceedings of the International Conference on Very Large Data Bases (VLDB)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564731"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","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 International Conference on Very Large Data Bases (VLDB). Chaudhuri, S. and Gravano, L. 1999. Evaluating top-k selection queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB)."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","author":"Donjerkovic D.","key":"e_1_2_1_7_1","unstructured":"Donjerkovic , D. and Ramakrishnan , R . 1999. Probabilistic optimization of top n queries . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Donjerkovic, D. and Ramakrishnan, R. 1999. Probabilistic optimization of top n queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237715"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","author":"Guentzer U.","key":"e_1_2_1_10_1","unstructured":"Guentzer , U. , Balke , W. , and Kiessling , W . 2000. Optimizing multi-feature queries in image databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Guentzer, U., Balke, W., and Kiessling, W. 2000. Optimizing multi-feature queries in image databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB)."},{"volume-title":"Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC).","author":"Guentzer U.","key":"e_1_2_1_11_1","unstructured":"Guentzer , U. , Balke , W. , and Kiessling , W . 2001. Towards efficient multi-feature queries in heterogeneous environments . In Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC). Guentzer, U., Balke, W., and Kiessling, W. 2001. Towards efficient multi-feature queries in heterogeneous environments. In Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170078"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206049.1206054","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1206049.1206054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:37Z","timestamp":1750258057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206049.1206054"}},"subtitle":["A unified cost-based approach"],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1206049.1206054"],"URL":"https:\/\/doi.org\/10.1145\/1206049.1206054","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2007,3]]},"assertion":[{"value":"2007-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}