Black, P.
(2012),
The New Golden Age of Algorithms and Data Structures
(Accessed April 19, 2024)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
The New Golden Age of Algorithms and Data Structures
Published
Author(s)
Abstract
Before 1976 Communications of the ACM printed (and numbered!) new algorithms every issue. Quicksort was invented in 1960, Boyer-Moore string search in 1977, and combsort in 1980. I haven't seen a new, general sorting algorithm in over a decade. The latest "general" data structure is the skip list, which was invented in 1990. Have all the basic, general algorithms and data structures been invented? We don't think so. With isochronous computing, heterogeneous multiprocessors, energy aware computing, wear-leveling (flash), cache and other anisotropic memory, distributed computing, streaming environments, functional languages, etc. there is a great need for research into new fundamental algorithms and data structures. As examples, we take the bulk of the time to present four which are novel and useful: reservoir sampling, majority on a stream, B-heap, and compacting and array in O(log n) time.Pub Type
Talks
Keywords
algorithms, data structures
Citation
Created October 29, 2012, Updated February 19, 2017