The predecessor problem is a fundamental and well-studied data structure problem, both from the perspective of upper bounds [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]} and lower bounds [11]}, [7]}, [13]}, [14]}, [15]}, [1]}, [17]}. The problem has many applications, for instance integer sorting [6]}, [19]}, [5]}, [21]}, string sorting [22]}, [23]}, [24]}, and string searching [25]}, [9]}, [27]}, [28]}, [29]}. See Navarro and Rojas-Ledesma [30]} for a recent survey.
