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 1
Computer Science: Reflections on the Field, Reflections from the Field Prelude Emily Shops at VirtualEmporia.com Just a decade ago, the Internet was the domain of specialists and technology aficionados, requiring knowledge of file systems, format compatibilities, and operating system commands. Even the more user-friendly systems such as e-mail and net news principally served relatively small communities of technically savvy people. Until recently, the Internet, the World Wide Web, and e-commerce all would have seemed akin to magic to all but the most tech-savvy. Yet despite today’s widespread acceptance of and familiarity with computer capabilities, the details of how commonly used computer systems work remains a mystery for non-specialists. It is not magic, of course, that is at work. Nor did today’s system arise as a result of a direct evolution of previous technology. Like many radical innovations, e-commerce, for one, was not planned or even anticipated by those involved in either research or commerce. Rather, it evolved from a series of technical results that were pursued with other motivations—such as sharing computer resources or scientific information among researchers. Examining the scientific roots of e-commerce shows how research pursued for its own sake can enable important, often unanticipated capabilities. We take as our example a hypothetical online retailer, VirtualEmporia.com, and reveal some of the magic—that is, the research foundations—behind the nowsimple operation of ordering a book online. Thus it is possible to identify some of the computer science (CS) research that enables retailing online and to provide pointers to discussions of that research later in this volume. Also noted are some of the ways that a virtual store can provide an intellectual boost over a conventional store through its capabilities for searching and indexing, exchanging information among customers, and providing an enormous catalog of items.
OCR for page 2
Computer Science: Reflections on the Field, Reflections from the Field Emily is planning to take a trip next week and she’s looking for something to read on the airplane. In the past, she would have gone to a bookstore during business hours and browsed through the shelves to select a book from the limited stock at hand. Today, Emily has the option of sitting down at a computer, at any time of the day or night, to select and buy a book or many other types of products. Although shopping online is now a routine experience for millions, its familiarity and simplicity mask the sophisticated events behind the scenes. Indeed, what Emily does in the next 5 minutes would have been impossible without many discoveries and inventions from computer science. Emily’s Computer Emily’s family, like more than half of the households in the United States, owns a personal computer and related software. Her garden-variety home PC, available for roughly $600, is able to run much more sophisticated programs—and run them much faster—than the first computer her employer bought only 20 years ago. Indeed, the very idea of a home computer, outside the professional or aficionado market, is only about 20 years old. If Emily were to pause and consider the functionality available to her, she might marvel that no other machine is as flexible, general-purpose, or malleable as a computer. The idea that machines can be adapted to completely new situations for which they were not originally designed usually borders on the farcical. Emily’s pencil will not also serve as a stapler if the need arises. Computers, though, are The cost of computing power has decreased dramatically. A typical 2003 home PC, which had a 2.66 GHz system clock, 256 Mb of RAM, and a 40 Gb hard drive, outperformed the IBM/XT PC, released in 1983, which had a 4.77 MHz system clock, 640 Kb of RAM, and a 10 Mb hard drive, by a factor of roughly 500—at one-tenth the cost. Hill (in Chapter 2) describes the phenomenon of exponential growth in computing power, and he shows how computer science research strives to design computers that sustain this remarkable rate of improvement in the cost/performance ratio of computers. Emily’s computer and software are remarkable not only for their low cost but also for their high complexity. The hardware comprises billions of transistors, and the software installed on the computer is defined by tens of millions of lines of code; hundreds of millions of lines of additional software is available. The capability of the computer is built up from these tiny elements. Shaw (in Chapter 4) describes how abstraction hides the complex and oftenmessy details of a piece of hardware or software in favor of a simpler, more focused view of the aspects of immediate
OCR for page 3
Computer Science: Reflections on the Field, Reflections from the Field universal symbol manipulators covering the entire gamut of information processing. The right software transforms a computer from a Web browser to a home accountant to a photo editor to a jukebox to a mailbox to a game, virtually at your whim. Although Emily’s computer arrived at her home with a large amount of software pre-installed (including the Web browser that Emily uses to shop at VirtualEmporia.com), it can also run tens of thousands of additional programs. Of course, Emily will actually use only a small fraction of those programs, but she has enormous variety to choose from. These programs potentially enable Emily to use her computer for many different tasks, ranging from applications inconceivable before we had computers—such as e-mail, online messenger services, or chat rooms—to computer-based enhancements to more traditional tasks like creating and typesetting documents, organizing a business, or tracking investments. relevance. This makes it possible to build enormously complex systems out of a tower of abstractions, one layer at a time. Systematic research on algorithms and data structures was also necessary to build such complex software and hardware systems. Nothing else—aside from a person—is a universal machine that can be taught or programmed to accomplish a very wide range of new tasks. Kleinberg and Papadimitriou (in Chapter 2) show how the idea of universality rests on the notion of the universal Turing machine and the Church-Turing hypothesis about the universality of computers. The capabilities of Emily’s computer can be improved as current programs are improved, and even not-yet-conceived capabilities can be added as new programs are written. Software tools—programs that manipulate and transform other programs—make it possible to create new applications. The most important of these tools are the programming languages that provide the grammar, syntax, and semantics programmers use to convey their ideas to computers. A wide range of programming languages and tools are available today and new languages and tools are the subject of computer science research. See Aho and Larus in Chapter 4. Human-computer interaction research has led to improved user interfaces that make it easier for people to work with this software. Foley (in Chapter 8) discusses how research on user interfaces made spreadsheet software easier to use. Ullman (in Chapter 8) describes the computer science research that led to today’s word processors. Foley (in Chapter 8) describes how a variety of CS research results made possible another kind of computer program, the spreadsheet.
OCR for page 4
Computer Science: Reflections on the Field, Reflections from the Field Visiting VirtualEmporia.com Equally remarkably, Emily’s computer is easily connected to the Internet. This allows her to obtain information from billions of Web pages, communicate with others using e-mail or chat programs, or use a myriad of other Internet-delivered services. Once she is online and has opened a Web browser, she can visit VirtualEmporia.com simply by typing “http://www.VirtualEmporia.com” or selecting a bookmark. Her computer translates the name of the destination site into an Internet address and sends a message across the Internet to VirtualEmporia, asking for a Web page, which contains links to the rest of VirtualEmporia’s network. The Internet, which made data exchange among distant computers fast, easy, and commonplace, marked a striking change in the use of computers. The Internet also represented a striking change in how communications networks were designed. The Internet is a distributed, fault-tolerant system for communicating among computers. Its design specifies very little about the form or content of data—that aspect is left to the applications and systems enabled by the Internet’s packet-data-transport mechanisms (see Peterson and Clark in Chapter 7). With few changes to its design or implementation, the Internet grew from approximately 300,000 interconnected machines (hosts) in 1990 to over 170 million hosts in 2003.1 Although the Internet was originally constructed to allow researchers to share data and remotely access expensive computers, users of the early Internet quickly made e-mail the most popular application, and it remains the most common use of the Internet today. Today, the Internet is opening up many new avenues for communication among people (see Bruckman in Chapter 7). The Internet’s success derives in large part from the fact that it provides effective abstractions to enable computers throughout the world to find each other and exchange data. Here, Emily’s browser and VirtualEmporia.com’s Web site use a communication protocol called http that is built on top of the Internet. The World Wide Web, another of the many uses of the Internet, owes its origins in part to earlier computer science research on hypertext, which provides a way of navigating among linked documents. 1 Internet Systems Consortium (ISC), 2004, “Internet Domain Survey,” ISC, Redwood City, Calif., January. Available online at http://www.isc.org/ds/.
OCR for page 5
Computer Science: Reflections on the Field, Reflections from the Field Shopping When Emily visits VirtualEmporia.com’s Web site, VirtualEmporia.com recognizes Emily as an established customer. It retrieves her records and produces a customized home page, based on her past shopping habits, that suggests a few items she might want to buy. As she navigates through the site, the pages she views are also customized. VirtualEmporia.com suggests new books that might interest her, based on previous items she has purchased or searched for. In addition, when she looks at items or adds them to her shopping cart, VirtualEmporia shows her more items that customers with similar shopping interests have selected. Research on collaborative filtering led to machine-learning algorithms that correlate a new shopper’s interests with those of other shoppers in the database, so that data from the entire shopping community can be used to learn Emily’s likely interests. Mitchell (in Chapter 6) discusses some other applications of machine learning. Emily can also refine her choices by reading reviews on the VirtualEmporia site, including reviews published by recognized critics and comments from other customers—which she takes more or less seriously depending on the credibility ratings these comments have accumulated. Emily can browse through the items for sale or search the database of available products. Emily first enters a search request by author’s name. She receives a response in a second or less, even though VirtualEmporia’s database contains information about millions of books and other items for sale, has tens of millions of registered customers, and may Computer science research on reputation systems allows VirtualEmporia to provide some indications of how much trust one should place in opinions contributed by strangers. Like many modern organizations such as airlines, banks, and governments, VirtualEmporia could not exist in its current form without database systems. Gray (in Chapter 5) describes the research that led to the relational model for databases and modern database systems. Building on this discovery, computer scientists have developed a rich collection of representations and algorithms for manipulating data; this makes it feasible to store, index, search, update, and sort billions of records in reasonable amounts
OCR for page 6
Computer Science: Reflections on the Field, Reflections from the Field receive queries from hundreds of users each second. Emily does not find the book (she doesn’t quite remember the author’s name), but she does remember the name of a character in the book, which she uses in a full-content search to locate the desired book. The online setting enables business partnerships that were previously difficult or impossible. VirtualEmporia also allows Emily to consider offerings from multiple booksellers, including not only a large seller who can provide almost all books currently in print, but also numerous used-book sellers, both companies and individuals. When Emily searches for a book, she not only gets information about how to order that book and other editions of that book but also the opportunity to buy a used copy from the many booksellers and individuals who list books at VirtualEmporia. of time, and to ensure their integrity in the face of overlapping queries and updates. The ability to store and rapidly process such enormous and growing volumes of information also depends on work leading to the ever-increasing performance of computers (see Hill in Chapter 2). Paying for the Book After some browsing and searching, Emily finds the books she wants and goes to the checkout page, which asks for a credit card number. Emily’s credit card information is automatically encrypted by her Web browser before it is sent over the Internet, making it harder for an unauthorized person to obtain it, even though the information is Sudan (in Chapter 7) explains how public-key encryption, a technology stemming from cryptology research, makes it possible for a business such as VirtualEmporia.com to engage in secure communications with millions of individuals.
OCR for page 7
Computer Science: Reflections on the Field, Reflections from the Field traveling across the Internet’s shared infrastructure and could potentially be processed by tens or hundreds of computers along the path between her computer and VirtualEmporia. Information encoded with a public key can be decrypted only with the corresponding private key. VirtualEmporia.com publishes its public key, which anyone can use to encrypt information and securely send it to VirtualEmporia.com. Only VirtualEmporia.com, however, knows the private key for decrypting these messages. This technique can be applied both ways: software on Emily’s computer can use the secure channel to VirtualEmporia.com to create a new one in the reverse direction (from VirtualEmporia.com to Emily). Therefore confidential two-way communication can proceed, protected from prying eyes. Shipping the Book VirtualEmporia’s shipping system makes use of software algorithms to decide which warehouse to use for the books Emily has ordered, whether the books will all be shipped in one package or separately to help speed the books to Emily, which shipper to select, and so forth. Even though the books are physical objects that traveled by airplane and truck, their rapid journey is assisted by the shipper’s computerized logistics systems that inventory, schedule, and track the books’ journey. These systems also make it possible for Emily to track a package through a Web site and receive updates on when she can expect the package to arrive. A special secure version of the World Wide Web communication protocol provides a layer of abstraction that makes it possible for Emily to use secure communication without knowing about the details. Inventory management and routing are both examples of activities involving information manipulation. Before computer science, these processes could be accomplished only by hand. Computerized inventory and routing algorithms have made express shipping much more efficient. The result has been a reduction of both the costs and the elapsed time for delivery. Like shopping, package tracking depends on database systems. It also depends on wireless communications from the delivery people who carry portable wireless devices. These devices owe their origins to research on wireless networks and low-power devices. Conclusion Emily’s books will arrive at her home a few days later. Impatiently awaiting her purchase, Emily starts to wonder why the book even had to be a physical object: why couldn’t it just be delivered as a digital object, transmitted over the Internet? Indeed, computer science research has already
OCR for page 8
Computer Science: Reflections on the Field, Reflections from the Field provided many of the necessary foundations of electronic books and has built prototypes of all the basic components. Electronic books have just entered the commercial marketplace and may become more commonplace once inexpensive and practical book-like reading devices become available. An “early adopter,” Emily decides she wants something to read right away. She goes to VirtualEmporia’s e-books department, orders and downloads a book, and starts reading it within minutes. Perhaps what is most remarkable about Emily’s shopping experience is that it’s so commonplace today (and electronic books may become commonplace just over the horizon), while just 10 years ago it seemed far-fetched—even as the computer science groundwork was being laid. What other stories, which may seem fantastic today even as computer science research is laying their foundations, will we come to label mundane 10 and 20 years from now?
Representative terms from entire chapter: