Contents

1 Statement of Work 2 1.1 Summary of Proposed Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Software that We Propose to Enhance and Build Upon . . . . . . . . . . . . . . . . . . . . 5

DEVise: A Tool for Visual Data Analysis and Exploration . . . . . . . . . . . . . . . . . . 6 BIRCH: A Tool for Clustering Multidimensional Datasets . . . . . . . . . . . . . . . . . . 7 Multidimensional Constraint Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Research Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Visual Queries and DEVise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Integrated Access to Data and Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Ad-Hoc Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Implementation Plan and Milestones 15 2.1 Year 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Year 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Year 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Data Requirements 16

4 Supporting Facilities 16

5 Management 16

6 Quality Assurance 17

7 Biographical Sketches 18

8 Bibliography 21

1 Statement of Work

1.1 Summary of Proposed Work

Goal: We propose to enhance and further develop a tool called DEVise for retrieval, integration and visual analysis of large datasets from one or more data sources, including tabular data sets, timeseries and imagery. DEVise is a public-domain tool for interactive visual exploration of large datasets, and BIRCH is a tool for clustering multidimensional data that is integrated with DEVise. We will leverage existing tools and funding from NASA and ORD by building upon these tools. Our proposal is focused upon specific applications in space sciences, but the underlying research has wide applicability in other domains as well; in addition to space science applications, we are currently applying these tools in areas such as analysis of medical data from the UW Clinics, financial applications using data from a variety of sources including Compustat, CRSP and ISSM, and sales information from a catalog merchant.

Research Topics: As larger and larger datasets are collected and generated by scientists, and the number and diversity of these datasets increases, effective tools for data retrieval, integration and analysis become essential. Given that the Web is quickly becoming the most widely used means of connecting users to datasets, tools that can efficiently and conveniently access local data together with remote data over the Web are especially timely and useful. From a research standpoint, several issues require attention in developing such tools:

1. Dataset Size: Tools should be able to deal with datasets larger than main memory by using buffering to bring in portions of data as needed from secondary storage devices. While this is standard for database query engines, it is not so for visualization tools. Further, as the amount of graphical data (i.e., data describing the visual presentation) increases, efficient indexing techniques are required for ensuring interactive response times.

2. Integrated Presentation of Data and Metadata: As datasets increase in number, diversity and size, metadata becomes an essential tool for managing this complexity. We use the term ‘metadata’ in a general sense to mean a summary of a subset of data. A powerful paradigm is to allow users to explore data and (various kinds of) metadata in a uniform manner, and to drill down to the necessary level of detail interactively. How to achieve this, especially in the context of a visual querying environment, is an important focus of this proposal.

3. Diversity, Distribution and Autonomy of Data Sources: The Web can be thought of as a gigantic distributed database, and queries over multiple data from multiple sites can be thought of as distributed database queries, but there are important differences: typically, there is little or no local data processing capability, the number and diversity of data sources is enormous, and there is complete autonomy across sites (one consequence of which is that, in contrast to a distributed database, there is no such thing as a global system catalog).

4. Integration of Database-style Querying and Visualization: End users often require visual presentations of data. Allowing users to define visual presentations in a flexible manner, and to pose complex queries in terms of these visual presentations, greatly facilitates data retrieval and analysis for users who are not database experts.

Expected Results: 1. An enhanced version of the DEVise system that is capable of supporting data integration and analysis tasks, with emphasis on visual exploration and queries over the Web. In contrast to other related tools, it will allow database-style queries to be combined easily with visual data exploration, support uniform querying of data and metadata, and implement queries over the Web efficiently.

2. An environment for analyzing data at multiple levels of detail, within the context of the DEVise tool. We believe that understanding how to use metadata and summary data effectively in exploring data is central to interactive analysis of large datasets. Various tools can be used to produce a high-level summary of data, and the visualization tool must support integrated viewing of the summary data, or metadata, as well as the original data. This requires the ability to inform the visualization tool about the mapping from a summary object to the data records that correspond to it. Specifically, we will develop an enhanced version of the BIRCH clustering package (which produces summaries that are ‘clusters’ in the data) integrated fully with DEVise, to support interactive classification tasks. More generally, we will provide interfaces to enable other kinds of tools to generate summaries and pass to DEVise the mapping from summary objects to data records.

Project Team: This project involves faculty members at the University of Wisconsin-Madison, graduate students, and a staff programmer. Prof. Livny has led the development of the DeNet simulation package and the Condor system for workstation cluster management system. Prof. Ramakrishnan has led the development of the Coral deductive system. These are research software packages that are considered to be state-of-the-art, and have been used widely in universities and research labs in the US and abroad. Profs. Livny and Ramakrishnan have collaborated in the past, with NASA support, to develop the current versions of the DEVise and BIRCH tools and a system (called SEQ) for querying sequence data, and have also combined Coral and Condor (using ORD support) to provide query evaluation capabilities utilizing idle resources. Prof. Norman has worked with measurements and integrative modeling in the area of environmental biophysics. He has developed a soil- plant-atmosphere model, named Cupid, that has been applied to problems in remote sensing, irrigation scheduling, integrated pest management and water and carbon budgets of ecosystems. Prof. Norman has been the domain scientist driving the development and use of DEVise and BIRCH.

1.2 Introduction

Many large datasets are being generated by scientists, in large projects such as NASA’s EOS and Mission to Planet Earth, as well as numerous smaller projects. Datasets from a variety of sources are becoming available through the World-Wide Web. Ease of access to these datasets and effective analysis tools are crucial to the successful exploitation of this data for scientific research. The following trends motivate our work, and we aim to develop a data integration and analysis tool that addresses the attendant problems:

1. Increasing size of datasets, which implies that tools must be able to deal with data spread over secondary storage devices. Further, tools must allow users to examine data at several levels of detail, ranging from individual observations to metadata that summarizes a large volume of related data. For example, browsing the data at the level of metadata or summary descriptions may reveal interesting high-level features, and the user may then want to examine relevant portions of the data (visually or analytically) in more detail.

2. Increasing variety and number of data sources, which means that there must be a convenient way to integrate and analyse data from multiple remote sources, and to combine this information with

local data.

3. The need for visual exploration of data to complement analytical tools. This is expecially important when data is noisy or when the user is looking for loosely defined patterns or trends in the data.

4. The Web as a medium for connecting researchers to data sources. This is a convenient means of sharing data between researchers in different locations, and of disseminating data from archival repositories. Ideally, users should be able to query data from several Web sites as if all the data were stored locally; currently available tools cannot do this efficiently when the datasets involved are large.

This proposal can be seen as a logical continuation of the work we have carried out under our current AISRP NASA grant, in which we have developed the SEQ system for analytical queries over sequences and the current version of the DEVise tool for visual queries. We intend to expand the scope of our work to include more general datasets and queries, and to emphasize two new issues:

1. Analytical data transformation and querying capabilities, with an emphasis on efficient access to data sources through the Web.

2. Integrated querying and visualization of data and metadata.

These two changes to our research direction are based largely on our experience with the current tools and users’ feedback. Originally, DEVise was intended to address just visual exploration. Computation and transformation of the original dataset were carried out using the CORAL system for deductive queries and the SEQ system for queries over sequences. While this paradigm of loosely coupling the data transformation tools with the visualization tool does provide a powerful environment (and continues to be important to users), users clearly wanted to be able to combine data transformation and visualization seamlessly within a single tool. This experience has led us in the direction of providing more data transformation and querying capabilities within a single tool, and this motivates many of the enhancements that we are currently making to DEVise and that we intend to carry out as part of this proposal.

The second issue, namely integrated access to data and metadata, arose out of user feedback on using DEVise in conjunction with the BIRCH clustering tool. The clusters produced by BIRCH can be seen as a summary of the original data, or as a form of metadata, providing a compact, high-level description. In our interaction with users of BIRCH and DEVise, it has become very clear that users want to be able to cluster a dataset with a particular choice of clustering parameters (e.g., weights for the different dimensions, choice of distance metric), see the clusters in a visual presentation, then select all records in the original data corresponding to one or more clusters and process these records further. This kind of summary is by no means the only useful one, but it is a very good canonical example. Other examples of summaries include statistical measures, highly compressed versions of images, moving averages over a time-series (with the window size controlling the degree of summarization), etc. Clearly, we cannot expect to provide a comprehensive set of tools for generating different kinds of summaries. Rather, we must provide a convenient environment for generating summaries using an appropriate tool, and analysing both the summaries and the original data together in a natural manner. The key here is to enable the visualization tool to understand the connection between a summary and the original data (i.e., which original data records contributed to a summary record, so that the user can go from an interesting portion of the summary to the corresponding portion of the original data).

As concrete applications of our tool, we envisage the following:

• Quality Assurance: Is the data noisy? Is there a lot of missing data? Is the loss/noisiness concentrated in certain ‘regions’ of the data (identified by value ranges for some of the attributes)? Such ‘data cleaning’ is an ubiquitous and time-consuming task for many scientists.

• Queries Over the Data: Scientists often need to identify parts of the data that satisfy certain criteria. For example, to test a climate model, a scientist may want to run it on datasets that were collected under certain atmospheric conditions. Sometimes, determining which part of a dataset satisfies such criteria involves complex analysis; often, however, the conditions to be checked can be expressed as a database-style query, e.g., “Find days when the temperature was higher than some value,” or, “Find days when the average weekly temperature for the preceding week was higher than some value.”

• Concept Identification and Classification: Can we identify instances of domain-specific concepts in the data? For example, given several terrain photographs collected by satellites, can we classify the regions in each photograph into leaves, sunlit regions, branches, etc.? (This is an example of an application that we can already handle, although with more manual intervention than we would like to have ultimately, with the current versions of the DEVise and BIRCH tools.)

• Hypothesis Verification: If we believe that there is a causal relationship between ozone levels in the atmosphere and the incidence of skin cancer, it would be helpful to be able to quickly browse relevant datasets to see if they might support such a hypothesis. Then, additional tools can be brought to bear upon such promising datasets.

• Exploratory Data Analysis: Can we spot interesting patterns or trends in the data, especially when the dataset is very large? For example, it might be the case that whenever the use of pesticides in an area goes above a certain threshold, there is a corresponding increase in the level of certain contaminants in local rivers. If we do not know this a priori, but would be interested in knowing, can tools be developed to assist us in discovering such correlations? Again, a combination of databasestyle ad-hoc querying and visual exploration could suggest such patterns, and additional tools could then be used to validate them. Such exploratory analysis is carried out routinely in many different application domains, but software environments supporting this activity are in their infancy. The problems that must be addressed and the techniques that can be applied have been studied in Statistics, Artificial Intelligence, and in Databases.

1.3 Software that We Propose to Enhance and Build Upon

Our overall goal is to develop a tool to support retrieval, integration and analysis of data from one or more sources over the Web. The tool must be capable of dealing with datasets whose size is larger than available main memory on a typical desktop machine, and must support browsing of metadata (typically generated using other tools) and data in a uniform manner. There are many aspects to such a tool, and we intend to enhance existing tools and software, rather than to develop a new tool from scratch. By doing so, we significantly leverage existing and prior support from NSF, NASA, ORD and the Packard Foundation. In this section, we describe the tools that we intend to enhance, and related software that we intend to build upon. Details of our enhancements and our research objectives are presented in Section 1.4.

DEVise: A Tool for Visual Data Analysis and Exploration

Visual exploration of large, multidimensional data sets is becoming increasingly important for business and scientific communities alike. Data streams are being continuously produced by remote sensors, program trace generators, simulators, and the stock market, to name a few. Interpreting such data in text form is a virtually impossible task due to the quantity of data. Analyzing the data statistically may be impossible if what should be looked for is not fully understood. A visual representation, on the other hand, can often be used to find interesting trends and patterns that cannot be expressed in exact statistical terms.

Large and complex data sets present a challenging task for visualization systems. The size of data streams can easily reach tens or hundreds of megabytes and each record in the stream may contain hundreds of data attributes. It is important for visualization systems to avoid overwhelming the main memory or virtual memory of a workstation, and to allow the user to navigate through the data and metadata without being buried in it. Standard & Poor’s CompuStat database, for instance, contains financial data of roughly 5,000 companies. The total size of the database is over 1 gigabyte and each data record has over 350 attributes. The Institute for the Study of Security Markets (ISSM) distributes an annual database containing trade and quote transactions of 5,000 stocks. Each stock is represented as a separate time series. The single largest time series in the 1992 ISSM database is for the IBM stock which recorded almost a million trade and quote transactions, totalling over 20 megabytes in size.

We have developed a data visualization and exploration system called DEVise that attempts to solve both the data size and metadata complexity issues. The system uses off-the-shelf hardware and has minimal main memory requirements. It can handle data that is large in volume, complex in structure (multidimensional and/or hierarchical), and that may be imported from different sources such as database servers, external programs, and World Wide Web resources. Commercial and scientific databases can also be linked to DEVise to allow the user to visualize and analyze related information from heterogeneous sources.

As an example of the use of DEVise, consider the following scenario, which is based on our collaboration with a Soil Sciences user-group. Extensive manual effort is currently required to extract useful data from the FIS or BORIS data bases (maintained by NASA). For example, to compare a prediction of infrared temperature from a soil-plant-atmosphere model (named Cupid) with aircraft and satellite observations, input data (soil, vegetation and weather data) required by the model must be obtained from the data base subject to the constraint that the site was cloud free at the time of satellite and aircraft observation. Furthermore, when a cloud-free period is obtained all the model input data must be available (weather data is collected on half hour intervals, surface soil moisture measured daily, leaf area and deep soil moisture measured weekly with the time of observation varying from station to station) from the previous day of rain to the time of coincidence of clear sky and satellite overpass either by direct measurement or interpolation in time or space. Extracting the appropriate data from the database is itself time consuming, but it does not require as much time as just finding an appropriate time sequence that meets the criteria, which can take months. We note that SQL is wholly inadequate for tasks such as this.

Missing or erroneous data are among the major complicating factors that make this selection process difficult. After the inputs required by the model have been extracted, the model is run; then model predictions of infrared temperatures are compared with measurements from aircraft or satellites, which also need to be extracted from the data system. Typically such comparisons involve time sequences of predictions and measurements. For example, predicted and measured infrared temperature would be plotted as a function of time; they may agree at some times and disagree at other times. On other occasions the two curves may just be shifted in time by some fixed phase. Alternatively they may agree at high wind speeds and disagree at low wind speeds. Clearly, the ability to visually browse such datasets is invaluable.

Defining Visual Queries in DEVise

In essence, we can think of visual queries in DEVise as definitions of views that integrate the source data, which can come from a variety of sources including text files, sequence databases, and the World-Wide Web. Using a point-and-click interface, a user can define a ‘visual query’ that determines how the source data is to be interpreted and displayed on the screen.

In DEVise, a data stream consists of binary or ASCII records where each record contains one or more attributes. A data stream is combined with a schema to produce TData. The schema describes the data attributes in the data stream. Each TData record is mapped to a GData record where each GData record consists of graphical attributes. This mapping can be defined by the user, and provides a very high degree of flexibility in defining visual queries, as the examples in the appendix illustrate.

Example Applications of DEVise

We now present some example applications of DEVise, to illustrate the power of the current tool and its scope.

The first example, shown in Figure DEVise-1, illustrates the combined use of DEVise and BIRCH and is discussed in Section 1.3.

The second example, shown in Figure DEVise-2, illustrates the use of DEVise to view data from multiple sources in a uniform manner. The sugar futures information is retrieved (in real-time, in response to user actions like scrolling and zooming) over the Web. The S&P information is stored in a local file. The information on DEC is taken from two vendor databases.

The third example, shown in Figure DEVise-3, illustrates the flexibility of DEVise. The data that is visualized is a collection of traces that reflects the execution of an experiment controlled by the CONDOR idle resource utilization software. The two pairs of graphs correspond to two different runs, with different scheduling policies (explained below). The experiment consists of several tasks, each of which must be executed in a round. Rounds of execution continue until the computation converges in a certain manner, and a new round cannot be started until all tasks in the previous round are complete. Clearly, the scheduling policy used for tasks within a round—when a machine becomes available, should we schedule the longest remaining task or the shortest, for example—affects the length of the computation. The visualization brings this out graphically. The X-axis corresponds to time, and the Y-axis corresponds to machines. A given location is assigned a block of a certain color, denoting the task being executed by the corresponding machine at that time. The red graph below shows the cumulative idle time. The ‘rounds’ of computation are clearly reflected in both graphs. It is worth noting that the datasets in these examples are all considerably larger than the memory available to DEVise—buffering is used to bring in just the portion of the data needed to refresh the display.

BIRCH: A Tool for Clustering Multidimensional Datasets

Finding natural ‘clusters’ in a multidimensional dataset is a well-studied problem in Statistics, and has been applied in a variety of domains for concept identification and classification. It can be regarded as a variant of the problem of computing a density function; this has applicability for constructing histograms of data, for example. Clearly, clustering is a powerful technique for exploratory analysis.

We have developed a clustering algorithm called BIRCH [ZRL96] that is capable of clustering very large datasets while using very little memory. It incrementally and dynamically clusters incoming multidimensional metric data points, and can typically find a good clustering with a single scan of the data, and improve the quality further with a few additional scans. A novel feature is that BIRCH exploits its knowledge of the portion of the input dataset that it has already clustered to find-tune the clustering of the rest of the dataset. Thus, it adjusts dynamically to the input dataset to try and produce the best quality clustering with the available resources (i.e., available memory and time constraints). The low memory requirements of Birch enable us to cluster on different subsets of the data attributes (i.e., dimensions) in parallel, and to collect useful statistical information on attributes that do not take part in the clustering.

Multidimensional Constraint Queries

Constraints offer a very powerful way of formulating queries over multidimensional point datasets, and can be used in a variety of applications, including business and scientific analysis. The idea is that a desired region (in the multidimensional space) can be specified as a conjunction of polynomial constraints. As an example, a convex polygon can be represented as a conjunction of two-dimensional linear constraints. Each constraint identifies a half-plane; a conjunction of constraints can therefore be used to identify any convex region, as illustrated in Figure 1. Note that the constraints did not have to form a closed region.

Figure 1: A Convex Polygon as a Conjunction of Constraints

The R^{∗}-Tree index is a popular multidimensional index structure and can be used to store multidimensional point datasets (as well as non-point data). It is used in several extensible and GIS-oriented database systems. Boxes that are orthogonal to the axes are the standard approximation for data objects and queries in such indexes. However, a box is often a poor approximation, especially for queries and data that are irregularly shaped and not suitably oriented with respect to the axes.

An alternative is to use a conjunction of constraints to describe the bounding envelope of data objects and queries. Storing conjunctions of linear constraints can be expensive in terms of space; we do not consider this approach. We do propose, however, that queries be approximated by such conjunctions; the only overhead is a more complex overlap test, which we demonstrate can be carried out very efficiently [GRSY96].

To illustrate the kinds of queries that can be supported with such index structures, let us consider a portion of the Compustat stock and business data set with attributes year number, earnings per share, stock low, stock high, and stock value at year close. One example query using constraints is: Retrieve all tuples that have a price-earnings (P/E) ratio less than some constant. Investors frequently use the P/E ratio as a measure of how undervalued or overvalued a company is. In terms of constraints, the above query can be expressed as: price_{year−end} = r ∗ earnings ≤ 0 (where r is the ratio value). As another example, consider: Retrieve all tuples that correspond to companies whose value didn’t vary by more than some percent of the price at year’s end. In terms of constraints: price_{high}−price_{low} −p∗price_{year−end} ≤ 0 (where p is the percentage above). This measure is indicative of a stock’s volatility.

It is easy to identify similar examples over virtually any multidimensional dataset of interest. For example, if we have an environmental dataset with attributes time, latitude, longitude, height, radiationlevel1, radiation-level2, we can ask queries like the following: “Find observations such that radiation-level1 is greater than radiation-level2.” “Find observations such that radiation−level1∗radiation−level2 < 1.”

We have developed an extension to the R^{∗}-Tree index that can support multidimensional constraint queries very efficiently, and implemented a package based upon this extension. We intend to use this both within the visual query processing engine of DEVise (to index graphical data) and to provide constraint query capabilities in the data transformation engine.

1.4 Research Goals

In this section, we motivate and describe how we propose to enhance and apply the tools and software mentioned above.

Visual Queries and DEVise

Visual browsing or visual querying of the data can be an extremely powerful way to explore large datasets. Several properties of a visual browser are important for the applications that we target:

1. In addition to providing some convenient way of using common visual presentation ‘templates’ such as scatter plots or bar graphs, the system should provide a flexible way to construct a broad class of new templates so that each dataset can be viewed in the most natural manner for any given application. To view data, the user must describe how it is to be visually presented; this includes a choice of existing templates or construction of new templates, and a specification of how the data records are to be mapped into a visual presentation based on these templates. We refer to the combination of templates and mappings used to describe a visual presentation as a visual query.

2. The definition of a ‘visual query’ should be cleanly separated from the actual dataset, so that it can be applied to other similar datasets, and the query definition facilities should be very flexible, in order to allow users to ‘see’ their data in as many different ways as possible.

3. The browser should be capable of simultaneously presenting multiple views of one or more datasets, in order to allow effective browsing of datasets with complex inter-relationships. Users should be able to define links between different views so that all related views change automatically in natural ways when one view is manipulated through a visual operation (e.g., a cursor operation, zooming, scrolling, etc.).

4. The browser should be capable of dealing with very large datasets, even if the datasets are several times larger than available memory sizes.

5. The browser should be capable of presenting the data at multiple levels of detail, in order to support effective interactive browsing of very large datasets. Typically, users want to see the data at a coarse level of detail, and then be able to look at interesting portions in more detail. The familiar operation of zooming is just one instance of this paradigm; more generally, there are several levels of summary data, or metadata, and users want to interleave browsing of the metadata and browsing of relevant portions of the actual data as needed.

Of the currently available tools for visual data exploration, we believe that DEVise [CLR95] comes the closest to meeting these goals. DEVise was developed by us with prior NASA support and is currently in use by several groups (e.g., the business school, scientists in soil science, the NMR data center, the UW clinics, a catalog merchant; under consideration by IBM for use with their Data Mining product, and by LBL Laboratories).

Extending DEVise

There are several areas in which DEVise needs to be enhanced. We intend to work on the following tasks, which are directly related to the visualization capabilities of the tool or the overall system architecture:

1. Separate query definitions from details of the underlying data sets. This will make DEVise a powerful tool for collaborative computing: a user can navigate the data, and other connected users will see the same data display simultaneously, including all the changes performed by the original user. Since each user has the ability to do such navigation, in effect each user sees an active data presentation.

2. Improve various implementation-level aspects of DEVise, e.g., 3D symbols, color management, network connections, etc.

3. Build ‘drivers’ for a variety of data sources so that DEVise can access these data sources. (We have drivers for text files, SEQ data streams, Web URLs, Compustat data, etc., but not for NetCDF, for example).

Extensions related to other aspects such as integrated data and metadata browsing and ad-hoc querying are described in Section 1.4 and 1.4.

Integrated Access to Data and Metadata

Visualization of very large datasets presents several challenges. A basic problem is that the dataset size may exceed the amount of main memory available. This problem has been addressed in DEVise by incorporating a buffer manager, which brings in data records as needed, if necessary making space in the buffer pool (an area of main memory allocated for this purpose) by discarding records that are not currently needed. Even with intelligent buffer management policies, interactive response times cannot be achieved for very large datasets, and too much information is lost by compressing a very large volume of data onto a single screen. A powerful paradigm for addressing this fundamental problem is to let users create summaries of data (which are typically much smaller than the original dataset) and to browse the summaries, or metadata, to get an overview of the entire dataset. Subsequently, users can look at interesting portions of the data in more detail; in our experience, users in fact want to be able to interleave the browsing of data and metadata.

As a concrete example, we have demonstrated the feasibility of integrating the BIRCH clustering tool with DEVise [?]. To illustrate the combined use of BIRCH and Devise, we present an actual application involving the filtering of forestry images. We were given two similar images of trees with a partly cloudy sky as the background, taken at two different wavelengths. One is in the near-infrared band (NIR), and the other is in visible wavelength band (VIS). Each image contains 512x1024 pixels, and each pixel has a pair of brightness values corresponding to NIR and VIS. Soil scientists receive hundreds of such image pairs and try to first filter the trees from the background, and then filter the trees into sunlit leaves, shadows and branches for statistical analysis.

We applied BIRCH to the (NIR,VIS) value pairs for all pixels in an image (512x1024 2-d tuples) by using 400 kbytes of memory (about 5% of the dataset size) and 80 kbytes of disk space (about 20% of the memory size), and weighting NIR and VIS values equally. We obtained 5 clusters that correspond to (1) very bright part of sky, (2) ordinary part of sky, (3) clouds, (4) sunlit leaves (5) tree branches and shadows on the trees. This step took 284 seconds.

However the branches and shadows were too similar to be distinguished from each other, although we could separate them from the other cluster categories. So we extracted the part of the data corresponding to (5) (146707 2-d tuples) and used BIRCH again. But this time, (1) NIR was weighted 10 times heavier than VIS because we observed that branches and shadows were easier to tell apart from the NIR image than from the VIS image; (2) BIRCH was able to draw finer distinctions because it processed a smaller dataset with the same amount of memory. The two clusters corresponding to branches and shadows were obtained in 71 seconds.

The result of clustering using BIRCH is shown in Figure DEVise-1 (in the appendix). Visually, we can see that it is a satisfactory filtering of the original image according to the user’s intention. While this was a very successful effort in terms of the clustering results that we obtained, the interaction between BIRCH (to do clustering) and DEVise (to display the results) was tedious.

The important point to be noted in this example of using BIRCH and DEVise together is that the clusters produced by BIRCH can be seen as a summary of the original data: these clusters can thus be regarded as a form of metadata, providing a compact, high-level description. This kind of summary is by no means the only useful one, but it is a very good canonical example. In our interaction with users of BIRCH and DEVise, it has become very clear that users want to be able to cluster a dataset with a particular choice of clustering parameters (e.g., weights for the different dimensions, choice of distance metric), see the clusters in a visual presentation, then select all records in the original data corresponding to one or more clusters and process these records further. In other words, they use the clusters produced by BIRCH to obtain a high-level overview of the data, and narrow the scope of subsequent detailed analysis of interesting portions of the data.

Extending DEVise to Handle Integrated Data/Metadata Browsing

The clusters produced by BIRCH are only one example of a summary description of data. Other examples of summaries include:

1. Statistical measures over subsets of the data. Indeed, such summaries are so useful that some support is built directly into the current version of DEVise.

2. Compressed versions of images.

3. Moving averages over a time-series, with the window size controlling the degree of summarization. Such a summary could be generated using the SEQ tool, for instance.

4. The result of an SQL Groupby query, which summarizes all records with the same value in the grouped field into a single record (using statistical functions like sum or average).

5. Patterns extracted by data mining techniques for finding association rules [] or sequential patterns [].

As an example of integrated data/metadata browsing using some of these other kinds of summaries for metadata, we can obtain a monthly average of a series of daily temperature readings, using the SEQ system, which we have developed for sequence querying. A user may then want to see a scatterplot of daily temperature versus rainfall for all months in which the average temperature is above a certain value.

As another example, a user may want to browse a large collection of satellite images (perhaps with additional selection criteria such as the time and location the images were recorded, which can be expressed using the ad-hoc query capabilities described in Section 1.4). By compressing the images, it becomes feasible to look directly at several images interactively; but having browsed this ‘metadata’ representation, the user may want to see a subset of the images in greater detail. Our work on quality-controlled compression [?] can be used to generate compressed images, and a natural interleaving of compression and browsing can be supported by incorporating this technology into DEVise; we propose to address this as a second instance of integrated data/metadata browsing (with the BIRCH/DEVise combination representing the first instance).

More generally, image summaries can be generated in several other ways as well, for example, by using mathematical tranforms (e.g., wavelets, DCT, Fourier, Karhunen-Loewe) which concentrate most of the ‘information’ in an image into a small vector of numbers. Each such vector summarizes an image, and comparing these summaries can be a useful filter in further processing of the image set: similar images have summaries that are ‘close’, using an appropriate distance metric. While we do not propose to directly address image processing issues, we note that visualizing such summaries, and then interactively looking at specific images, is done very naturally in the DEVise data/metadata browsing paradigm.

The list of possible kinds of summaries presented above is not comprehensive, and users may want to utilize other kinds of summaries as well. Thus, we cannot expect to provide a comprehensive set of tools for generating different kinds of summaries.

Rather, we must provide a convenient environment for generating summaries using an appropriate tool, and analysing both the summaries and the original data together in a natural manner. The key here is to enable the visualization tool, DEVise, to understand the mapping between a summary object and the original data (i.e., which original data records contributed to a summary object, such as a cluster, so that the user can go from an interesting portion of the summary to the corresponding portion of the original data).

We intend to develop BIRCH further (e.g., to cluster non-metric data), and to integrate it fully with DEVise. In doing so, we expect to abstract from the experience and put in place a framework and a set of interfaces that will enable users to browse other kinds of summaries.

Ad-Hoc Queries

The DEVise tool was originally intended to address just visual exploration, with database style querying and, in general, computation and transformation of the original dataset carried out using other tools. Specifically, we provided our users with the CORAL system for deductive queries and the SEQ system for queries over sequences. While this paradigm of loosely coupling the data transformation tools with the visualization tool did provide a powerful framework (and continues to be supported), users clearly wanted to be able to combine data transformation and visualization seamlessly within a single tool. We therefore added data transformation capabilities to DEVise, and this has proven to be very popular.

One of the objectives of this proposal is to add a data transformation, or analytical query, component to DEVise. This would allow source data to be combined and transformed, before it is presented visually. More generally, it would make DEVise a very powerful front-end for SQL-style query languages, in addition to its other applications, given the tight interaction between visual operations and data retrieval in DEVise: a broad class of SQL queries over a relation, including queries utilizing grouping and aggregate operations, can be expressed in terms of mouse operations on a DEVise presentation.

Developing a powerful database style query facility is a significant task, but fortunately, we have a significant code-base—and feedback from a wide user-base!—to draw upon in this effort, and indeed, we have a preliminary prototype in place. The system architecture for DEVise with all the extensions that we propose is shown in Figure 2; it closely follows the architecure of the current prototype.

Figure 2: DEVise System Architecture

In extending and refining the prototype ad-hoc query facility, we intend to draw upon code from the following systems that we have developed (and distributed widely): the CORAL deductive query system, the Minibase relational DBMS, and the SEQ sequence query system. The idea is not to simply take the three systems; rather, we have chosen specific pieces of code that we can re-use and combine effectively to develop a powerful data transformation engine within DEVise. As noted earlier, an initial prototype is in place, and we intend to develop it further as part of this proposal to provide a unique combination of visual exploration and database querying facilities within a single tool.

Queries over the Web

The data transformation component allows new tables and time-series to be defined in terms of existing tables and time-series, using the transformation language (or query language, depending on one’s point of view). Efficient database-style query optimization is important, and a query optimizer taken from the Minibase RDBMS has already been incorporated into our prototype ad-hoc query facility.

DEVise views can be defined over datasets stored at several Web sites, and distributed query optimization is essential to good performance. We therefore propose to extend the optimizer in the prototype to do database-style distributed query optimization for queries that access multiple sources over the Web. This would greatly enhance the use of our tool for accessing large datasets over the Web, and we have already initiated work on this extension.

A novel aspect of our paradigm is that we are developing light-weight data wrappers that can be used to provide efficient access in conjunction with the query optimization in the browser. For example, if a site contains a lot of tabular data (e.g., weather tables, financial time-series), the owner of the site can download the data wrapper package and use it to provide an alternative way to access the data. The wrapper supports index creation, and includes an optimizer and evaluation engine for simple queries, plus a well-defined interface that is understood by the optimizer in the DEVise browsing tool. Thus, without modifying the original files or moving them into a DBMS, local query processing capability is added, and the browser can exploit this capability to minimize data traffic and compute queries efficiently. This benefits both the owner of the data site, since more queries can be supported, given that each query requires less information to be shipped (although some local processing cost is involved), and the user of the browsing tool, who receives a response faster.

We emphasize that our design goal is to let users maintain their data in whatever format they happen to be in currently, without requiring that the data be imported into a specialized system such as a conventional DBMS or converted to a different file format. We will use drivers to read data in various file formats, and include any necessary processing capabilities in our data transformation engine and the source wrappers. Further, the use of source wrapper code is entirely optional. If a user does not wish to install and use this software, his or her data can still be retrieved, transformed and visualized using the DEVise browser, only perhaps less efficiently since filtering at the source site is not supported in this scenario.

Class of Queries to be Supported

Designing the data transformation language is an important task. Based on feedback from our users, it seems clear that basic SQL-style queries supporting selection, projection of attributes, relational joins, grouping and aggregate operations is required. Further, a number of queries over time-series such as computing moving averages arise frequently in the scientific applications that we have encountered. A third class of queries that seems useful to support in this context is the class of conjunctive constraint queries on k-dimensional datasets described in Section 1.3. These are queries specified as a conjunction of linear or nonlinear polynomial constraints over one or more of the k attributes, and intuitively, define regions in k-dimensional space.

We are currently in the process of designing a language with support for the kinds of queries described above.

Related Work

In comparison to other visualization tools DEVise is unique in its combination of database style query capabilities and flexible visualization support. Unlike most visualization tools, it is designed to deal with large datasets, and buffering and caching (both from disk and from remote sites) are integral aspects of the DEVise architecture. By mapping each data record to a visual element, and associating the record id of the data record with the corresponding visual element, DEVise has the ability to go from the visual presentation all the way back to the original data record. In conjunction with the ability to associate summary data with the original data records, this gives DEVise (with the extensions that we propose) unique capabilities with respect to the levels of detail at which a user can explore a dataset: a user can switch interactively from a metadata representation (e.g., a cluster) to the visual representation of the data records in the cluster, to the actual data records themselves, and back again to the cluster level.

To our knowledge there is no other tool or research that aims to support the paradigm of integrated querying and browsing of data together with a wide range of metadata, independently of how the metadata is generated. It is worth noting however that tools such as IDL now provide a number of packages that allow data to be processed. This indicates that the importance of using such metadata, and

Specifically, the following visualization tools are similar in certain respects to DEVise. We regard some of these tools, e.g. Vis5D, as being complementary to DEVise in that they both provide some valuable and distinct capabilities.

2 Implementation Plan and Milestones

Our overall plan can be summarized as follows. In the first year, we will study the interaction between BIRCH and DEVise, and abstract from this to arrive at a toolkit interface design, and a first-cut ‘toolkit’ that allows combined use of these two tools. We will also initiate research into the data mining and constraint query problems outlined in this proposal. In the second year, we will implement tools based on the algorithms developed in the first year, and also integrate some of the existing tools like CORAL and SEQ into the toolkit architecture. In the third year, we will complete the integration of all the tools, and address the issue of idle-resource utilization.

2.1 Year 1

1. Separate query definitions from details of the underlying data sets in DEVise.

2. Add 3-D symbols to DEVise.

3. Improve color management in DEVise to ensure that a consistent palette of colors is used when a session is stopped and re-started, in the presence of other tools (e.g. the Netscape browser) that also access the system’s color map.

4. Incorporate efficient indexing of graphical data in the visual engine, using the extended R^{∗}-Tree package that we have developed.

5. Optimize evaluation of visual operations by improving the caching techniques for graphical data.

6. Develop a buffer manager interface that allows the visual engine and the data transformation engine to share the buffer pool.

7. Extend the buffering and caching modules to deal cleanly with remote data and data from sequential media such as tape drives.

8. Improve the way network connections are managed within DEVise.

9. Build ‘drivers’ for a variety of data sources so that DEVise can access these data sources. (We have drivers for text files, SEQ data streams, Web URLs, Compustat data, etc., but not for NetCDF, for example).

10. Understand the interaction of BIRCH and DEVise, in particular, the nature of the intermediate datasets produced as a result of BIRCH and DEVise operations in the course of a long session in which both kinds of operations are interleaved.

11. Develop a clean interface between BIRCH and DEVise that allows a user to guide the interaction between them by using a point-and-click interface.

12. Extend the relational query optimizer and run-time query evaluation code in the current prototype to make it more robust.

13. Design the data transformation/query language, to support a combination of efficiently implementable relational, sequence and constraint queries.

14. Develop the run-time query evaluation code in the prototype to support the extended transformation language.

15. Extend the optimizer to do distributed query optimization.

16. Develop interfaces for data source wrappers, following industry standards such as OLE/DB as closely as possible.

17. Develop the prototype source wrapper package further to make it more robust and integrate efficient indexing based upon the extended R^{∗}-Tree package that we have developed.

18. Develop a GUI front-end for the source wrapper package to allow users to conveniently make their data accessible to DEVise.

2.2 Year 2

1.

2.3 Year 3

1.

3 Data Requirements

4 Supporting Facilities

The Computer Sciences department currently has 190 DecStations running Ultrix4.2, 46 HP workstations (Snakes) running HPUX8, and 24 Sparcs running SunOS4.1. In addition to these workstations the Computing Facility of the Computer Sciences department includes a 64-node CM5 and a 64-node INTEL Paragon. Every faculty, stuff member, and graduate student, has a workstation on his/her desk.

The instruction laboratories of the department consist of more than 70 powerful workstations (HP Snakes and Sparc-10s) and several PCs of various kinds.

All the computing resources, research and instructional, are managed and maintained by the Computer System Lab (CSL) of the department.

These facilities are more than adequate for the proposed work; we are therefore only asking for four machines for the new research assistants to be hired as part of this project.

5 Management

This work will be carried out under the supervision of the PIs, R. Ramakrishnan and M. Livny, with Prof. J. Norman providing direction and feedback as a domain scientist whose laboratory uses our tool. Each will be responsible for certain portions of the work, with Profs. Livny and Ramakrishnan primarily responsible for the tool interface design and development, and Prof. Norman responsible for using the tool in soil science and climatology applications and suggesting necessary refinements. In addition to meetings with individual students and staff members, there will be weekly meetings involving all the members working on the project, to ensure that all the work is carefully co-ordinated. Based upon our ongoing successful collaboration on other projects, we anticipate that this approach will prove to be effective in terms of both producing good research results and adhering to the overall project milestones.

6 Quality Assurance

Since we do not propose to generate datasets, or to carry out studies using specific datasets, our main concern in this respect is testing and refinement of the tool being enhanced. We propose to continue with our current approach, which is based on developing in-house test suites, which are re-run with each version of our software, and extensive interaction with users in our group and in other groups. (While we will use datasets to experiment with and illustrate the use of our tools, our focus is on the tools themselves, and we do not expect to draw conclusions based on any particular data.)

7 Biographical Sketches

Miron Livny

University of Wisconsin - Madison Department of Computer Sciences Madison, WI 53706 (608)262-0856 miron@cs.wisc.edu

EDUCATION Ph.D., Computer Science, Weizmann Institute of Science, February, 1984.

Dissertation Topic: “The Study of Load Balancing Algorithms for Decentralized Distributed

Processing Systems” Dissertation Advisor: “Myron Melman”

M.Sc., Computer Science, Weizmann Institute of Science, March, 1978. B.Sc., Physics and Mathematics, Cum Laude, Hebrew University, July, 1975.

RESEARCH AND PROFESSIONAL EXPERIENCE University of Wisconsin-Madison, Depart-

ment of Computer Sciences, Associate Professor, September, 1989 - present. University of Wisconsin-Madison, Department of Computer Sciences, Assistant Professor, April,

1984 - August 1989.

SOFTWARE DEVELOPED The DENET simulation package and the CONDOR workstation cluster management system. Both are distributed freely, and are currently being used extensively worldwide.

SELECTED RECENT PUBLICATIONS “Value-Based Scheduling in Real Time Database Sys-

tems”, to appear in the VLDB Journal, (with J. Haritsa, and M. Carey). “Tapes Hold Data Too”, 1993 ACM SIGMOD International Conference on Management of Data,

May, 1993, (with M. Carey and L. Haas). “Managing Memory to Meet Multiclass Workload Response Time Goals”, The 18th International

Conference on Very Large Databases, August 1993, (with K. Brown and M. Carey). “Conceptual Schemas: Multi-Faceted Tools for Desktop Scientific Experiment Management”, to

appear in the International Journal of Intelligent and Cooperative Information Systems, (with Y. Ioannidis).

“The Impact of Autocorrelation on Queueing Systems”, Management Science, Vol, No. 3, March

1993 (with B. Melamed and A. K. Tsiolis). “Paring: A Token Ring Local Area Network with Concurrency”, IEEE Transactions on Commu-

nication, April 1992, (with Y. Qu, and L.H. Landweber). “On Transaction Boundaries in Active Databases: A Performance Perspective”, IEEE Trans. on

Knowledge and Data Engineering, September 1991, (with M. Carey and R. Jauhari). “Making Workstations a Friendly Environment for Batch Jobs”, Proc. of the third Workshop on

Workstation Operating Systems, April 1992, (with M. Litzkow).

John M. Norman

University of Wisconsin - Madison Department of Soil Science Madison, WI 53706 (608)262-4576 norman@calshp.cals.wisc.edu

EDUCATION Ph.D., Soil Science, University of Wisconsin-Madison, 1971.

Dissertation Topic: “Sunfleck-Size and Light-Intensity Distributions in Plant Canopies” Dissertation Advisor: “Champ B. Tanner”

M.S., Soil Science, University of Minnesota, St. Paul, MN, 1967. B.S., Physics, University of Minnesota, Mpls., MN, 1964.

RESEARCH AND PROFESSIONAL EXPERIENCE University of Wisconsin-Madison, Depart-

ment of Soil Science, Professor, September, 1988 - present. University of Nebraska-Lincoln, Department of Agronomy, Professor, August, 1978 - August 1988.

Pennsylvania State University, Department of Meteorology, Associate Professor September 1975-1978, Assistant Professor September 1972-1975. University of Aberdeen, Aberdeen, Scotland, Botany Department, Research Fellow, March 1971 - May 1972.

SELECTED RECENT PUBLICATIONS “Instrumentation For Studying Vegetation Canopies For Remote Sensing In Optical And Thermal Infrared Regions”, Harwood Academic Publishers, London, 360 pp. November 1990. (Edited with N.S. Goel).

“Biospheric Models, Measurements And Remote Sensing Of Vegetation”, ISPRS J. Photogram-

metry and Remote Sensing, Vol 47, pp. 163-188, 1992, (with N.S. Goel). “Scaling Processes Between Leaf And Canopy Levels”, Scaling Physiological Processes: Leaf To

Globe, eds J.R.Ehleringer and C.B.Field, Academic Press, Inc. New York. pp. 41-76. 1993, “Soil Surface CO2 Fluxes And The Carbon Budget Of A Grassland”, J. Geophys. Res. Vol 97,

pp. 18,845-18,853, (with R. Garcia and S.B. Verma). “Photon Transport In Discontinuous Canopies: A Weighted Random Approach”, Photon-Vegetation

Interaction: Application In Optical Remote Sensing And Plant Ecology, eds. J. Ross and R. Myneni, pp. 389-414., 1991 (with J.M. Welles).

“Leaf Bidirectional Reflectance And Transmittance In Corn And Soybean”, Remote Sensing of

Environment, Vol 29, pp. 161-174., 1989, (with E.A. Walter-Shea and B.L.Blad). “Contrasts Among Bidirectional Reflectance Of Leaves, Canopies And Soils”, IEEE Trans. On

Geoscience And Remote Sensing, Vol GE-23, pp.659-667, September 1985, (with J.M. Welles and E.A. Walter).

“From Artificial Life To Real Life: Computer Simulation of Plant Growth”, International J. General Systems, Vol 18, pp. 291-319, 1991, (with N.S. Goel and L.B. Knox).

Raghu Ramakrishnan

University of Wisconsin, Dept. of Computer Sciences Madison, WI 53706, (608)262-9759, raghu@cs.wisc.edu

EDUCATION Ph.D., Computer Science, University of Texas at Austin, May 1987.

RESEARCH AND PROFESSIONAL EXPERIENCE University of Wisconsin-Madison, CS Dept.,

Associate Professor, September, 1992 - present. University of Wisconsin-Madison, CS Dept., Assistant Professor, July, 1987 - August 1992. Editorial Board: Journal of Logic Programming (JLP), Journal of Constraints, Journal of Intelli-

gent Information Systems (JIIS). Program Committee Member: Databases (PODS, SIGMOD, VLDB, ICDE, PDIS, CIKM, DOOD,

EDBT) and logic programming (ICLP, ILPS, NACLP).

AWARDS NSF Presidential Young Investigator, 1990 - 1995, Packard Fellowship in Science and Engineering, 1989 - 1994, IBM Faculty Development Award, 1988 - 1990.

SOFTWARE DEVELOPED The CORAL deductive system. Source code in C++ for CORAL is

available freely, and is now installed at several universities and research labs. The Minibase DBMS. Currently in beta-tests with Ramakrishnan’s database text at several

schools. Includes a relational DBMS plus several visualization tools. The DEVise visualization tool and the BIRCH clustering tool. These are available in beta versions,

and were developed jointly with Prof. Livny.

SELECTED RECENT PUBLICATIONS M. Cheng, M. Livny, and R. Ramakrishnan, “Visual Analysis of Stream Data”, Proc. SPIE Conf. on Visual Data Exploration and Analysis, 1995.

R. Ramakrishnan and J.D. Ullman, “A Survey of Deductive Database Systems”, Journal of Logic programming, Vol. 23, No. 2, 1995.

P. Seshadri, M. Livny and R. Ramakrishnan, “Sequence Data Processing”, Proc. ACM SIG-MOD Intl. Conf. on Management of Data, 1994.

R. Miller, Y. Ioannidis and R. Ramakrishnan, “Translation and Integration of Heterogeneous Schemas: Bridging the Gap between Theory and Practice”, Information Systems, Vol. 19, No. 1, 1994. (Also in Proc. EDBT 93, and received the best paper award.)

J.F. Naughton and R. Ramakrishnan, “How to Forget the Past Without Repeating It”, Journal of the ACM, Vol. 41, No. 6, 1994.

R. Ramakrishnan, D. Srivastava and S. Sudarshan, “CORAL: A Database Programming Language”, Proc. VLDB, 1992.

R. Ramakrishnan. “Magic Templates: A Spellbinding Approach to Logic Programs”, Journal of Logic Programming, Vol. 11, No. 3, Oct. 1991.

I.S. Mumick, S. Finkelstein, H. Pirahesh and R. Ramakrishnan, “Magic is Relevant”, Proc. ACM SIGMOD Intl. Conf. on Management of Data, 1990.

F. Bancilhon and R. Ramakrishnan, “An Amateur’s Introduction to Recursive Query Processing Strategies”, Proc. ACM SIGMOD Intl. Conf. on Management of Data, 1986. Reprinted in “Readings in AI and Databases”, Eds. M. Brodie and J. Mylopoulos, 1988, pp. 376-430.

8 Bibliography

References

[A94] R. Agrawal. Tutorial: Data Mining. In Proceedings of the ACM PODS Conference, 1994.

[AS94] R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, 1994.

[AS96] Rakesh Agrawal,Ramakrishnan Srikanth. Mining Sequential Patterns: Generalizations and Improvements, In 5th Intl. Conference on Extending Database Technology, Avignon, France, 1996.

[CLR95] M. Cheng, M. Livny, and R. Ramakrishnan. Visual Analysis of Stream Data. In Proceedings of the IS&&T SPIE Conference on Visual Data Exploration and Analysis, San Jose, 1995.

[FMR94] C. Faloutsos, M. Ranganathan, Y. Manolopoulos. Fast Subsequence Matching in Time-Series Databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, 1994.

[FMMT96] T. Fukuda, Y. Morimoto, S. Morishita and T. Tokuyama. Data Mining Using Two-Dimensinal Optimized Association Rules: Scheme, Algorithms, and Visualization. In Proceedings of the ACM SIGMOD Conference on Management of Data, 1996.

[GRSY96] J. Goldstein, R. Ramakrishnan, U. Shaft and J. Yu. Using Constraints to Query R^{∗}-Trees Technical Report No. 1301 , Comp. Sci. Dept., Univ. of Wisconsin-Madison, 1996.

[HPSDBV94] W.L. Hibbard, B.E. Paul, D.A. Santek, C.R. Dyer, A.L. Battaiola and M-F. Voidrot-Martinez. Interactive Visualization of Earth and Space Science Computations. IEEE Computer, 27(7):65–72, July 1994.

[CU89] D. Kamins, C. Upson, Thomas Faulhaber Jr. The application visualization system: A computational environment for scientific visualization. IEEE Computer Graphics & Application, 9(4):30–42, July 1989.

[LLM88] M. Livny, M. Litzkow, and M. Mutka. Condor—A Hunter of Idle Workstations. In Proc. of the 8th Int. Conf. on Distributed Computing Systems, San Jose, CA, 1988.

[LL90] M. Livny and M. Litzkow. Experience with the Condor Distributed Batch System. In Proc. of the IEEE Workshop on Experimental Distributed Systems, Huntsville, AL, 1990.

[RSS92] R. Ramakrishnan, D. Srivastava, and S. Sudarshan. CORAL: Control, Relations and Logic. In Proceedings of the International Conference on Very Large Databases, 1992.

[RSSS93] R. Ramakrishnan, D. Srivastava, S. Sudarshan, and P. Seshadri. Implementation of the CORAL deductive database system. In Proceedings of the ACM SIGMOD Conference on Management of Data, 1993.

[SLR95] P. Seshadri, M. Livny and R. Ramakrishnan. Sequence Data Processing In Proceedings of the ACM SIGMOD Conference on Management of Data, 1994.

[Sno87] R. Snodgrass. The Temporal Query Language Tquel. ACM Transactions on Database Systems, 12(2):247–298, June 1987.

[ZRL96] T. Zhang, R. Ramakrishnan, and M. Livny. BIRCH: A Clustering Algorithm for Large Multidimensional Datasets. In Proceedings of the ACM SIGMOD Conference on Management of Data, 1996.