2015 | OriginalPaper | Buchkapitel
Compact Encodings and Indexes for the Nearest Larger Neighbor Problem
Autoren: Seungbum Jo, Rajeev Raman, Srinivasa Rao Satti
Verlag: Springer International Publishing
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
L
1
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
(
n
2
)-bit encoding that answers
NLV
queries in
O
(1) time. When
A
is a binary array, we describe a simpler
O
(
n
2
)-bit encoding that also supports
NLV
queries in
O
(1) time. Using this, we obtain an index of size
O
(
n
2
/
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
) log
c
) 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.
