Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
NIST Authors in Bold
|Author(s):||Paul E. Black;|
|Title:||The New Golden Age of Algorithms and Data Structures|
|Published:||October 29, 2012|
|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.|
|Keywords:||algorithms, data structures|
|Research Areas:||Information Technology|