Please use this identifier to cite or link to this item:
Title: Space Efficient Data Structures for Nearest Larger Neighbor
Authors: Jayapaul, V.
Jo, S.
Raman, V.
Raman, Rajeev
Rao, S. R.
First Published: 13-Jan-2016
Publisher: Elsevier
Citation: Journal of Discrete Algorithms 2016, 36, pp. 63–75
Abstract: Given a sequence of n elements from a totally ordered set, and a position in the sequence, the nearest larger neighbor (NLN) query returns the position of the element which is closest to the query position, and is larger than the element at the query position. The problem of finding all nearest larger neighbors has attracted interest due to its applications for parenthesis matching and in computational geometry [1, 2, 3]. We consider a data structure version of this problem, which is to preprocess a given sequence of elements to construct a data structure that can answer NLN queries efficiently. We consider time-space tradeoffs for the problem in both the encoding (where the input is not accessible after the data structure has been created) and indexing model, and consider cases when the input is in a one dimensional array, and also initiate the study of this problem on two-dimensional arrays.
DOI Link: 10.1016/j.jda.2016.01.001
ISSN: 1570-8667
eISSN: 1570-8675
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: © 2015, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
NLN_Latest.pdfPre-review (submitted draft)282.24 kBAdobe PDFView/Open

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