{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T16:31:00Z","timestamp":1778344260361,"version":"3.51.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007780","name":"Indian Institute of Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"GRF","award":["14203421, 14207820"],"award-info":[{"award-number":["14203421, 14207820"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            A\n            <jats:italic>reporting query<\/jats:italic>\n            returns the objects satisfying a predicate\n            <jats:italic>q<\/jats:italic>\n            from an input set. In\n            <jats:italic>prioritized reporting<\/jats:italic>\n            , each object carries a real-valued weight (which can be query dependent), and a query returns the objects that satisfy\n            <jats:italic>q<\/jats:italic>\n            and have weights at least a threshold \u03c4. A\n            <jats:italic>\n              top-\n              <jats:italic>k<\/jats:italic>\n              query\n            <\/jats:italic>\n            finds, among all the objects satisfying\n            <jats:italic>q<\/jats:italic>\n            , the\n            <jats:italic>k<\/jats:italic>\n            ones of the largest weights; a\n            <jats:italic>max query<\/jats:italic>\n            is a special instance with\n            <jats:italic>k<\/jats:italic>\n            = 1. We want to design data structures of small space to support queries (and possibly updates) efficiently.\n          <\/jats:p>\n          <jats:p>\n            Previous work has shown that a top-\n            <jats:italic>k<\/jats:italic>\n            structure can also support max and prioritized queries with no performance deterioration. This article explores the opposite direction: do prioritized queries, possibly combined with max queries, imply top-\n            <jats:italic>k<\/jats:italic>\n            search? Subject to mild conditions, we provide affirmative answers with two reduction techniques. The first converts a prioritized structure into a static top-\n            <jats:italic>k<\/jats:italic>\n            structure with the same space complexity and only a logarithmic blowup in query time. If a max structure is available in addition, our second reduction yields a top-\n            <jats:italic>k<\/jats:italic>\n            structure with no degradation in expected performance (this holds for the space, query, and update complexities). Our techniques significantly simplify the design of top-\n            <jats:italic>k<\/jats:italic>\n            structures because structures for max and prioritized queries are often easier to obtain. We demonstrate this by developing top-\n            <jats:italic>k<\/jats:italic>\n            structures for interval stabbing, 3D dominance, halfspace reporting, linear ranking, and\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            nearest neighbor search in the RAM and the external memory computation models.\n          <\/jats:p>","DOI":"10.1145\/3546074","type":"journal-article","created":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T12:33:25Z","timestamp":1656506005000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Generic Techniques for Building Top-\n            <i>k<\/i>\n            Structures"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5984-0934","authenticated-orcid":false,"given":"Saladi","family":"Rahul","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bengaluru, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_4"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261299"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.31"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.21"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.04.003"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1709"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/10078791X"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2955098"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559816"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795295936"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.09.006"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/toc\/10.1145\/996546"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/060669474"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/11575832_10","volume-title":"String Processing and Information Retrieval (SPIRE)","author":"Bialynicka-Birula Iwona","year":"2005","unstructured":"Iwona Bialynicka-Birula and Roberto Grossi. 2005. Rank-sensitive data structures. In String Processing and Information Retrieval (SPIRE). 79\u201390."},{"key":"e_1_3_2_17_2","first-page":"23:1\u201323:14","volume-title":"Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","author":"Brodal Gerth Stolting","year":"2016","unstructured":"Gerth Stolting Brodal. 2016. External memory three-sided range reporting and Top-k queries with sublogarithmic updates. In Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS\u201916). 23:1\u201323:14."},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-642-10631-6_19","volume-title":"International Symposium on Algorithms and Computation (ISAAC\u201909)","author":"Brodal Gerth Stolting","year":"2009","unstructured":"Gerth Stolting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro Lopez-Ortiz. 2009. Online sorted range reporting. In International Symposium on Algorithms and Computation (ISAAC\u201909). 173\u2013182."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703439404"},{"key":"e_1_3_2_20_2","first-page":"31:1\u201331:14","volume-title":"Proceedings of International Colloquium on Automata, Languages and Programming (ICALP\u201918)","author":"Chan Timothy M.","year":"2018","unstructured":"Timothy M. Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. 2018. Orthogonal point location and rectangle stabbing queries in 3-d. In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP\u201918). 31:1\u201331:14."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187875"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2590774"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0518-2"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.32"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209017"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/978-3-642-40273-9_18","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"Lewenstein Moshe","year":"2013","unstructured":"Moshe Lewenstein. 2013. Orthogonal range searching for text indexing. In Space-Efficient Data Structures, Streams, and Algorithms. 267\u2013302."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90006-E"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_3_2_36_2","first-page":"657","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Muthukrishnan S.","year":"2002","unstructured":"S. Muthukrishnan. 2002. Efficient algorithms for document retrieval problems. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). 657\u2013666."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.84"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/140998949"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594557"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2316807"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745777"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.07.013"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_68"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213576"},{"key":"e_1_3_2_46_2","first-page":"313","volume-title":"Proceedings of Symposium on Computational Geometry (SoCG\u201912)","author":"Tao Yufei","year":"2012","unstructured":"Yufei Tao. 2012. Stabbing horizontal segments with rays. In Proceedings of Symposium on Computational Geometry (SoCG\u201912). 313\u2013322."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594543"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.90"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546074","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3546074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:19Z","timestamp":1750188619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3546074"],"URL":"https:\/\/doi.org\/10.1145\/3546074","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2021-02-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}