(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
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 8 March 2021.
HTML page formatted Wed Oct 30 12:15:31 2024.
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