Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/39591
Title: Encoding Nearest Larger Values
Authors: Hoffmann, Michael
Iacono, John
Nicholson, Patrick K.
Raman, Rajeev
First Published: 8-Mar-2017
Publisher: Elsevier
Citation: Theoretical Computer Science, 2017, in press
Abstract: In nearest larger value (NLV) problems, we are given an array A[1..n] of distinct numbers, and need to preprocess A to answer queries of the following form: given any index i∈[1,n], return a “nearest” index j such that A[j]>A[i]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A[j]>A[i] and|j−i| is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is deleted after preprocessing. The NNLV encoding problem turns out to have an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Of particular interest is the tiebreaking rule: if there exist two nearest indices j1,j2 such that A[j1]>A[i] and A[j2]>A[i] and |j1−i|=|j2−i|, then which index should be returned? For the tiebreaking rule where the rightmost (i.e., largest) index is returned, we encode a path-compressed representation of the Cartesian tree that can answer all NNLV queries in 1.89997n+o(n) bits, and can answer queries inO(1) time. An alternative approach, based on forbidden patterns , achieves a very similar space bound for two tiebreaking rules (including the one where ties are broken to the right), and (for a more flexible tiebreaking rule) achieves 1.81211n+o(n) bits. Finally, we develop a fast method of counting distinguishable configurations for NNLV queries. Using this method, we prove a lower bound of 1.62309n−Θ(1) bits of space for NNLV encodings for the tiebreaking rule where the rightmost index is returned.
DOI Link: 10.1016/j.tcs.2017.02.017
ISSN: 0304-3975
Links: http://www.sciencedirect.com/science/article/pii/S0304397517301500
http://hdl.handle.net/2381/39591
Embargo on file until: 8-Mar-2019
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2017, Elsevier. Deposited with reference to the publisher’s open access archiving policy.
Description: The file associated with this record is under embargo until 24 months after publication, in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
submitted_version.pdfPost-review (final submitted author manuscript)674.55 kBAdobe PDFView/Open


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