National Academies Press: OpenBook

Continuing Innovation in Information Technology (2012)

Chapter: Appendix C: Examples of Impacts from Algorithms Research

« Previous: Appendix B: Transfers of Ideas and People and Impacts Since 2003 Added to Figure 1
Suggested Citation:"Appendix C: Examples of Impacts from Algorithms Research." National Research Council. 2012. Continuing Innovation in Information Technology. Washington, DC: The National Academies Press. doi: 10.17226/13427.

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



Algorithms for network congestion

Universities in the mid-1990s

A key building block for today’s networking technologies, such as content-distribution networks


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

Suggested Citation:"Appendix C: Examples of Impacts from Algorithms Research." National Research Council. 2012. Continuing Innovation in Information Technology. Washington, DC: The National Academies Press. doi: 10.17226/13427.
Page 32
Continuing Innovation in Information Technology Get This Book
 Continuing Innovation in Information Technology
Buy Paperback | $27.00 Buy Ebook | $21.99
MyNAP members save 10% online.
Login or Register to save!
Download Free PDF

Information technology (IT) is widely understood to be the enabling technology of the 21st century. IT has transformed, and continues to transform, all aspects of our lives: commerce and finance, education, employment, energy, health care, manufacturing, government, national security, transportation, communications, entertainment, science, and engineering. IT and its impact on the U.S. economy-both directly (the IT sector itself) and indirectly (other sectors that are powered by advances in IT)—continue to grow in size and importance.

In 1995, the National Research Council's Computer Science and Telecommunications Board (CSTB) produced the report Evolving the High Performance Computing and Communications Initiative to Support the Nation's Information Infrastructure. A graphic in that report, often called the "tire tracks" diagram because of its appearance, produced an extraordinary response by clearly linking government investments in academic and industry research to the ultimate creation of new information technology industries with more than $1 billion in annual revenue.

Used in presentations to Congress and executive branch decision makers and discussed broadly in the research and innovation policy communities, the tire tracks figure dispelled the assumption that the commercially successful IT industry is self-sufficient, underscoring through long incubation periods of years and even decades. The figure was updated in 2002, 2003, and 2009 reports produced by the CSTB. With the support of the National Science Foundation, CSTB updated the tire tracks figure. Continuing Innovation in Information Technology includes the updated figure and a brief text based in large part on prior CSTB reports.


  1. ×

    Welcome to OpenBook!

    You're looking at OpenBook,'s online reading room since 1999. Based on feedback from you, our users, we've made some improvements that make it easier than ever to read thousands of publications on our website.

    Do you want to take a quick tour of the OpenBook's features?

    No Thanks Take a Tour »
  2. ×

    Show this book's table of contents, where you can jump to any chapter by name.

    « Back Next »
  3. ×

    ...or use these buttons to go back to the previous chapter or skip to the next one.

    « Back Next »
  4. ×

    Jump up to the previous page or down to the next one. Also, you can type in a page number and press Enter to go directly to that page in the book.

    « Back Next »
  5. ×

    Switch between the Original Pages, where you can read the report as it appeared in print, and Text Pages for the web version, where you can highlight and search the text.

    « Back Next »
  6. ×

    To search the entire text of this book, type in your search term here and press Enter.

    « Back Next »
  7. ×

    Share a link to this book page on your preferred social network or via email.

    « Back Next »
  8. ×

    View our suggested citation for this chapter.

    « Back Next »
  9. ×

    Ready to take your reading offline? Click here to buy this book in print or download it as a free PDF, if available.

    « Back Next »
Stay Connected!