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 10 January 2007.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "oblivious algorithm", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 January 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/obliviousAlgorithm.html