{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:30Z","timestamp":1740142770620,"version":"3.37.3"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2020R1G1A1101477"],"award-info":[{"award-number":["NRF-2020R1G1A1101477"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,11,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We design a practical variant of an encoding for range Top-2 query (RT2Q) and evaluate its performance. Given an array $A[1,n]$ of $n$ elements from a total order, the range Top-2 encoding problem is to construct a data structure that answers ${\\textsf{RT2Q}}{}$, which returns the positions of the first and second largest elements within a given range of $A$, without accessing the array $A$ at query time. We design the following two implementations: (i) an implementation based on an alternative representation of Davoodi et al.\u2019s [Phil. Trans. Royal Soc. A, 2016] data structure, which supports queries efficiently. Experimental results show that our implementation is efficient in practice and gives improved time-space trade-offs compared with the indexing data structures (which keep the original array $A$ as part of the data structure) for range maximum queries. (ii) Another implementation based on Jo et al.\u2019s ${\\textsf{RT2Q}}{}$ encoding on $2 \\times n$ array [CPM, 2016], which can be constructed in $O(n)$ time. We compare our encoding with Gawrychowski and Nicholson\u2019s optimal encoding [ICALP, 2015] and show that in most cases, our encoding shows faster construction time while using a competitive space in practice.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac122","type":"journal-article","created":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T15:58:11Z","timestamp":1662998291000},"page":"2794-2809","source":"Crossref","is-referenced-by-count":0,"title":["Practical Implementation of Encoding Range Top-2 Queries"],"prefix":"10.1093","volume":"66","author":[{"given":"Wooyoung","family":"Park","sequence":"first","affiliation":[{"name":"Dep. of Computer Science and Engineering, Seoul National University , Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seungbum","family":"Jo","sequence":"additional","affiliation":[{"name":"The Division of Computer Convergence, Chungnam National University , Daejeon, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasa","family":"Rao Satti","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, Norwegian University of Science and Technology , Trondheim, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,9,10]]},"reference":[{"key":"2023111618464142300_ref1","first-page":"12:1","article-title":"Practical range minimum queries revisited","volume":"190","author":"Baumstark","year":"2017","journal-title":"SEA"},{"key":"2023111618464142300_ref2","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.jda.2016.09.002","article-title":"Improved range minimum queries","volume":"43","author":"Ferrada","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"2023111618464142300_ref3","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","article-title":"Space-efficient preprocessing schemes for range minimum queries on static arrays","volume":"40","author":"Fischer","journal-title":"SIAM J. Comput"},{"key":"2023111618464142300_ref4","first-page":"1","article-title":"Encoding data structures","author":"Raman","year":"2015","journal-title":"WALCOM"},{"first-page":"553","volume-title":"ESA 2013","author":"Grossi","key":"2023111618464142300_ref5"},{"key":"2023111618464142300_ref6","first-page":"28:1","article-title":"Asymptotically optimal encodings of range data structures for selection and top-k queries","volume":"13","author":"Grossi","journal-title":"ACM Trans. Algorithms"},{"key":"2023111618464142300_ref7","first-page":"11:1","article-title":"A survey of top-k query processing techniques in relational database systems","volume":"40","author":"Ilyas","journal-title":"ACM Comput. Surv"},{"key":"2023111618464142300_ref8","article-title":"Encoding range minima and range top-2 queries","volume":"372","author":"Davoodi","journal-title":"Philos. Trans. R. Soc A"},{"first-page":"593","volume-title":"ICALP 2015, Proceedings, Part I","author":"Gawrychowski","key":"2023111618464142300_ref9"},{"key":"2023111618464142300_ref10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/358841.358852","article-title":"A unifying look at data structures","volume":"23","author":"Vuillemin","journal-title":"Commun. ACM"},{"key":"2023111618464142300_ref11","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/s00453-012-9664-0","article-title":"A uniform paradigm to succinctly encode various families of trees","volume":"68","author":"Farzan","journal-title":"Algorithmica"},{"key":"2023111618464142300_ref12","first-page":"84","article-title":"Succinct trees in practice","author":"Arroyuelo","year":"2010","journal-title":"Proceedings of ALENEX"},{"key":"2023111618464142300_ref13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","article-title":"Representing trees of higher degree","volume":"43","author":"Benoit","journal-title":"Algorithmica"},{"key":"2023111618464142300_ref14","doi-asserted-by":"crossref","first-page":"3379","DOI":"10.1007\/s00453-021-00856-1","article-title":"Encoding two-dimensional range top-k queries","volume":"83","author":"Jo","journal-title":"Algorithmica"},{"key":"2023111618464142300_ref15","first-page":"135","article-title":"Scaling and related techniques for geometry problems","author":"Gabow","year":"1984","journal-title":"Proc, STOC"},{"key":"2023111618464142300_ref16","first-page":"549","article-title":"Space-efficient static trees and graphs","author":"Jacobson","year":"1989","journal-title":"FOCS"},{"key":"2023111618464142300_ref17","first-page":"16:1","article-title":"Fully functional static and dynamic succinct trees","volume":"10","author":"Navarro","journal-title":"ACM Trans. Algorithms"},{"key":"2023111618464142300_ref18","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed suffix trees with full functionality","volume":"41","author":"Sadakane","journal-title":"Theory Comput. Syst."},{"key":"2023111618464142300_ref19","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","article-title":"Ultra-succinct representation of ordered trees with applications","volume":"78","author":"Jansson","journal-title":"J. Comput. Syst. Sci."},{"key":"2023111618464142300_ref20","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets","volume":"3","author":"Raman","journal-title":"ACM Trans. Algorithms"},{"key":"2023111618464142300_ref21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1151","article-title":"Space efficient suffix trees","volume":"39","author":"Munro","journal-title":"J. Algorithms"},{"key":"2023111618464142300_ref22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s11786-017-0294-4","article-title":"On succinct representations of binary trees","volume":"11","author":"Davoodi","journal-title":"Math. Comput. Sci."},{"first-page":"326","volume-title":"13th International Symposium on Experimental Algorithms, (SEA 2014)","author":"Gog","key":"2023111618464142300_ref23"},{"key":"2023111618464142300_ref24","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/rsa.3240050205","article-title":"On random Cartesian trees","volume":"5","author":"Devroye","journal-title":"Random Struct. Algorithms"},{"key":"2023111618464142300_ref25","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","article-title":"A technique for high-performance data compression","volume":"17","author":"Welch","journal-title":"Computer"},{"first-page":"10:1","volume-title":"19th International Symposium on Experimental Algorithms, SEA 2021, June 7\u20139, 2021, Nice, France","author":"Jo","key":"2023111618464142300_ref26"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/11\/2794\/53401040\/bxac122.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/11\/2794\/53401040\/bxac122.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,16]],"date-time":"2023-11-16T18:47:24Z","timestamp":1700160444000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/11\/2794\/6695274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,10]]},"references-count":26,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2022,9,10]]},"published-print":{"date-parts":[[2023,11,14]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac122","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,11]]},"published":{"date-parts":[[2022,9,10]]}}}