Encoding 2D range maximum queries

详细信息    查看全文

• 作者：Mordecai Golin^a ; ^{golin@cse.ust.hk" class="auth_mail" title="E-mail the corresponding author} ; John Iacono^b ; ¹ ; ^{jiacono@poly.edu" class="auth_mail" title="E-mail the corresponding author} ; Danny Krizanc^c ; ^{dkrizanc@wesleyan.edu" class="auth_mail" title="E-mail the corresponding author} ; Rajeev Raman^d ; ² ; ^{rr29@mcs.le.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Srinivasa Rao Satti^e ; ³ ; ^{ssrao@cse.snu.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Sunil Shende^f ; ^{shende@camden.rutgers.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Range maximum queries ; Cartesian trees ; Effective entropy ; Indexing model ; Encoding model
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P2
• 页码：316-327
• 全文大小：440 K

文摘

We consider the two-dimensional range maximum query (2D-RMQ) problem: given an array containing elements from an ordered set, encode the array so that the position of the maximum element in any specified range of rows and range of columns can be found efficiently. We focus on determining the effective entropy of 2D-RMQ, i.e., how many bits are needed to encode an array so that 2D-RMQ queries can be answered without accessing the array. We give tight upper and lower bounds on the expected effective entropy for the case when A contains independent identically-distributed random values, and give new upper and lower bounds for the case when the array contains few rows. The latter results improve upon the upper and lower bounds by Brodal et al. [4]. We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.