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
algorithms, data structures