{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:59Z","timestamp":1740109319226,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NTNU Norwegian University of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,11]]},"abstract":"Abstract<\/jats:title>We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering $${\\text{Top-}}{k}$$<\/jats:tex-math>\n \n Top-<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For an $$m \\times n$$<\/jats:tex-math>\n \n m<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> array, with $$m \\le n$$<\/jats:tex-math>\n \n m<\/mml:mi>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we first propose an encoding for answering 1-sided $${\\textsf {Top}}{\\text {-}}k{}$$<\/jats:tex-math>\n \n Top<\/mml:mi>\n -<\/mml:mtext>\n k<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> queries, whose query range is restricted to $$[1 \\dots m][1 \\dots a]$$<\/jats:tex-math>\n \n [<\/mml:mo>\n 1<\/mml:mn>\n \u22ef<\/mml:mo>\n m<\/mml:mi>\n ]<\/mml:mo>\n [<\/mml:mo>\n 1<\/mml:mn>\n \u22ef<\/mml:mo>\n a<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for $$1 \\le a \\le n$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n \u2264<\/mml:mo>\n a<\/mml:mi>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Next, we propose an encoding for answering for the general (4-sided) $${\\textsf {Top}}{\\text {-}}k{}$$<\/jats:tex-math>\n \n Top<\/mml:mi>\n -<\/mml:mtext>\n k<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> queries that takes $$(m\\lg {{(k+1)n \\atopwithdelims ()n}}+2nm(m-1)+o(n))$$<\/jats:tex-math>\n \n (<\/mml:mo>\n m<\/mml:mi>\n lg<\/mml:mo>\n \n \n \n (<\/mml:mo>\n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n +<\/mml:mo>\n 2<\/mml:mn>\n n<\/mml:mi>\n m<\/mml:mi>\n \n (<\/mml:mo>\n m<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n o<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits, which generalizes the joint Cartesian tree<\/jats:italic> of Golin et al. [TCS 2016]. Compared with trivial $$O(nm\\lg {n})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n m<\/mml:mi>\n lg<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-bit encoding, our encoding takes less space when $$m = o(\\lg {n})$$<\/jats:tex-math>\n \n m<\/mml:mi>\n =<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n lg<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In addition to the upper bound results for the encodings, we also give lower bounds on encodings for answering 1 and 4-sided $${\\textsf {Top}}{\\text {-}}k{}$$<\/jats:tex-math>\n \n Top<\/mml:mi>\n -<\/mml:mtext>\n k<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> queries, which show that our upper bound results are almost optimal.<\/jats:p>","DOI":"10.1007\/s00453-021-00856-1","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T11:02:48Z","timestamp":1627383768000},"page":"3379-3402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Encoding Two-Dimensional Range Top-k Queries"],"prefix":"10.1007","volume":"83","author":[{"given":"Seungbum","family":"Jo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Lingala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0636-9880","authenticated-orcid":false,"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,27]]},"reference":[{"issue":"2","key":"856_CR1","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput. 22(2), 221\u2013242 (1993)","journal-title":"SIAM J. Comput."},{"key":"856_CR2","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Brodnik, A., Davoodi, P.: The encoding complexity of two dimensional range minimum data structures. In: Algorithms\u2014ESA 2013\u201421st Annual European Symposium, Sophia Antipolis, France, September 2\u20134, 2013. Proceedings, pp. 229\u2013240 (2013)","DOI":"10.1007\/978-3-642-40450-4_20"},{"issue":"4","key":"856_CR3","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"GS Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica 63(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"key":"856_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Greve, M., L\u00f3pez-Ortiz, A.: Online sorted range reporting. In: ISAAC 2009, Proceedings, pp. 173\u2013182 (2009)","DOI":"10.1007\/978-3-642-10631-6_19"},{"key":"856_CR5","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2013.0131","author":"P Davoodi","year":"2014","unstructured":"Davoodi, P., Navarro, G., Raman, R., Rao, S.S.: Encoding range minima and range top-2 queries. Philos Trans R Soc Lond Math Phys Eng Sci (2014). https:\/\/doi.org\/10.1098\/rsta.2013.0131","journal-title":"Philos Trans R Soc Lond Math Phys Eng Sci"},{"issue":"1","key":"856_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s11786-009-0007-8","volume":"3","author":"J Fischer","year":"2010","unstructured":"Fischer, J., Heun, V.: Finding range minima in the middle: approximations and applications. Math. Comput. Sci. 3(1), 17\u201330 (2010)","journal-title":"Math. Comput. Sci."},{"issue":"2","key":"856_CR7","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1006\/inco.1993.1030","volume":"104","author":"GN Frederickson","year":"1993","unstructured":"Frederickson, G.N.: An optimal algorithm for selection in a min-heap. Inf. Comput. 104(2), 197\u2013214 (1993)","journal-title":"Inf. Comput."},{"key":"856_CR8","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Nicholson, P.K.: Encodings of range maximum-sum segment queries and applications. In: Combinatorial Pattern Matching\u201426th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29\u2013July 1, 2015, Proceedings, pp. 196\u2013206 (2015)","DOI":"10.1007\/978-3-319-19929-0_17"},{"key":"856_CR9","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Nicholson, P.K.: Optimal encodings for range top-k k , selection, and min-max. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 593\u2013604 (2015)","DOI":"10.1007\/978-3-662-47672-7_48"},{"key":"856_CR10","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1016\/j.tcs.2015.10.012","volume":"609","author":"MJ Golin","year":"2016","unstructured":"Golin, M.J., Iacono, J., Krizanc, D., Raman, R., Satti, S.R., Shende, S.M.: Encoding 2d range maximum queries. Theor. Comput. Sci. 609, 316\u2013327 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"856_CR11","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/3012939","volume":"13","author":"R Grossi","year":"2017","unstructured":"Grossi, R., Iacono, J., Navarro, G., Raman, R., Rao, S.S.: Asymptotically optimal encodings of range data structures for selection and top-k queries. ACM Trans. Algorithms 13(2), 28:1-28:31 (2017)","journal-title":"ACM Trans. Algorithms"},{"key":"856_CR12","first-page":"553","volume":"2013","author":"R Grossi","year":"2013","unstructured":"Grossi, R., Iacono, J., Navarro, G., Raman, R., Satti, S.R.: Encodings for range selection and top-k queries. ESA 2013, 553\u2013564 (2013)","journal-title":"ESA"},{"key":"856_CR13","doi-asserted-by":"crossref","unstructured":"He, M.: Succinct and implicit data structures for computational geometry. In: Space-Efficient Data Structures, Streams, and Algorithms\u2014Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pp. 216\u2013235 (2013)","DOI":"10.1007\/978-3-642-40273-9_15"},{"key":"856_CR14","unstructured":"Jo, S., Lingala, R., Satti, S.R.: Encoding two-dimensional range top-k queries. In: 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, June 27\u201329, 2016, Tel Aviv, Israel, pp. 3:1\u20133:11 (2016)"},{"key":"856_CR15","unstructured":"Jo, S., Satti, S.R.: Encoding two-dimensional range top-k queries revisited. In: 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16\u201319, 2018, Jiaoxi, Yilan, Taiwan, pp. 69:1\u201369:13 (2018)"},{"key":"856_CR16","doi-asserted-by":"publisher","DOI":"10.5948\/UPO9780883859223","volume-title":"Geometric Inequalities","author":"N Kazarinoff","year":"1961","unstructured":"Kazarinoff, N.: Geometric Inequalities. Random House, New York (1961)"},{"key":"856_CR17","unstructured":"Miltersen, P.B.: Cell probe complexity\u2014a survey. FSTTCS (1999)"},{"issue":"3","key":"856_CR18","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"856_CR19","doi-asserted-by":"crossref","unstructured":"Rahul, S., Tao, Y.: On top-k range reporting in 2d space. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31\u2013June 4, 2015, pp. 265\u2013275 (2015)","DOI":"10.1145\/2745754.2745777"},{"key":"856_CR20","doi-asserted-by":"crossref","unstructured":"Rahul, S., Tao, Y.: Efficient top-k indexing via general reductions. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26\u2013July 01, 2016, pp. 277\u2013288 (2016)","DOI":"10.1145\/2902251.2902290"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00856-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00856-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00856-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T12:03:50Z","timestamp":1635336230000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00856-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,27]]},"references-count":20,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["856"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00856-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,7,27]]},"assertion":[{"value":"24 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}