Continuing Innovation in Information Technology (2012)
Chapter: Appendix C: Examples of Impacts from Algorithms Research
Examples of Impacts from Algorithms Research
Research in theory and algorithms (see Box 1, “Research in the Theoretical and Algorithmic Foundations of Computing”) has provided an important foundation for the advances depicted in Figure 1. Shown in Table C.1 are some of the many examples of research advances in algorithms that have helped lead to substantial economic impact.
TABLE C.1 Algorithms Research—Some Examples of Impacts
|
|
||
|
Research Topic |
Origins |
Impact |
|
|
||
|
Algorithms for network congestion |
Universities in the mid-1990s |
A key building block for today’s networking technologies, such as content-distribution networks |
|
CPLEX |
Universities pre-1985, later work in industry and start-ups (e.g., ILOG, IBM, and others) |
A foundation for a wide array of practical optimization and resource-allocation problems and for logistics, delivery systems, and so on |
|
Turbo codes |
Decades of university and industry research, reduced to practical form at Telecom-Bretagne in 1993 |
Absolutely essential in digital communications, and in particular in wireless networking technologies today |
|
Eigenvalues, PageRank, and so on |
Decades of university research; PageRank emerged out of Stanford in 1998 |
PageRank the core of Google search; today, related concepts still fundamental |
|
Distributed hash tables |
Universities and industry, with practical algorithms available by 2001 |
A core element of today’s peer-to-peer systems; also a strong influence on university and industry R&D |
|
VCG auction mechanism |
University research, emerging in 2000 |
A major impact on online advertising in the major search engines |
|
N-gram matching for natural language processing |
University and industry research, emerging as practical around 2004 |
The core of today’s language-processing and translation systems |
|
|
||
