{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:02Z","timestamp":1759638962185,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T00:00:00Z","timestamp":1488758400000},"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. Algorithms"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>\n            Given an array\n            <jats:italic>A<\/jats:italic>\n            [1,\n            <jats:italic>n<\/jats:italic>\n            ] of elements with a total order, we consider the problem of building a data structure that solves two queries: (\n            <jats:italic>a<\/jats:italic>\n            ) selection queries receive a range [\n            <jats:italic>i<\/jats:italic>\n            ,\n            <jats:italic>j<\/jats:italic>\n            ] and an integer\n            <jats:italic>k<\/jats:italic>\n            and return the position of the\n            <jats:italic>k<\/jats:italic>\n            th largest element in\n            <jats:italic>A<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ,\n            <jats:italic>j<\/jats:italic>\n            ]; (\n            <jats:italic>b<\/jats:italic>\n            ) top-\n            <jats:italic>k<\/jats:italic>\n            queries receive [\n            <jats:italic>i<\/jats:italic>\n            ,\n            <jats:italic>j<\/jats:italic>\n            ] and\n            <jats:italic>k<\/jats:italic>\n            and return the positions of the\n            <jats:italic>k<\/jats:italic>\n            largest elements in\n            <jats:italic>A<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ,\n            <jats:italic>j<\/jats:italic>\n            ]. These problems can be solved in optimal time,\n            <jats:italic>O<\/jats:italic>\n            (1+lg\n            <jats:italic>k<\/jats:italic>\n            \/lg lg\n            <jats:italic>n<\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ), respectively, using linear-space data structures.\n          <\/jats:p>\n          <jats:p>\n            We provide the first study of the\n            <jats:italic>encoding<\/jats:italic>\n            data structures for the above problems, where\n            <jats:italic>A<\/jats:italic>\n            cannot be accessed at query time. Several applications are interested in the relative order of the entries of\n            <jats:italic>A<\/jats:italic>\n            , and their positions, rather their actual values, and thus we do not need to keep\n            <jats:italic>A<\/jats:italic>\n            at query time. In those cases, encodings save storage space: we first show that any encoding answering such queries requires\n            <jats:italic>n<\/jats:italic>\n            lg\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            lg\n            <jats:italic>k<\/jats:italic>\n            ) bits of space; then, we design encodings using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            lg\n            <jats:italic>k<\/jats:italic>\n            ) bits, that is, asymptotically optimal up to constant factors, while preserving optimal query time.\n          <\/jats:p>","DOI":"10.1145\/3012939","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T19:12:04Z","timestamp":1488913924000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-\n            <i>k<\/i>\n            Queries"],"prefix":"10.1145","volume":"13","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Polytechnic Institute of New York University, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Leicester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Rao","family":"Satti","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Seoul National University, Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"volume-title":"Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794","author":"Belazzougui D.","key":"e_1_2_1_2_1","unstructured":"D. Belazzougui , P. Boldi , R. Pagh , and S. Vigna . 2009. Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses . In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794 . D. Belazzougui, P. Boldi, R. Pagh, and S. Vigna. 2009. Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses. In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635816"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629339"},{"key":"e_1_2_1_5_1","unstructured":"T. Bell J. Cleary and I. Witten. 1990. Text Compression. Prentice Hall.   T. Bell J. Cleary and I. Witten. 1990. Text Compression. Prentice Hall."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_83"},{"volume-title":"Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 241--251","author":"Chan T.","key":"e_1_2_1_9_1","unstructured":"T. Chan and B. T. Wilkinson . 2013. Adaptive and approximate orthogonal range counting . In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 241--251 . T. Chan and B. T. Wilkinson. 2013. Adaptive and approximate orthogonal range counting. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 241--251."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2013.0131"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.036"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_1"},{"key":"e_1_2_1_17_1","unstructured":"P. Gawrychowski and P. K. Nicholson. 2015b. Optimal encodings for range min-max and top-k. CoRR 1411.6581v2 (2015). http:\/\/arxiv.org\/abs\/1411.6581v2.  P. Gawrychowski and P. K. Nicholson. 2015b. Optimal encodings for range min-max and top-k. CoRR 1411.6581v2 (2015). http:\/\/arxiv.org\/abs\/1411.6581v2."},{"volume-title":"Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Part I (LNCS 9134)","author":"Gawrychowski P.","key":"e_1_2_1_18_1","unstructured":"P. Gawrychowski and P. K. Nicholson . 2015a. Optimal encodings for range top-k, selection, and min-max . In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Part I (LNCS 9134) . 593--604. P. Gawrychowski and P. K. Nicholson. 2015a. Optimal encodings for range top-k, selection, and min-max. In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Part I (LNCS 9134). 593--604."},{"volume-title":"Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373","author":"Golynski A.","key":"e_1_2_1_19_1","unstructured":"A. Golynski , I. Munro , and S. Rao . 2006. Rank\/select operations on large alphabets: A tool for text indexing . In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373 . A. Golynski, I. Munro, and S. Rao. 2006. Rank\/select operations on large alphabets: A tool for text indexing. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373."},{"volume-title":"Proc. 21st Annual European Symposium on Algorithms (ESA) (LNCS 8125)","author":"Grossi R.","key":"e_1_2_1_20_1","unstructured":"R. Grossi , J. Iacono , G. Navarro , R. Raman , and S. Srinivasa Rao . 2013. Encodings for range selection and top-k queries . In Proc. 21st Annual European Symposium on Algorithms (ESA) (LNCS 8125) . 553--564. R. Grossi, J. Iacono, G. Navarro, R. Raman, and S. Srinivasa Rao. 2013. Encodings for range selection and top-k queries. In Proc. 21st Annual European Symposium on Algorithms (ESA) (LNCS 8125). 553--564."},{"volume-title":"Proc. 26th International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs 3). 517--528","author":"Grossi R.","key":"e_1_2_1_21_1","unstructured":"R. Grossi , A. Orlandi , R. Raman , and S. S. Rao . 2009. More haste, less waste: Lowering the redundancy in fully indexable dictionaries . In Proc. 26th International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs 3). 517--528 . R. Grossi, A. Orlandi, R. Raman, and S. S. Rao. 2009. More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In Proc. 26th International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs 3). 517--528."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488440"},{"volume-title":"Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 805--813","author":"J\u00f8rgensen A. G.","key":"e_1_2_1_23_1","unstructured":"A. G. J\u00f8rgensen and K. G. Larsen . 2011. Range selection and median: Tight cell probe lower bounds and adaptive data structures . In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 805--813 . A. G. J\u00f8rgensen and K. G. Larsen. 2011. Range selection and median: Tight cell probe lower bounds and adaptive data structures. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 805--813."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559918"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574697"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_27_1","volume-title":"Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 657--666","author":"Muthukrishnan S.","year":"2002","unstructured":"S. Muthukrishnan . 2002 . Efficient algorithms for document retrieval problems . In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 657--666 . S. Muthukrishnan. 2002. Efficient algorithms for document retrieval problems. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 657--666."},{"volume-title":"Proc. 34th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 291--302","author":"Navarro G.","key":"e_1_2_1_28_1","unstructured":"G. Navarro , R. Raman , and S. Srinivasa Rao . 2014. Asymptotically optimal encodings for range selection . In Proc. 34th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 291--302 . G. Navarro, R. Raman, and S. Srinivasa Rao. 2014. Asymptotically optimal encodings for range selection. In Proc. 34th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 291--302."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601073"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132551"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_32_1","volume-title":"Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 225--232","author":"Sadakane K.","year":"2002","unstructured":"K. Sadakane . 2002 . Succinct representations of lcp information and improvements in the compressed suffix arrays . In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 225--232 . K. Sadakane. 2002. Succinct representations of lcp information and improvements in the compressed suffix arrays. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 225--232."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3012939","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3012939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:39Z","timestamp":1750273539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3012939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3012939"],"URL":"https:\/\/doi.org\/10.1145\/3012939","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}