NIST

oblivious algorithm

(definition)

Definition: An algorithm whose behavior, by design, is independent of some property that influences a typical algorithm for the same problem.

Generalization (I am a kind of ...)
algorithm.

Specialization (... is a kind of me.)
bitonic sort.

Note: For example, an oblivious sort algorithm always makes the same comparisons, regardless of the input. This is useful for external sorts, since there is a fixed I/O schedule, or parallel algorithms, like bitonic sort.

Other types of oblivious algorithms are cache oblivious, which are not dependent on hardware parameters like cache size and cache-line length, and oblivious routing, which route packets independent of the network topology, the history of traffic flow, or the congestion.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 8 March 2021.
HTML page formatted Mon Mar 8 10:01:45 2021.

Cite this as:
Paul E. Black, "oblivious algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 8 March 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/obliviousAlgorithm.html