Abstract
Given a d-dimensional array, for any integer d > 0, the nearest larger value (NLV) query returns the position of the element which is closest, in L1 distance, to the query position, and is larger than the element at the query position. We consider the problem of preprocessing a given array, to construct a data structure that can answer NLV queries efficiently. In the 2-D case, given an n ×n array A, we give an asymptotically optimal O(n2)-bit encoding that answers NLV queries in O(1) time. When A is a binary array, we describe a simpler O(n2)-bit encoding that also supports NLV queries in O(1) time. Using this, we obtain an index of size O(n2/c) bits that supports NLV queries in O(c) time, for any parameter c, where 1 ≤ c ≤ n, matching the lower bound. For the 1-D case we consider the nearest larger right value (NLRV) problem where the nearest larger value to the right is sought. For an array of length n, we obtain an index that takes O((n/c) logc) bits, and supports NLRV queries in O(c) time, for any any parameter c, where 1 ≤ c ≤ n, improving the earlier results of Fischer et al. and Jayapaul et al.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asano, T., Bereg, S., Kirkpatrick, D.: Finding nearest larger neighbors. In: Albers, S., Alt, H., Näher, S. (eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 249–260. Springer, Heidelberg (2009)
Asano, T., Kirkpatrick, D.: Time-space tradeoffs for all-nearest-larger-neighbors problems. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 61–72. Springer, Heidelberg (2013)
Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344–370 (1993)
Brodal, G.S., Brodnik, A., Davoodi, P.: The encoding complexity of two dimensional range minimum data structures. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 229–240. Springer, Heidelberg (2013)
Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Srinivasa Rao, S.: Two dimensional range minimum queries and fibonacci lattices. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 217–228. Springer, Heidelberg (2012)
Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica 63(4), 815–830 (2012)
Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. Algorithmica 68(3), 610–625 (2014)
Ferragina, P., Manzini, G., Mäkinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms 3(2) (2007)
Fischer, J.: Combined data structure for previous- and next-smaller-values. Theor. Comput. Sci. 412(22), 2451–2456 (2011)
Fischer, J., Mäkinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theor. Comput. Sci. 410(51), 5354–5364 (2009)
Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549–554. IEEE Computer Society (1989)
Jayapaul, V., Jo, S., Raman, V., Satti, S.R.: Space efficient data structures for nearest larger neighbor. In: Proc. IWOCA 2014 (to appear, 2014)
Okanohara, D., Sadakane, K.: Practical entropy-compressed rank/select dictionary. In: ALENEX (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Jo, S., Raman, R., Rao Satti, S. (2015). Compact Encodings and Indexes for the Nearest Larger Neighbor Problem. In: Rahman, M.S., Tomita, E. (eds) WALCOM: Algorithms and Computation. WALCOM 2015. Lecture Notes in Computer Science, vol 8973. Springer, Cham. https://doi.org/10.1007/978-3-319-15612-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-15612-5_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15611-8
Online ISBN: 978-3-319-15612-5
eBook Packages: Computer ScienceComputer Science (R0)