Compact Encodings and Indexes for the Nearest Larger Neighbor Problem

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.