Treffer: The All Nearest Smaller Values Problem Revisited in Practice, Parallel and External Memory

We present a thorough investigation of the All Nearest Smaller Values (ANSV) problem from a practical perspective. The ANSV problem is defined as follows: given an array A consisting of n values, for each entry Ai compute the largest index l < i and the smallest index r > i such that Ai > Al and Ai > Ar, i.e., the indices of the nearest smaller values to the left and to the right of Ai. The ANSV problem was solved by Berkman, Schieber, and Vishkin [J. Algorithms, 1993] in the PRAM model. Their solution in the CREW PRAM model, which we will refer to as the BSV algorithm, achieves optimal O (n) work and O(log n) span. Until now, the BSV algorithm has been perceived as too complicated for practical use, and we are not aware of any publicly available implementations. Instead, the best existing practical solution to the ANSV problem is the implementation by Shun and Zhao presented at DCC'13. They implemented a simpler O(n log n)-work algorithm with an additional heuristic first proposed by Blelloch and Shun at ALENEX'11. We refer to this implementation as the BSZ algorithm. In this paper, we implement the original BSV algorithm and demonstrate its practical efficiency. Despite its perceived complexity, our results show that its performance is comparable to the BSZ algorithm. We also present the first theoretical analysis of the heuristic implemented in the BSZ algorithm and show that it provides a tunable trade-off between optimal work and optimal span. In particular, we show that it achieves O (Formula presented) span, for any integer parameter 1 ≤ k ≤ n. Thus, for k = Θ (log n), the BSZ algorithm can be made to be work-optimal, albeit at the expense of increased span compared to BSV. Our discussion includes a detailed examination of different input types, particularly highlighting that for random inputs, the low expected distance between values and their nearest smaller values renders simple algorithms efficient. Finally, we analyze the input/output (I/Oxspace) complexities of the BSV algorithm.