The most common way of framing the search problem is as an exchange between a user and a database, where the user issues queries and the database replies with results that satisfy constraints imposed by the query but that also optimize some notion of relevance. There are several variations to this basic model that augment the dialogue between humans and machines through query refinement, relevance feedback, and other mechanism. However, rarely is this problem ever posed in a way in which the properties of the client and server are fundamentally different and in a way in which exploiting the differences can be used to yield substantially different experiences.

In 1993, Verner Vinge [3] introduced the notion of the Singularity -- a step function to nearly unlimited technological capability -- which would be realized if the acceleration of scientific progress continues to produce such things as strong AI, nanotechnology, and super-human intelligence. Since its introduction, the idea of the Singularity has been met with both evangelism (by Ray Kurzweil [2]) and apocalyptic warnings (by Bill Joy [1]).In this talk, I will introduce a more modest version of the idea, which I call the Internet Singularity. Like the original, the Internet Singularity suggests continued acceleration of progress, but makes greater emphasis on our ability to improve science, analytic methods, and engineering on data as opposed to the physical world. I make the case for the Internet Singularity in four steps.First, there is a general trend of more capabilities being more available to more people. These increasing capabilities span content creation, community, and commerce, yielding more power to today's amateur than yesterday's professional. As a result, the boundary between producers and consumers is becoming increasingly blurred over time.Second, in many parts of the Internet we see power law distributions with a heavy tail. One implication of heavy tail distributions is that the aggregate impact of small participants can be greater than that of the large participants.Third, with the Internet comes entirely new means for authoring new and derivative works: aggregations, mashups, tagging, remixing, etc. The greater emphasis on collaboration and sharing yields direct and indirect network effects. Network effects, can produce entirely new utility, making online activities potentially more efficient or valuable than the offline equivalent.Fourth, on the Internet, advances are effectively decoupled from the physical constraints of the offline world: startups costs are smaller; customer, collaborator, and audience pools are dramatically larger; and improvements happen in more of a continuous rather than discreet manner. As a result the effective clock cycle of progress is potentially much faster online.Putting these four pieces together reveals a compelling pattern: more people contribute to the collective pool; the collective pool contains entirely new value that is derived from its data; and the new value from the data increases individual and aggregate capabilities. In combination, these components mutually reinforce one another, forming something of a virtuous cycle. This is the Internet Singularity.Conceptually, if we consider engineering to be the ability to create artifacts, mathematical analysis to be the ability to analyze numerical properties, and science to be the pursuit of knowledge, then each of these activities -- when focused on digital objects as they exist on the Internet -- can be amplified in a manner consistent with the Internet Singularity.The implications for the Internet Singularity are profound as they suggest nothing less than the evolution of the scientific method itself. Moreover, these trends also imply that now may be the best possible moment in the history of the universe to be a computer scientist.

In the context of binary classification, we define disagreement as a mea- sure of how often two independently-trained models differ in their clas- sification of unlabeled data. We explore the use of disagreement for error estimation and model selection. We call the procedure co-validation, since the two models effectively (in)validate one another by comparing results on unlabeled data, which we assume is relatively cheap and plen- tiful compared to labeled data. We show that per-instance disagreement is an unbiased estimate of the variance of error for that instance. We also show that disagreement provides a lower bound on the prediction (gen- eralization) error, and a tight upper bound on the "variance of prediction error", or the variance of the average error across instances, where vari- ance is measured across training sets. We present experimental results on several data sets exploring co-validation for error estimation and model selection. The procedure is especially effective in active learning set- tings, where training sets are not drawn at random and cross validation overestimates error.

The World Wide Web has been at the center of a revolution in how algorithms are designed with massive amounts of data in mind. The essence of this revo- lution is conceptually very simple: real-world massive data sets are, more often than not, highly structured and regular. Regularities can be used in two com- plementary ways. First, systematic regularities within massive data sets can be used to craft algorithms that are potentially suboptimal in the worst-case, but highly effective for expected cases. Second, nonsystematic regularities—those that are too subtle to be encoded within an algorithm—can be discovered by automated methods so that the solutions are actually determined by the un- derlying data. In both cases, the existence of enormous problem instances that arise from a highly regular source is key to building more effective methods.

The Internet and the Web are continuously evolving giving rise to a rich and extremely dynamic environment where an increasing number of users require and expect new and more sophisticated services. Because of this, a field called “ Web Intelligence” is starting to receive interest from the Artificial Intelligence community. The Web and Internet pose new challenges to AI algorithms, which have been successfully applied in many other fields, at the same time stimu- lating the development of new techniques. In particular, as pointed out in the introduction to the first part of this special issue (Vol. 4, no. 2, May 2004), ma- chine learning methods have been extensively studied and have been applied to create intelligent systems that are actively involved with the Internet and Web.

When searching the WWW, users often desire results restricted to a particular document category. Ideally, a user would be able to filter results with a text classifier to minimize false positive results; however, current search engines allow only simple query modifications. To automate the process of generating effective query modifications, we introduce a sensitivity analysis-based method for extracting rules from nonlinear support vector machines. The proposed method allows the user to specify a desired precision while attempting to maximize the recall. Our method performs several levels of dimensionality reduction and is vastly faster than searching the combination feature space; moreover, it is very effective on real-world data.

The structure of the web is increasingly being used to improve organization, search, and analysis of information on the web. For example, Google uses the text in citing documents (documents that link to the target document) for search. We analyze the relative utility of document text, and the text in citing documents near the citation, for classification and description. Results show that the text in citing documents, when available, often has greater discriminative and descriptive power than the text in the target document itself. The combination of evidence from a document and citing documents can improve on either information source alone. Moreover, by ranking words and phrases in the citing documents according to expected entropy loss, we are able to accurately name clusters of web pages, even with very few positive examples. Our results confirm, quantify, and extend previous research using web structure in these areas, introducing new methods for classification and description of pages.

We p r e s e n t DEADLINER, a search engine that catalogs conference and workshop announcements, and ultimately will monitor and extract a wide range of academic convocation material from the web.The system currently extracts speakers, locations, dates, paper submission (and other) deadlines, topics, program committees, abstracts, and aÆliations.A user or user agent can perform detailed searches on these elds.DEADLINER was constructed using a methodology for rapid implementation of specialized search engines.This methodology avoids complex hand-tuned text extraction solutions, or natural language processing, by B a yesian integration of simple extractors that exploit loose formatting and keyw ord con ventions.The Bayesian framework further produces a search engine where each user can control the false alarm rate on a eld in an intuitive y et rigorous fashion.

We analyze the persistence of information on the web, looking at the percentage of invalid URLs contained in academic articles within the CiteSeer (ResearchIndex) database.The number of URLs contained in the papers has increased from an average of 0.06 in 1993 to 1.6 in 1999.We found that a significant percentage of URLs are now invalid, ranging from 23% for 1999 articles, to 53% for 1994.We also found that for almost all of the invalid URLs, it was possible to locate the information (or highly related information) in an alternate location, primarily with the use of search engines.However, the ability to relocate missing information varied according to search experience and effort expended.Citation practices suggest that more information may be lost in the future unless these practices are improved.We discuss persistent URL standards and their usage, and give recommendations for citing URLs in research articles as well as for finding the new location of invalid URLs.

We de ne a communit y on the web as a set of sites that have more links (in either direction) to members of the community than to non-members.Members of such a c o m m unity can be eÆciently iden ti ed in a maxim um ow / m i n im um cut framew ork, where the source is composed of known members, and the sink consists of well-kno wn non-members.A focused crawler that crawls to a xed depth can approximate community m e m bership by augmenting the graph induced by the cra wl with links to a virtual sink node.The effectiveness of the approximation algorithm is demonstrated with several crawl results that iden tify hubs, authorities, w eb rings, and other link topologies that are useful but not easily categorized.Applications of our approach include focused cra wlers and searc h engines, automatic population of portal categories, and improved ltering.

Neural networks are examined in the context of function approximation and the related field of time series prediction. A natural extension of radial basis nets is introduced. It is found that use of an adaptable gradient and normalized basis functions can significantly reduce the amount of data necessary to train the net while maintaining the speed advantage of a net that is linear in the weights. The local nature of the network permits the use of simple learning algorithms with short memories of earlier training data. In particular, it is shown that a one-dimensional Newton method is quite fast and reasonably accurate