All nearest smaller values

Last updated December 04, 2023

In computer science, the all nearest smaller values problem is the following task: for each position in a sequence of numbers, search among the previous positions for the last position that contains a smaller value. This problem can be solved efficiently both by parallel and non-parallel algorithms: Berkman, Schieber & Vishkin (1993), who first identified the procedure as a useful subroutine for other parallel programs, developed efficient algorithms to solve it in the Parallel Random Access Machine model; it may also be solved in linear time on a non-parallel computer using a stack-based algorithm. Later researchers have studied algorithms to solve it in other models of parallel computation.

Example

Suppose that the input is the binary van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

The first element of the sequence (0) has no previous value. The nearest (only) smaller value previous to 8 and to 4 is 0. All three values previous to 12 are smaller, but the nearest one is 4. Continuing in the same way, the nearest previous smaller values for this sequence (indicating the nonexistence of a previous smaller value by a dash) are

—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

In most applications, the positions of the nearest smaller values, and not the values themselves, should be computed, and in many applications the same computation should be computed for the reversal of the sequence in order to find the following smaller value that is closest in the sequence.

Applications

Berkman, Schieber & Vishkin (1993) mention many other problems that may be solved efficiently in parallel using a nearest smaller values computation. Among them, they include the following:

Merge algorithms, computing the merge step of a merge sort. The input to these algorithms consists of two sorted arrays of numbers; the desired output is the same set of numbers in a single sorted array. If one concatenates the two sorted arrays, the first in ascending order and the second in descending order, then the predecessor of each value in the output is either its closest previous smaller value or its closest following smaller value (whichever of the two is larger), and the position of each value in the sorted output array may easily be calculated from the positions of these two nearest smaller values.
Construction of Cartesian trees. A Cartesian tree is a data structure introduced by Vuillemin (1980) and further studied by Gabow, Bentley & Tarjan (1984) for range searching applications. Cartesian trees also arise in the definition of the treap and randomized binary search tree data structures for binary searching. The Cartesian tree of a sequence of values has a node for each value. The root of the tree is the minimum value of the sequence; for every other node, the parent of the node is either its closest previous smaller value or its closest following smaller value (whichever of the two exists and is larger). Thus, Cartesian trees may be constructed in linear time based on an all nearest smaller values algorithm.
Matching parentheses. If a sequence of open and close parenthesis characters is given as input, together with the nesting depth of each parenthesis, then the match to each open parenthesis is the next close parenthesis with no larger nesting depth, so it can be found by an all nearest smaller values computation that breaks ties in favor of close parentheses. If the nesting depths are not given, they can be calculated using a prefix sum computation.

Similar techniques may also be applied to problems of polygon triangulation, convex hull construction (parallelizing the sequential Graham scan convex hull algorithm), reconstruction of trees from two of the trees' traversal orderings, and quadtree construction.^[1]

Sequential algorithm

On a sequential computer, all nearest smaller values may be found by using a stack data structure: one processes the values in sequence order, using the stack to maintain a subsequence of the values that have been processed so far and are smaller than any later value that has already been processed. In pseudocode, the algorithm is as follows.

S = new empty stack data structure for x in the input sequence dowhile S is nonempty and the top element of S is greater than or equal to x do         pop S     if S is empty then         x has no preceding smaller value     else         the nearest smaller value to x is the top element of S     push x onto S

Despite having a nested loop structure, the running time of this algorithm is linear, because every iteration of the inner loop removes an item that had been added in some previous iteration of the outer loop. It is closely related to an algorithm of Knuth for sorting with a stack (for inputs that can be sorted in this way).^[2]

An even simpler linear-time sequential algorithm (Barbay, Fischer & Navarro (2012), Lemma 1) does not even need a stack; it assumes that the input sequence is given as an array A[1,n] of size n, and stores the index j of the preceding smaller value of the i^th value A[i] in P[i]. We assume an artificial overall minimum at A[0]:

for i from 1 to n:     j = i-1     while A[j] >= A[i]:         j = P[j]     P[i] = j

Parallel algorithms

Berkman, Schieber & Vishkin (1993) showed how to solve the all nearest smaller values problem efficiently on a concurrent-read concurrent-write Parallel Random Access Machine. For a sequence of n values, stored as an array, they use a doubly logarithmic tree to show that the problem may be solved in time O(log log n) using a linear amount of total work. For sequences where all values are integers in the interval [1,s], Berkman, Matias & Ragde (1998) improved this bound to O(log log log s); they also showed that, for sufficiently large values of s, the previous doubly logarithmic time bound is the best that can be achieved for the problem. Since this work, parallel algorithms for the all nearest smaller values problem have also been developed on other models of parallel computation, including parallel computers with a hypercube-structured communications network,^[3] and the bulk synchronous parallel model.^[4]

Notes

↑ Bern, Eppstein & Teng (1999).
↑ Knuth, Donald (1968), "Vol. 1: Fundamental Algorithms", The Art of Computer Programming , Reading, Mass.: Addison-Wesley.
↑ Kravets & Plaxton (1996).
↑ He & Huang (2001).

Related Research Articles

In parallel computer architectures, a systolic array is a homogeneous network of tightly coupled data processing units (DPUs) called cells or nodes. Each node or DPU independently computes a partial result as a function of the data received from its upstream neighbours, stores the result within itself and passes it downstream. Systolic arrays were first used in Colossus, which was an early computer used to break German Lorenz ciphers during World War II. Due to the classified nature of Colossus, they were independently invented or rediscovered by H. T. Kung and Charles Leiserson who described arrays for many dense linear algebra computations for banded matrices. Early applications include computing greatest common divisors of integers and polynomials. They are sometimes classified as multiple-instruction single-data (MISD) architectures under Flynn's taxonomy, but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: SISD, SIMD, MISD, MIMD, as discussed later in this article.

<span class="mw-page-title-main">Graham scan</span> Algorithm for computing convex hulls in a set of points

Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In computational complexity theory, the 3SUM problem asks if a given set of $real numbers contains three elements that sum to zero. A generalized version, k -SUM, asks the same question on k numbers. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation.$

In computer science, a selection algorithm is an algorithm for finding the $th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time .$

In computer science, a suffix tree is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.

In computer science, a parallel random-access machine is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM). In the same way that the RAM is used by sequential-algorithm designers to model algorithmic performance, the PRAM is used by parallel-algorithm designers to model parallel algorithmic performance. Similar to the way in which the RAM model neglects practical issues, such as access time to cache memory versus main memory, the PRAM model neglects such issues as synchronization and communication, but provides any (problem-size-dependent) number of processors. Algorithm cost, for instance, is estimated using two parameters O(time) and O(time × processor_number).

<span class="mw-page-title-main">Recursion (computer science)</span> Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As Anderson & Miller (1990) wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers $x 0, x 1, x 2, ...$ is a second sequence of numbers $y 0, y 1, y 2, ...$ , the sums of prefixes of the input sequence:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes $v$ and $w$ in a tree or directed acyclic graph (DAG) $T$ is the lowest node that has both $v$ and $w$ as descendants, where we define each node to be a descendant of itself.

In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.

In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.

<span class="mw-page-title-main">Range minimum query</span> Minimizing problem in computer programming

In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP).

In computer science, a doubly logarithmic tree is a tree where each internal node of height 1, the tree layer above the leaves, has two children, and each internal node of height $has children. Each child of the root contains leaves. The number of children at a node from each leaf to root is 0,2,2,4,16, 256, 65536, ...$

The Euler tour technique (ETT), named after Leonhard Euler, is a method in graph theory for representing trees. The tree is viewed as a directed graph that contains two directed edges for each edge in the tree. The tree can then be represented as a Eulerian circuit of the directed graph, known as the Euler tour representation (ETR) of the tree. The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory. It was introduced by Tarjan and Vishkin in 1984.

In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are.

In mathematics and computer science, a stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.

Pointer jumping or path doubling is a design technique for parallel algorithms that operate on pointer structures, such as linked lists and directed graphs. Pointer jumping allows an algorithm to follow paths with a time complexity that is logarithmic with respect to the length of the longest path. It does this by "jumping" to the end of the path computed by neighbors.

References

Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations", Theoretical Computer Science, 459: 26–41, arXiv: 1009.5863 , doi:10.1016/j.tcs.2012.08.010 .
Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998), "Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains", Journal of Algorithms, 28 (2): 197–215, doi:10.1006/jagm.1997.0905 .
Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms, 14 (3): 344–370, doi:10.1006/jagm.1993.1018 .
Bern, Marshall; Eppstein, David; Teng, Shang-Hua (1999), "Parallel construction of quadtrees and quality triangulations" (PDF), International Journal of Computational Geometry & Applications, World Scientific Publishing Company, 9 (6): 517–532, doi:10.1142/S0218195999000303 .
Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), "Scaling and related techniques for geometry problems", Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84, New York, NY, USA: ACM, pp. 135–143, doi:10.1145/800057.808675, ISBN 0-89791-133-4, S2CID 17752833 .
He, Xin; Huang, Chun-Hsi (2001), "Communication efficient BSP algorithm for all nearest smaller values", Journal of Parallel and Distributed Computing, 61 (10): 1425–1438, doi:10.1006/jpdc.2001.1741 .
Kravets, D.; Plaxton, C. G. (1996), "All nearest smaller values on the hypercube", IEEE Trans. Parallel and Distributed Systems, 7 (5): 456–462, doi:10.1109/71.503770 .
Vuillemin, Jean (1980), "A unifying look at data structures", Commun. ACM, New York, NY, USA: ACM, 23 (4): 229–239, doi: 10.1145/358841.358852 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Bern, Eppstein & Teng (1999).

[2] Knuth, Donald (1968), "Vol. 1: Fundamental Algorithms", The Art of Computer Programming , Reading, Mass.: Addison-Wesley.

[3] Kravets & Plaxton (1996).

[4] He & Huang (2001).

[1]

[2]

[3]

[4]