Research

External Visitors and Data Management Colloquium Series Speakers

Recent visitors include:

Date	Name	Affiliation	Topic
11/19/98	Prof. Kenneth A. Ross	Columbia University, Department of Computer Science	Reusing Invariants: A New Strategy for Correlated Queries
02/04/99	Prof. Wayne Wolf and Prof. Bede Liu	Princeton University, Department of Electrical Engineering	Challenges in Internet Multimedia Systems
02/22/99	S. K. Chang	University of Pittsburgh, Visual Computer Laboratory, Department of Computer Science	Querying Multimedia Data Sources and Databases
05/03/99	Michael Lesk	Division of Information and Intelligent Systems, Computer and Information Science and Engineering Directorate, National Science Foundation	Internet Time, Real Time, Geological Time, and Bureaucratic Time
05/14/99	Prof. Krithi Ramamritham	Univ. Of Massachusetts- Amherst and IIT- Bombay	Reading Consistent and Current Data "Off the Air"

Future visitors include:

Date	Name	Affiliation	Topic
~5/99	Prof. Armando Fox	Stanford University, Computer Science Department	Adapting to network and client variability
~6/99	Prof. Richard R. Muntz	UCLA Computer Science Department	Scientific DBMS
~6/99	Prof. Praveen Seshadri	Cornell University, Computer Science Department	Cornell database systems research

Title	Abstract
Reusing Invariants: A New Strategy for Correlated Queries	Prof. Kenneth A. Ross, Columbia University, Department of Computer Science, Reusing Invariants: A New Strategy for Correlated Queries, Correlated queries are very common and important in decision support systems. Traditional nested iteration evaluation methods for such queries can be very time consuming. When they apply, query rewriting techniques have been shown to be much more efficient. But query rewriting is not always possible. When query rewriting does not apply, can we do something better than the traditional nested iteration methods? We propose a new invariant technique to evaluate correlated queries efficiently. The basic idea is to recognize the part of the subquery that is not related to the outer references and cache the result of that part after its first execution. Later, we can reuse the result and combine it with the result of the rest of the subquery that is changing for each iteration. Our technique applies to arbitrary correlated subqueries. We introduce algorithms to recognize the invariant part of a data flow tree, and to restructure the evaluation plan to reuse the stored intermediate result. We also propose an efficient method to teach an existing join optimizer to understand the invariant feature and thus allow it to be able to generate better join plans in the new context. Some other related optimization techniques are also discussed. The proposed techniques were implemented within three months on an existing real commercial database system. We also experimentally evaluate our proposed technique. Our evaluation indicates that, when query rewriting is not possible, the invariant technique is significantly better than the traditional nested iteration method. Even when query rewriting applies, the invariant technique is sometimes better than the query rewriting technique. Our conclusion is that the invariant technique should be considered as one of the alternatives in evaluating correlated queries since it fills the gap left by rewriting techniques. This talk represents joint work with Jun Rao.
Title	Abstract
Challenges in Internet Multimedia Systems	Prof. Wayne Wolf and Prof. Bede Liu, Princeton University, Department of Electrical Engineering, Challenges in Internet Multimedia Systems, This talk will provide an overview into some of the work being done at Princeton University on multimedia information systems which may be used either at a distance or locally. First, we will talk about 2 problems on watermarking we recently worked on: (a) a method for inserting fragile watermarks in compressed domain for authentication, some difficulties and ways to overcome them; and (b) a simple way to attack locally embedded watermarks. [Local watermarking has the advantage that human visual system can easily be incorporated.] Second, we will describe methods for video analysis and search. We will describe some techniques for video segmentation and keyframe analysis. We will then describe methods for visual search of extracted keyframes.
Title	Abstract
Querying Multimedia Data Sources and Databases	S. K. Chang, Visual Computer Laboratory, Department of Computer Science, University of Pittsburgh, Querying Multimedia Data Sources and Databases, To support the retrieval and fusion of multimedia information from multiple sources and databases, a spatial/temporal query language called SigmaQL is described. SigmaQL is based upon the sigma-operator sequence and in practice expressible in SQL-like syntax. SigmaQL allows a user to specify powerful spatial/temporal queries for both multimedia data sources and multimedia databases, eliminating the need to write different queries for each. A SigmaQL query can be processed in the most effective manner by first selecting the suitable transformations of multimedia data to derive the multimedia static schema, and then processing the query with respect to this multimedia static schema. Applications in distance learning and remote sensing are discussed.
Title	Abstract
Internet Time, Real Time, Geological Time, and Bureaucratic Time	Michael Lesk, Division of Information and Intelligent Systems Computer and Information Science and Engineering Directorate National Science Foundation, The President's Information Technology Advisory Committee (PITAC) has recommended a major expansion of research in computer science, and the Administration has requested over $300M in fiscal year 2000, with $146M to go to the National Science Foundation. What topics are most important? What style of research is most important? I will try to explain the NSF style: small projects, little supervision, peer review, and a wide span of scientific interest, and contrast with the PITAC desire for big projects, focused in five areas, getting steadily broader: Software, Scalable Networking, HCI and Information Management, High-End Computation, and Social/Ethical/Workforce issues. The most important conflict, especially for those of us temporarily at NSF, is the discrepancy between the rate at which NSF can change and the rate at which computer science is changing. If Congress approves the Administration request, NSF will fund an additional $110M of fundamental research in computer science next year (about a 50% increase) and it will also buy a new $36M supercomputer. During the next few months, meetings will discuss what the research agenda should be; what size projects should be encouraged; and how best to build community support to help make everything as successful as possible. Your input is welcome, although NSF usually does not fund industrial research. Even for funding to be awarded by September 2000, we ought to write the solicitations this summer. In my division, we started, this year, new programs in universal access, ethical/legal/social implications of information technology, visualization, multilingual technology, international digital libraries and personal robotics; but it's a race with the clock. Responding to the PITAC issues may take so long that new challenges might be more important (e.g. workforce shortages may disappear through rising university enrollments in CS while we are still debating what to do about them). The requests for FY2001 allocations are coming in now; computer science moves faster than that.
Title	Abstract
Reading Consistent and Current Data "Off the Air"	Krithi Ramamritham, University of Massachusetts-Amherst A crucial consideration in environments where data is broadcast to clients is the low bandwidth available for clients to communicate with servers. Many applications in such environments need to read data that is mutually consistent as well as current. However, given the asymmetric communication capabilities and the needs of clients in mobile environments, traditional serializability-based approaches are too restrictive, unnecessary, and impractical. We thus propose the use of a weaker correctness criterion called update consistency and outline a suite of mechanisms based on this criterion that ensure (1) the "mutual consistency" of data maintained by the server and read by clients, and (2) the "currency" of data read by clients. Using these mechanisms, clients can obtain data that is current and mutually consistent ``off the air'', i.e., without contacting the server to, say, obtain locks. Experimental results show a substantial reduction in response times as compared to existing (serializability-based) approaches. A further attractive feature of the approach is that if caching is possible at a client, weaker forms of currency can be obtained while still satisfying the mutual consistency of data.