Please use this identifier to cite or link to this item:
Title: Encoding range minima and range top-2 queries
Authors: Davoodi, Pooya
Navarro, Gonzalo
Raman, Rajeev
Rao, S. Srinivasa
First Published: 21-Apr-2014
Publisher: The Royal Society
Citation: Philosophical Transactions of the Royal Society A : Mathematical, Physical and Engineering Sciences, 2014, 372, 20130131
Abstract: We consider the problem of encoding range minimum queries (RMQs): given an array A[1..n] of distinct totally ordered values, to pre-process A and create a data structure that can answer the query RMQ(i,j), which returns the index containing the smallest element in A[i..j], without access to the array A at query time. We give a data structure whose space usage is 2n+o(n) bits, which is asymptotically optimal for worst-case data, and answers RMQs in O(1) worst-case time. This matches the previous result of Fischer and Heun, but is obtained in a more natural way. Furthermore, our result can encode the RMQs of a random array A in 1.919n+o(n) bits in expectation, which is not known to hold for Fischer and Heun’s result. We then generalize our result to the encoding range top-2 query (RT2Q) problem, which is like the encoding RMQ problem except that the query RT2Q(i,j) returns the indices of both the smallest and second smallest elements of A[i..j]. We introduce a data structure using 3.272n+o(n) bits that answers RT2Qs in constant time, and also give lower bounds on the effective entropy of the RT2Q problem.
DOI Link: 10.1098/rsta.2013.0131
ISSN: 1364-503X
eISSN: 1471-2962
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2014 The Author(s) Published by the Royal Society. All rights reserved. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper.pdfPost-review (final submitted)363.27 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.