Appendix C

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




The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement



Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page 32
Appendix C 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 A foundation for a wide array of industry and start-ups (e.g., ILOG, practical optimization and resource- IBM, and others) allocation problems and for logistics, delivery systems, and so on Turbo codes Decades of university and industry Absolutely essential in digital research, reduced to practical form communications, and in particular in at Telecom-Bretagne in 1993 wireless networking technologies today Eigenvalues, PageRank, and so on Decades of university research; PageRank the core of Google PageRank emerged out of Stanford search; today, related concepts still in 1998 fundamental Distributed hash tables Universities and industry, with A core element of today’s peer-to-peer practical algorithms available by systems; also a strong influence on 2001 university and industry R&D VCG auction mechanism University research, emerging in A major impact on online advertising in 2000 the major search engines N-gram matching for natural University and industry research, The core of today’s language-processing language processing emerging as practical around 2004 and translation systems 32