Morning

Breakfast and Registration: 8:15 - 8:45

Welcome and Greeting: 8:50 - 9:00
Fred Roberts, Director of DIMACS

Representing Web Data

The study of the web as a graph is not only fascinating in its own right, but also yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution. We report on experiments on local and global properties of the web graph using two crawls each with over 200M pages and 1.5 billion links. Our study indicates that the macroscopic structure of the web is considerably more intricate than suggested by earlier experiments on a smaller scale.

Collaborators: Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Raymie Stata, Andrew Tomkins, Eli Upfal and Janet Wiener.

Data on the Web is hard to represent with conventional knowledge-base and database formalisms, due to problems like terminological differences across sites, and the frequent interleaving of textual information with structured, data-like information. Over the last few years, I have developed a new "information representation language" called WHIRL that addresses these problems by incorporating ideas from both AI knowledge representation systems and statistical information retrieval. Specifically, WHIRL is a subset of Prolog that has been extended by adding special features for reasoning about the similarity of fragments of text. WHIRL's combination of features greatly facilitates the construction of Web-based information integration systems; in more recent work, WHIRL has also been useful for collecting Web data for collaborative filtering and machine learning systems.

One of the major challenges in dealing with the web is the unstructured or semistructured nature of the data. There are major benefits in extracting the structure implicit in the web or extracting a subset of the data that can be structured easily. I will give a personal view of some attempts in this direction. The focus will be on the problems and proposals for attacking these problems.

New Web applications are enhancing businesses' abilities to gather data about their online customers that helps them to provide customized services and targeted advertising. By learning more about their customers, online businesses can develop more personal relationships with them, allowing them to better anticipate and meet their customers' needs. However, many of the Web-based data collection systems being deployed raise many privacy concerns. First, most of these systems are being deployed silently, without notifying Web site visitors or giving them an opportunity to choose whether or not they wish to have their data collected. Second, online data is increasingly being combined with data from a variety of sources, allowing for the development of detailed individual profiles. Third, data gathered for business purposes is increasingly being subpoenaed for use in criminal investigations and civil proceedings. Even when data is stored without traditional identifiers such as name or social security number, profiles often contain enough information to uniquely identify individuals. The privacy concerns raised by online data collection are gaining increased attention from the news media, the public, and policy makers. As more advanced data collection and processing applications are deployed without addressing privacy concerns, individual privacy is slowly eroding. Individually, most of these applications do not pose major threats, but taken together they are bringing us closer to a surveillance society.

How should a firm value information capital? This essay offers one framework that combines ideas from economics and computer science. Drawing a distinction between data and procedures, it augments the traditional Bayesian model that treats information as a change in uncertainty with instruments that permit information as instructions to be executed and reused. It then applies the standard hedonic methods - used in marketing to value tangible goods - to information goods. This leads to a generalized method for ascribing value that can be applied both to procedural information such as software, blueprints, and production know-how as well as to arbitrary resources that have instrumental qualities, that is, they represent tools for effecting outcomes. This approach has the added advantage of supporting efficient information transfers since consumers need not always see the information they are about to buy.

Text is passe. The growing popularity of the MP3 and RealAudio formats is leading to a new revolution on the Internet -- online music. In this talk, I will discuss some challenging problems that arise in building multi-media web crawlers, and in mining the web for nuggets of text and audio information.

In 2015, for a few hundred dollars a year, you can have a personal petabyte database (PetDB) that you can access from any point of connection, with any device. It stores and organizes any kind of digital data you want to have, without losing structure or information. All this data is queryable and it is arranged by type, content, structure, association and multiple categorizations and groupings. You can also locate items by when or how you encountered them, what you have done with them, where you were when you accessed them.

What could you fit in a personal petabyte store? Some possibilities:

• The contents of every book and magazine you ever bought.
• Every web page you've ever visited.
• Every email you've ever sent or received, including all attachments.
• Every version of any piece of software you have ever used.
• Maps and images of every place you have ever been.
• Descriptions and price lists for every kind of product you might want to buy-a "universal, personal catalog."
• Portions of the web you might want to browse, including snapshots at past points of time.

The PetDB isn't predicated upon some massive improvement in holographic memory technology or DNA-based storage units. Rather, it is an example of what could be done with a new generation of software infrastructure we term Net Data Managers (NDMs). NDMs are a radical departure from the capabilities and structure of current database management systems. They focus on data movement, rather than data storage, working equally well with live streams of data as with files in secondary storage. They will be capable of storing data of arbitrary types, without a matching database schema having been defined previously. They will efficiently execute queries over thousands or tens of thousands of information sites. They will locate and select data items by both internal content as well as a variety of external contexts. NDMs will also support monitoring rapidly changing information sources in a way that scales to thousands or even millions of triggers.

This talk lays out the requirements for Net Data Management, and reports on the research directions being pursued by the NIAGARA project, a joint undertaking with David DeWitt and Jeffrey Naughton at the University of Wisconsin.

This talk describes current limitations, new techniques, and future directions for information access and data processing on the web. We describe recent studies analyzing the accessibility, distribution, and structure of information on the web, which highlight the fact that there is much room for improvement and new methods. New techniques for information access and data processing on the web are described, including two projects at NEC Research Institute: Inquirus, which is a content-based metasearch engine, and CiteSeer, which is the largest free full-text index of scientific literature in the world.

Joint work with Lee Giles, Kurt Bollacker, and Eric Glover.

Web-related data has been gathered since the inception of Web, often without the knowledge of a vast majority of Web users. By Web data, I mean client, proxy, and server logs, and HTTP packet traces. Apart from obvious privacy issues, Web data has problems relating to gathering, storing, cleaning, and validation.

I have been involved in several aspects of collection of Web-related data from a wide variety of sources (both inside and outside AT&T) and in creating a repository in conjunction with the W3C World Wide Web consortium's Web Characterization group. The data has been used in several applications ranging from Web caching, improving the HTTP/1.1 protocol, testing Web software components for compliancy with the protocol, reducing validation traffic, to predicting future access.

I will cover the basics of collecting Web data, software issues dealing with cleaning and validating, related protocol issues, and use in a few applications.

In the first half of this talk, I will share some of my thoughts on semistructured databases, object-relational databases, XML, web querying, and how they are all related (or not). Using one of my favorite queries ("find U.S.-made Fender Jazz Bass or Precision Bass guitars available for under $700 within 50 miles of my home in San Jose, California"), I'll talk about what one can and can't do on the web today and how the database community can hopefully help change that. I'll also talk about the pros and cons of the aforementioned technologies, in terms of making my query answerable, and I'll propose a possible XML-based research agenda that might help us get there from here.

In the second half of this talk, I will discuss a new project - called Xperanto (Xml Publishing of Entities, Relationships, ANd Typed Objects) - that we have initiated at the IBM Almaden Research Center. The goal of this project is to provide facilities to enable "XML people" (as opposed to "SQL people") to conveniently publish content from relational and object-relational databases on the web in queryable XML form. I will outline the approach that we're taking, including the architecture of the system, the roles of the various Xperanto components, and some of the technical issues and challenges involved in the project.

XML (eXtensible Markup Language) is a magnet for hype: the successor to HTML for Web publishing, electronic data interchange, and e-commerce. In fact, XML is little more than a notation for trees and for tree grammars, a verbose variant of Lisp S-expressions coupled with a poor man's BNF (Backus-Naur form). Yet this simple basis has spawned scores of specialized sublanguages: for airlines, banks, and cell phones; for astronomy, biology, and chemistry; for the DOD and the IRS. Domain-specific languages indeed! There is much for the language designer to contribute here. In particular, as all this is based on a sort of S-expression, is there a role for a sort of Lisp?

We present the design of ObjectGlobe, a distributed and open query processor. Today, data is published on the Internet via Web servers which have, if at all, very localized query processing capabilities. The goal of the ObjectGlobe project is to establish an open market place in which data and query processing capabilities can be distributed and used by any kind of Internet application. The goal of the ObjectGlobe project is twofold. First, we would like to create an infrastructure that makes it as easy to distribute query processing capabilities (i.e., query operators) as it is to publish data and documents on the Web today. Second, we would like to enable clients to execute complex queries which involve the execution of operators from multiple providers at different sites and the retrieval of data and documents from multiple data sources. All query operators should be able to interact in a distributed query plan and it should be possible to move query operators to arbitrary sites, including sites which are near the data. The only requirement we make is that all query operators must be written in Java and conform to the secure interfaces of ObjectGlobe. One of the main challenges in the design of such an open system is to ensure s ecurity. We discuss the ObjectGlobe security requirements, show how basic components such as the optimizer and runtime system need to be extended. Finally, we present the results of some performance experiments that assess the benefits of placing query operators close to the Internet data sources and the additional cost for ensuring security in such an open system.

This is joint work with R. Braumandl, M. Keidl, D. Kossmann, A. Kreutz, S. Proels, S. Seltzsam, and K. Stocker (all at the University of Passau).

In the not too distant future, many devices (e.g., common household appliances, PDAs, cellphones, cars) will contain computer chips that will enable them to exhibit more sophisticated behavior and interact with other devices. For example, refrigerators will be able to monitor their contents and automatically order supplies. The heating system of a house will monitor the alarm clocks and calendars of their owners to set the temperature in an optimal fashion. In the context of ubiquitous computing, data exchange and computation occur in the background in response to cues from users. Computing is centered around the network and data, rather than around the computing devices or disks as it is today. Devices are added and removed from the network on a regular basis, and they must be able to interoperate with little human intervention.