IDFL

April 1 - June 30, 1996 (FY96Q3)

Goals: Setup experimental platform. Begin implementation of database in conjunction with display development. Begin identification of techniques for representation of spatial and temporal uncertainty. Continue research on techniques for representing spatial and temporal uncertainty. Begin exploring the impact of uncertainty to query processing. Begin implementation of techniques for uncertainty management in databases. Design experiments to evaluate the representation and query processing strategies.

Progress: Equipment was ordered for the experimental setup and for use as the database server. The database system used in the initial testbed will be Illustra which has also been ordered.

We conducted a literature survey on mechanisms for representing spatial uncertainty in data and processing uncertain queries. We have begun developing mechanisms for handling uncertainty in queries to answer fuzzy concept-based queries over interpreted image databases.

July 1 - September 30, 1996 (FY96Q4)

Goals: Set up experimental platform. Design experiments to evaluate the representation and query processing strategies. Complete initial implementation of battlefield database. Conduct experiments to evaluate the techniques developed for managing uncertainty and report the results of the evaluation.

Progress: In this quarter, we received and installed our experimental platform consisting of a Sun Enterprise 3000 database server and the Illustra database management system. Several meetings were held with the display and information filtering teams to continue discussions on the database testbed. The consensus was to use the terrain and other feature data from Fort Irwin for the Annual Fed Lab Symposium demo. These data are available through the Geographic Modeling Systems Laboratory at UIUC. Research on representing spatial uncertainty models was continued. A literature survey on uncertainty in spatial relations and spatial query languages was conducted.

Research has started on supporting dynamic database.

The original goal to have the experimental database installed and to conduct experiments on the testbed this quarter was delayed due to the late arrival of some hardware and software. We designed the experiments to evaluate representation and query processing strategies. Due to the delay in the setup of the experimental platform, we substituted testbed development with research activity on supporting dynamic databases, which was originally scheduled for FY97.

October 1 - December 31, 1996 (FY97Q1)

Goals: Complete first phase of the design of experimental battlefield database suited for information processing and visualization. Complete analysis of problems in concurrency control and recovery in supporting dynamic access to multidimensional data in military databases.

Progress: We conducted extensive studies in identifying the problems due to concurrency control and recovery in multidimensional access methods. A large amount of literature was surveyed. The problem of concurrency control consists of two interrelated problems. The first is the development of mechanisms to support concurrent operations on the data structures. The second is the development of techniques for protecting search regions from concurrent insertions and deletions (phantom problem). We have so far focused on developing techniques to protect search ranges from phantom insertion and deletions and devised many approaches to solve the problem. Reports on our initial work will appear as a poster at the 1997 Annual Fed Lab conference and have been submitted for publication in the Very Large Database conference.

Our work on designing a database for visualization and information processing applications continued. A UIUC student continued work on an interface design to access spatio-temporal databases from virtual reality and immersive environments.

With respect to our work on uncertainty management, we are examining two natures of uncertainty. The first is the geo-spatial uncertainty in the underlying battlefield information. Representation of such uncertainty and its impact on the spatial relationships is being addressed and a preliminary analysis appears in Johnston and Ellis (1997). The second nature of uncertainty being examined is on representation, impact and processing of fuzziness in the underlying queries. This work has primarily been considered support for content-based queries in databases and has been done in the context of multimedia information retrieval. More recently, however, the work has been extended for multimedia enhanced geographical information retrieval.

Based on the extension, a demo was developed and will be displayed in the 1997 Annual Fed Lab Symposium. We are currently examining integration of the developed algorithms with the information filtering and processing tasks in facilitating the information processing pipeline.

January 1 - March 31, 1997 (FY97Q2)

Goals: Report on existing approaches to uncertainty representation and management within spatial databases.

Progress: We are preparing a draft report covering our work to date on representation of spatial relations. We detail the definitions of 2-d relations using first-order logic and present definitions for primitives and compound relations for distance, direction, and spatial configuration of database objects. The current focus of efforts is on detecting movement of entities over time. Uncertainty in location and identification is incorporated into these relations through qualitative reasoning.

A first step towards 2-d relations is presented in our prototype terrain matching system. This system allows for specifying first-order logic expressions over different domains of a geographical area. Domains include satellite imaging bands, topographic elevation data and synthetic aperture radar data and others may be added later.

Figure 1 shows an example of this prototype. This screen allows a user to select a domain, which will be converted into a predicate in the expression. Subsequent screens (not shown) allow the user to graphically construct more complete first-order logic expressions over the available domains.

Figure 1: Terrain similarity matching tool for specifying first-order logic expressions over different domains of a geographical area.

Figure 2 shows the results for such a completed query. The resulting selected area is color coded from red (best match) towards blue (worst match).

Figure 2: Query results of terrain feature matching based on satellite imagery.

Currently we are also exploring how to map a higher level concept onto a lower level expression over differing domains. This task requires collaboration with domain experts since in the absence of automatic learning techniques for this domain, an expert will need to instruct such mappings.

April 1 - June 30, 1997 (FY97Q3)

Goals: Report on existing approaches to uncertainty representation and management within spatial databases. Report on initial algorithms for supporting concurrent access to multidimensional database. Complete investigation of the application of existing approaches of uncertainty representation to military projects.

Progress: We made significant advances in our work on representation of uncertainty in dynamic military environments, algorithms to support concurrent operations on multidimensional data structures to support dynamic environments, techniques for indexing high-dimensional non-Euclidean spaces, and similarity-based retrieval over imprecise feature-based multimedia databases.

New approaches to spatial modeling have been developed in part as a response to a number of problems inherent in standard database implementations including transformational impedance, and partial and uncertain information. The objective of this line of research is to accommodate data obtained from different sources and at different levels of granularity while balancing the computational load of the database with the cognitive load of the user.

Commercially available databases are deficient in the representation of spatial relations and uncertainty in data. Database systems typically feature simple topological relations of intersection, inclusion, and exclusion, and very basic two dimensional Euclidean distance calculations. We suggest that the transformational burdens of coordinate conversion and spatial relations will interfere with the ability to maintain situational awareness by the user.

To address this shortcoming we are developing a language of spatial relations based on Tarski's (1941) "Calculus of Relations". The functions and operations defined in these relations are built on top of existing database functions and extend their utility. To date, we have developed a set of primitives for representing distance, direction and temporal characteristics of database objects. The extension into temporal representation has not been well addressed in the literature. While we are taking a relatively fundamental approach at this time, it is obviously essential for dynamic databases. Future work will address more advanced approaches to temporal representation.

A fundamental goal of this research, building on the extended functionality of existing databases, is to examine the affect of using a language of spatial relations in reducing the cognitive load of users attempting to build mental models of geographic space and objects within it. We have developed an experimental protocol to examine the contribution of spatial reasoning in conjunction with different display modalities to spatial awareness built from database query. We have implemented a two-factor-between- subjects and three-factor-within-subjects design. The experiment assesses user performance in various tasks associated with constructing comprehension of a dynamic geographic environment. We will initiate the experiment in the fourth quarter.

The problem of concurrent operations over multidimensional data structures consists of two parts; the supporting of concurrent operations over the data structures without violating its consistency, and protecting data accesses via the data structure from phantom insertions and deletions.

We designed the first dynamic granular locking approach to phantom protection in R-trees which we believe is the first practical solution to integrating R-trees into databases suited for highly dynamic database environments. A report based on the developed algorithm has been submitted for outside publication. We also implemented our algorithms and are currently testing them for their effectiveness. The developed algorithms can be generalized to support concurrent access via other data structures including the generalized search tree template which can be used to implement a variety of data structures in a database. We are investigating this research avenue since that will increase the scope and applicability of our algorithms significantly.

Besides the aforementioned work, we continued our research on content-based retrieval in multimedia databases. Significant progress was made in adapting and extending existing information retrieval techniques for feature based retrieval over multimedia databases based on which many papers were submitted for outside publication.

We also conducted research on efficient techniques for indexing highly multidimensional feature spaces which may be defined over non-Euclidean spaces. We identified various strategies of dealing with the high-dimensionality and non-Euclidean nature of feature spaces. We explored clustering as an indexing mechanism for such feature spaces and developed a clustering algorithm and a retrieval approach which offers good performance. We are currently writing a report based on this work.

We also started a large effort in building a prototype database management system that provides effective and efficient storage and content-based retrieval of complex multidimensional data as in multimedia information, satellite imagery, etc. Over the past year, we have conducted significant amount of research on developing strategies to build such a system on top of existing commercial object-oriented databases. Our conclusions are that existing database management systems are deficient in many regards and are not extensible enough to support the requirements posed by such emerging applications. Motivated by this, we launched an effort to build a new object-oriented database management system prototype that provides seamless support to complex multidimensional objects capable of storage and retrieval based on their content.

The system includes next-generation multimedia information systems, geographical information retrieval systems, as well as many command and control database applications. Many discussions were held with Army Research Laboratory visitors during the quarter regarding the possibilities of deploying the system being built for Army database needs.

July 1 - September 30, 1997 (FY97Q4)

Goals: Complete development of new algorithms to support concurrent access to spatial multidimensional database. Report on initial algorithms for uncertainty management in military databases.

Progress: We extended the algorithm for granular locking in R-trees to GiST data structure. R-trees are balanced, paginated, multidimensional data structures. GiST is a template-based, multidimensional data structure (generalized search tree), which is becoming popular because it can simulate a number of other multidimensional data structures, including R-trees. With GiST, the access method implementor does not need to write complex structural maintenance code and, hence, does not need to have any familiarity with server specific buffer management, concurrency control, and recovery protocols. Our algorithm will be presented at the 2nd Annual Fed Lab Symposium in February 1998.

We began designing an experiment to test the fundamental abilities of a Spatial Query Language to reduce the cognitive effort currently needed to perform spatial queries; and to reduce decision making errors, resulting from false assumptions of spatial accuracy due to uncertainty in spatial data (Figure 3). The experiment implements spatial query functions based on distance, direction, and time in a simulated user interface, and subsequently observing user performance.

Figure 3: Test design for comparing the interaction effects of display modality and spatial reasoning procedures on subject's ability to identify spatial relationships between displayed objects.

Three information retrieval tasks - distance (ds), direction (dr), movement (mv), and one judgment task - are being manipulated within three levels of representation (numeric, 2-D graphic, 3-D graphic) and two levels of support (No QSR, QSR), shown in Figure 4. QSR, or Qualitative Spatial Reasoning, is an approach to representing spatial relationships through topological structures between data objects, in which constructs are built on primitives based on distance, direction, and temporal measures. Descriptions of higher level relationships and configurations of individual spatial objects are enabled, and a more direct mapping between a user's cognitive models of space and spatial relations between data objects and display representation is claimed.

Figure 4: Depiction of the application in the experimental setting of display tools that make the spatial relationships between objects explicit. Because of display distortions (especially in 3-D displays), errors in spatial judgment regarding relative position of objects (for example) are hypothesized to be compensated for by development of query tools that explicitly portray the spatial relationships between objects. This approach is hypothesized to reduce attentional requirements of the user, enabling a richer display environment than would otherwise be possible.

Treatments are being counterbalanced to control for ordering effects. This study is a "two-factor within subjects by three factor between subjects" design, which is the experimental design protocol used in testing display modalities involving qualitative spatial reasoning. Basically, the protocol states that we will apply several different ways of displaying geospatial information (tabular, 2-D, 3-D) x two different applications of the QSR (with and without). The order in which subjects undertake tasks (spatial reasoning tasks with and without QSR) is varied to make sure differences in subject performance are not because they become familiar with the problem, or the interface, etc.

We have defined a new research direction towards developing a general technique for managing uncertainty and imprecision in databases. They will be exploring the viability of the proposed approach for spatial reasoning and multimedia databases (two database applications in which not only is the information uncertain, but the underlying query and processing techniques may themselves not be precise) in the upcoming year.

October 1 - December 31, 1997 (FY98Q1)

Goals: Report on display modality experiments with spatial relation language support. Perform analysis of requirements for spatial reasoning to support conceptual queries for information processing and battlefield visualization tasks. Extend approaches to phantom protection over R-trees to GiST-based multidimensional data structures to support dynamic multidimensional data sets. Complete a cost-based analysis of tradeoffs between frequent position updating of moving battlefield objects versus deviation cost from the current object location. Define cost-based position update policies for moving objects. Determine techniques to incorporate position update policies developed into an active database architecture.

Progress: Christopher Ellis, PhD. candidate, completed his dissertation, "The Effectiveness of Qualitative Spatial Representation in Supporting Spatial Awareness and Spatial Decision Making". The dissertation extended work in representation of basic spatial relations, such as distance and direction, to include temporal elements of time (movement) and domain contexts (battlefield situational awareness). An experiment was implemented testing users spatial judgment skills across a range of tasks, and in several display modalities. Figure 5 shows an interface with displays using spatial relation display support. Performance (spatial judgment) deteriorated as spatial relations became more complex (distance, direction, movement, "threat", "tactical decision"), as seen in Figure 6. Performance also deteriorated when display modality was switched from 2-D exocentric to 3-D exocentric. Inclusion of spatial relation language support provided significant improvements in all spatial relation tasks, and appears to compensate for distortions introduced by 3-D exocentric displays. Subject spatial skill variability was not a factor, as measured by a standard 3-D rotation test. Five papers focusing on aspects of this work are under development.

Figure 5: The interface showing displays using spatial relation display support.

Figure 6: Comparison of results from subject testing, showing performance differences in spatial judgment tasks between 2-D and 3-D display modalities and with/without spatial relation display support.

Work has been initiated on the analysis of requirements to expand spatial reasoning language primitives to support higher level domain-dependent reasoning tasks.

Approaches were extended to phantom protection over R-trees to GiST-based multidimensional data structures to support dynamic multidimensional data sets. A paper based on the completed work was submitted for publication to the ACM SIGMOD conference. A poster demonstration of this work will be included in the upcoming ARL conference.

A paper summarizing the results a cost-based analysis of tradeoffs between frequent position updating of moving battlefield objects versus deviation cost from the current object location will appear in the IEEE ICDE conference. A simulation system that supports the analysis also has been developed.

Work defining cost-based position update policies for moving objects has been completed. A paper summarizing the results has been submitted for publication. We developed and analyzed location-update policies that encapsulate the cost of database-location deviation, the cost of location uncertainty, and the cost of location updating.

The techniques to incorporate position update policies developed into an active database architecture have been determined and a paper will appear in the book "Temporal Databases". We devised a scheme of implementing location update policies using triggers.

January 1 - March 31, 1998 (FY98Q2)

Goals: Perform requirements analysis for spatial reasoning to support conceptual queries for information processing and battlefield visualization tasks (Q198). Provide initial report on algorithms to evaluate conceptual queries to support information filtering and visualization tasks in battlefield environments. Provide storage and implementation of terrain feature database into the Informix database management system to support visualization tasks.

Progress: Based on the outcomes of the experiments conducted this winter, we know spatial reasoning is a likely benefit in both database query and visualization support. We also know, however, the richness of database queries is a function of echelon focus, domain task (intelligence, vs operations, etc) and other factors; we need to conduct a great deal more work to enable a richer query interface. The visualization requirements are much more focused. We will need to expand our experiments into the virtual display domain to completely specify the visual objects to represent spatial relations among database objects.

Our research assistant, Chris Ellis, successfully defended his dissertation, "The Effectiveness of Qualitative Spatial Representation in Supporting Spatial Awareness and Spatial Decision-Making". The dissertation points to the opportunities to use conceptual queries in information filtering, and in compensating for spatial distortions introduced in 3-D display environments. We are currently at work on several papers drawn from the dissertation, and the next goal is to expand the conceptual queries into a richer set to incorporate more domain functions.

We successfully stored the Army Historical Archive System (AHAS) data, which will be used to drive the visualization into the Informix database management system. Next, we are going to build software to drive VGIS using the AHAS data. To support this work, we will integrate the Informix system with the indexing mechanisms and concurrency control mechanisms developed earlier.

April 1 - June 30, 1998 (FY98Q3)

Goals: Complete initial implementation of algorithms for evaluating conceptual queries for filtering and visualization, and develop example applications. Integrate GiST based phantom protection techniques with techniques for concurrency control and recovery for a solution to dynamic, concurrent, multidimensional access methods. Explore clustering as an access mechanism for retrieving high-dimensional data sets.

Progress: Algorithms for specifying a limited set of conceptual queries have been completed and implemented within a commercial database management system (DBMS). Completion of example applications is pending, based on the need for project staff replacements.

Dynamic granular technique for GiST based data structures have been developed. A report based on the algorithms developed has been written. The developed algorithms are being integrated into the existing GiST code to support dynamic concurrent multidimensional access methods. Also, the developed mechanisms are being integrated into the VGIS system to support an index over the objects database in VGIS.

Our initial experiments with clustering as an approach to indexing high-dimensional data sets were not very encouraging. Instead, we explored a new approach to indexing multidimensional data: hybrid tree. Our experiments show that the developed approach scales to much higher dimensionality compared to all previous methods especially for nearest neighbor searches. Essentially, the approach attempts to combine the best features of space partitioning approaches (e.g., kd tree) and object clustering approaches (e.g., R-tree) into a single data structure. A report based on the results is being prepared. It will be made available after some more robust experiments with respect to its scalability under different conditions has been explored.

Additionally, during this quarter we initiated research on integrating our work on multidimensional indexing into VGIS. The SATURN system is the spatio-temporal uncertainty reasoning system. It supports mechanisms for multidimensional indexing, representation of spatio-temporal uncertainty and query processing. We are currently integrating VGIS system with the indexing mechanisms of SATURN to effectively support moving objects in VGIS.

We are exploring using the developed indexing mechanisms to support moving objects in 3-D visualization. Currently, the frame rate of VGIS drops to less than a frame per second when there are over a few hundred objects located in the terrain. We are exploring usage of the indexing mechanism to precull the objects not in the field of view within the object server in order to reduce the culling that the renderer has to perform. In the current implementation, the object server pushes all the objects (irrespective of whether or not they are in the view) to the renderer which then culls the objects not in view. We expect our approach to perform significantly better and to improve the frame rate and scalability of VGIS to larger object databases. Our initial experiments validate our claims.

July 1 - September 30, 1998 (FY98Q4)

Goals: Complete initial implementation of algorithms for evaluating conceptual queries for filtering and visualization, and develop example applications.(Q398). Integrate GiST based phantom protection techniques with techniques for concurrency control and recovery for a solution to dynamic, concurrent, multidimensional access methods.(Q398). Provide an initial report on a query language design to integrate conceptual similarity-based queries into DBMS query processing. Conduct experiments to determine effectiveness of spatial reasoning techniques for conceptual queries in visualization and intelligent information processing tasks. Perform initial integration of COA generator with the terrain feature database to drive the COA generation.

Progress: The first, third, and fourth milestones were deferred pending filling of a vacant staff position. The third milestone was also deferred since the current course of action (COA) generator (Fox) is undergoing a significant modification in its design and extensibility. Our objective for this task was to illustrate the usefulness of the spatio-temporal indexing mechanism in supporting COA generation. Since the current Fox is limited in the nature of COAs it generates and is undergoing modification, we implemented a disaster relief task instead. The task is to plan a search for a missing vehicle (e.g., a crashed airplane) using VGIS and SATURN system.

We have developed the software for integrating GiST based phantom protection techniques with techniques for concurrency control and it is currently being debugged and tested.

Prof. Sharad Mehrotra (UIUC) worked on the development of SATURN technology for indexing spatio-temporal objects, integrating SATURN's indexing mechanism to VGIS in order to support efficient object preculling (see Figure 7). This improved VGIS performance and scalability, as did the development of a monitor for VGIS, which attempts to ensure quality of service in the VGIS display.

Figure 7: Integration plan for VGIS and SATURN.

Prof. Ouri Wolfson (UIC) worked on the Moving Objects databases. Work was conducted on distributed update policies, by which moving objects update their location in a distributed database. The database is distributed among the moving objects that are interconnected by a wireless unreliable network. Also, Dr. Wolfson worked on indexing the location of moving objects. This research was conducted by supplemental funds from ARL.

October 1 - December 31, 1998 (FY99Q1)

Goals: Complete initial implementation of algorithms for evaluating conceptual queries for filtering and visualization, and develop applications. (Reported as incomplete FY98Q3). Provide an initial report on a query language design to integrate conceptual similarity-based queries into DBMS query processing. (Reported as incomplete FY98Q4). Conduct experiments to determine effectiveness of spatial reasoning techniques for conceptual queries in visualization and intelligent information processing tasks. (Reported as incomplete FY98Q4). Perform initial integration of COA generator with the terrain feature database to drive the COA generation. (Reported as incomplete FY98Q4). Develop experiments testing spatial reasoning techniques for conceptual queries. Perform an initial integration of spatial reasoning visualization tools for conceptual queries to the database. Exploration of applications to demonstrate utility of Spatio-Temporal Uncertainty reasoning (SATURN) system to battlefield visualization and situational awareness tasks.

Progress: Work on the first two milestones is still pending due to lack of staffing.

We have developed visualization tools for rendering spatial relations in a dynamic, immersive 3D-display environment. This is an extension to work done for static 2D display. We are experimenting with rendering techniques to maintain performance with large numbers of displayed dynamic objects (order 10^3). These tools will subsequently be used in human subject testing of spatial reasoning skills.

The initial integration of a Course of Action (COA) generator with the terrain feature database to drive the COA generator has been deferred as explained in the previous quarterly progress report.

We are coding extensions of the 2D-display experiment for use in 3D stereo. This version will be available for conducting experiments during the 3rd quarter of FY99.

Regarding the initial integration of spatial reasoning visualization tools for conceptual queries to the database: We have coupled the display environment to a database of time-stamped object positions for dynamic rendering of object locations and spatial relationships relative to other objects. We are working to enrich the functions of display.

We explored utilizing SATURN's indexing and dynamic object representation techniques to support effective visualization. With the help of additional funds made available by ARL, SATURN's indexing techniques were integrated with VGIS and were used to manage the dynamic AHAS and weather objects (Figures 8 and 9). We will further explore other applications for SATURN's support for imprecise queries to situational awareness and visualization tasks.

Figure 8: Original VGIS architecture before integration with SATURN.

Figure 9: VGIS architecture after integration with SATURN.

In other research, some additional funding provided by ARL, to support another database management task, was utilized as follows. We integrated the indexing and representation techniques of SATURN (Spatio-Temporal Uncertainty Reasoning system) with the Virtual GIS (VGIS) system in order to improve its performance and scalability to complex dynamic environments as well as to enhance its functionality as a collaborative planning tool. To achieve this we added three new components to VGIS: a spatio-temporal object manager, a performance monitor, and a task database. The spatio-temporal object manager uses SATURN techniques for indexing dynamic multidimensional (spatio-temporal) objects to support effective and efficient object traversal during visualization. The performance monitor adjusts the resource allocation between VGIS components and adaptively adjusts image quality to guarantee bounded visualization performance. The task database extends VGIS as a tool for collaborative planning.

Performance results illustrate that the SATURN techniques for object management and the performance monitor significantly improve VGIS performance allowing it to scale to complex scenarios with a large number of dynamic objects. Performance results will be reported in the 1999 Displays Federated Laboratory Symposium Proceedings. Simulating and storing information about a task of searching for a missing vehicle (e.g., crashed aeroplane) illustrated the utility of the task database during a disaster relief operation. Other planning and battlefield operations could also potentially utilize the task model implemented and will be explored in the future. The task database provides a mechanism to store, query, retrieve and manage such collaborative tasks in a database.

We also made significant progress on a related MARS project whose goal is to develop effective and efficient mechanisms to support complex multimedia information as first class objects in databases such that they can be stored and retrieved based on their content. In this context we explored the relevance feedback mechanism to learn user queries in multimedia databases, efficient techniques to evaluate imprecise content-based queries in multimedia databases, as well as techniques to content-based representation and retrieval of video.

January 1 - March 31, 1999 (FY99Q2)

Goals: Complete initial implementation of algorithms for evaluating conceptual queries for filtering and visualization, and develop applications (reported as incomplete FY98Q3). Provide an initial report on a query language design to integrate conceptual similarity-based queries into DBMS query processing (reported as incomplete FY98Q4). Perform initial integration of COA generator with the terrain feature database to drive the COA generation (reported as incomplete FY98Q4). Implement the query language to integrate conceptual similarity-based queries into databases. Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets.

We have designed a set of algorithms for clustering database objects into higher order classes based on spatial proximity and relative location. These algorithms are based on fundamental spatial operations with novel topologic relations computed from positional and object attribute information. We are currently implementing these operations within a spatial data analysis and management tool for immediate demonstration and testing.

The initial report on a query language design remains incomplete pending completion of the previous task.

The task of integrating a COA with the terrain feature database has been substituted with another task, as explained in the FY98Q4 report. As we mentioned in the FY98Q4, the purpose of this task was to demonstrate the usefulness of our work on representation, indexing, management of imprecise spatio-temporal data (SATURN) and the support for qualitative reasoning on spatio-temporal data. Since COA's are spatio-temporal objects, integrating our research with FOX in order to support COA generation and reasoning tasks seemed very attractive. However, at the time when this task had to be performed, FOX was exploring COA at the level and granularity for which our work on representing complex spatio-temporal objects was not required. In contrast, the underlying terrain database and army exercise data (AHAS) that drives VGIS provided us with a more suitable application to demonstrate our research in SATURN. We have therefore substituted this task with the task of integrating SATURN with VGIS to support both better performance of VGIS as well as to explore extended functionality to VGIS.

In terms of implementing a query language, we have developed a database server application to provide real-time communication between a database storing the temporal and spatial characteristics of battlefield objects with a virtual display environment built from our earlier 2 dimensional representational experiments. The battlefield objects are continuously updated in the display as their state changes according to the conceptual query structures being implemented (Figure 10). These results will be used in our experimental settings and can feed into the task below.

Figure 10: Query Structure

The integration of VGIS and SATURN is incomplete pending porting of VGIS to UC, Irvine. We expect to make progress over this task in the next quarter.

In other research, we have continued to make significant progress in the related MARS project that explores an integrated multimedia information retrieval and database management system with the objective of providing native support for and content based retrieval of multimedia objects in databases. Our progress has been in (1) techniques to support query refinement in MARS to map user's information need to an exact query representation, (2) techniques to support imprecise queries in databases, and (3) high dimensional feature indexing. During this period, we have developed a Web Search engine called WEB-MARS that supports an integrated retrieval using both textual descriptions (content) of HTML pages as well as visual content of images linked to the HTML. This is the first such search engine to truly combine text and visual properties into a single paradigm.

April 1 - June 30, 1999 (FY99Q3)

Goals: Complete initial implementation of algorithms for evaluating conceptual queries for filtering and visualization and develop applications (reported as incomplete FY98Q3).

Provide an initial report on a query language design to integrate conceptual similarity-based queries into DBMS query processing (reported as incomplete FY98Q4). Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets (reported as incomplete FY99Q2). Perform scaling studies of spatial reasoning in a large, multi-dimensional access methods developed in SATURN. Report on approaches to optimize conceptual queries using multi-dimensional access methods developed in SATURN.

Progress: A programmer has been hired to complete the implementation of algorithms and the task will be complete in summer 1999.

Ms. Michelle Yeh, a graduate researcher working with Prof. Doug Johnston has been hired to complete the query language design and subsequent report.

The integration of VGIS and SATURN's spatio-temporal indexing mechanisms is still incomplete since we have not been able to port VGIS to UC-Irvine. The task will be completed this summer.

Michelle Yeh under the guidance of Prof. Johnston will conduct and complete scaling studies during this summer.

A paper has been completed on approaches to optimize conceptual queries. It has been submitted to the upcoming ICDE conference. The paper illustrates how conceptual queries can be optimized for conceptual queries in the spatio-temporal domain. Another paper based on evaluating spatio-temporal queries over imprecise spatio-temporal locational information using multidimensional index structure is currently being written and will be completed mid July.

In other research, we made significant progress in the related MARS, SATURN, and DOMINO projects.

Multimedia Analysis and Retrieval System (MARS) is an integrated multimedia information retrieval and database management system which is being developed at the University of California, Irvine with the objective of providing native support for content-based retrieval over the multimedia objects in databases. The progress we made over the past quarter in the MARS project was along the following directions:

We explored information retrieval techniques to support combined retrieval using both text and image properties in a single retrieval paradigm. Experiments were conducted to validate the improvements that result when more than one media type are considered at the same time. The information retrieval techniques developed and the experiments resulted in two manuscripts that have been submitted for publication.

We explored efficient techniques to refine conceptual similarity queries in database systems. The idea is as follows: Consider that the user specifies a conceptual similarity query to the system which approximates their information need. The system evaluates the query and returns a set of answers. The user then provides a feedback to the system by possibly marking the set of answers returned by the system with the level of relevance of the answer to their information need. The system, based on the feedback, refines the query representation to improve the set of answers returned. We have, in the past, explored various models to support such a query refinement process. While the process has been explored in the context of multimedia similarity query, the approach applies to any general domain--specifically, the domain of spatio-temporal queries. In this quarter, we explored efficient mechanisms to evaluate such refinement queries. Done naively, the system needs to reevaluate the entire query from start per refinement. We explored techniques, which can be utilized to optimally reutilize the query evaluation in previous iterations to improve performance of successive refinement queries.

The Spatio-Temporal Uncertainty Reasoning System (SATURN) is a specialized database management system for storage, representation, indexing and querying of spatio-temporal information being developed at University of California, Irvine. A primary concern in SATURN is to develop effective database management techniques to support 3-d visualization of dynamic geographical spaces (e.g., battlefield simulations). The nature of data in such simulations is highly voluminous and dynamic. In the SATURN project, we have been exploring novel multidimensional indexing and concurrency control techniques for management of highly dynamic (rapidly changing) voluminous spatio-temporal data sets. In this quarter, we made significant progress towards query processing in dynamic geographical spaces. Specifically, we considered continuous query. Consider a vehicle (e.g., aeroplane) that navigates in the 3-d spatio-temporal space observing objects (mobile as well as stationary) in its view frustum. The view frustum of the observer is essentially a range query to the database storing spatio-temporal location of objects. Notice that the view frustum of the observer keeps changing as a function of time based on the motion of the observer. We developed efficient query processing techniques to dynamically maintain consistent and up-to-date information about objects in the view frustum of an observer as the observer navigates the 3-d space. The developed techniques provide an order of magnitude improvement over querying the database repeatedly to determine the set of objects in the view frustum. The techniques developed are of direct relevance to supporting effective and efficient visualizations in VGIS and BattleView. We will explore their effectiveness in this context in the following quarter.

Additionally, based on a suggestion from Bernie Corona during the June review, Dr. Sharad Mehrotra (UCI) has been working with Mr. Rob Stein and Dr. Polly Baker (UIUC) to explore the utility of the query processing techniques being developed in SATURN to the BattleView and the Boeing supported simulation database. Stein has provided Mehrotra with the simulation database as well as some queries with which they are having difficulty in real-time simulation and visualization. Jing Liu, a student working with Mehrotra has conducted initial experiments to evaluate SATURN techniques over the data set and queries provided. The results look very encouraging -- the same query, which takes about 5 minutes to run in Informix (a commercial database management system), runs in a few milliseconds in SATURN. More experiments will need to be done to further validate the effectiveness of using SATURN techniques.

DOMINO Project (UIC), Ouri Wolfson studied the problem of data replication in a wireless unreliable network in which a set of mobile computers (or nodes) communicate by broadcast messages. Each node i "owns" the master copy of a data item, i.e. it generates all the updates to . This is called a "master" replication environment. For example, may be the latest in a sequence of images taken periodically by the node i of its local surroundings. Each new image updates . Or, may be the location of the node which is moving; is updated when the Global Positioning System (GPS) on board the node i indicates a current location that deviates from by more than a prespecified threshold. The database of interest is D =,..., where n is the number of nodes. Each node has a local copy of this database that may contain some inconsistencies, which are due to network unreliability. We devised a cost-based lazy-replication approach to controlling and minimizing the inconsistency of each local database. We compared our solution to two relatively naive approaches to solve the same problem.

July 1 - September 30, 1999 (FY99Q4)

Goals: Complete initial implementation of algorithms for evaluating conceptual queries for filtering and visualization, and develop applications. (Reported as incomplete FY98Q3.) Provide an initial report on a query language design to integrate conceptual similarity-based queries into DBMS query processing. (Reported as incomplete FY98Q4.) Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets. (Reported as incomplete FY99Q2.) Perform scaling studies of spatial reasoning in a large, multi-dimensional battlefield terrain database. (Reported as incomplete FY99Q3.)Report on scaling studies in battlefield terrain database. Conduct display modality experiments using immersive display technologies. Initial integration of conceptual query framework (including optimization algorithms) into the SATURN system.

Progress: Implementation of algorithms was completed as part of the work leading to our display modality/query support tool experiments in FY99. These algorithms were reported in the dissertation written by Chris Ellis (August, 1998): "The effectiveness of qualitative spatial representation in supporting spatial awareness and spatial decision making."

Initial evaluation of the use of query support language and tools has been completed. Work has focused on analyzing data produced from the experiments conducted by Chris Ellis. Specifically we were looking at use patterns of query tools relative to performance. This expands upon the research question of whether or not query tools improve spatial judgments in multi-modal geographic representations, and begins to explore the how's and why's of the shown improvement. The work is important in improving the ability of software systems to support queries made complex because of the dynamics of data and the complexity of display environments.

The display modality experiments are not yet complete due to staffing problems. In this experiment, users first perform tasks using a qualitative spatial representation display, and then with a qnq, 2Dqnq or 3Dqnq display. What we have found, in summary, is there is a significant effect of question type in determining what interface features subjects use, and the results are consistent with what would be expected (e.g., distance functions are used more when the question is a distance question, etc.). The distance functions actually played a large role. Subjects accessed these functions more in the 2Dqnq display condition than in the other conditions. There were not a large number of movement or threat function selections. When the questions got difficult, subjects accessed the direction functions more than when the questions were easier. Subjects seemed to access the direction functions more when they were in the numerical condition than in the 2D or 3D conditions.

Subjects found the direction functions most useful for answering these questions. For the distance functions, there was no effect of display, but a significant effect of question difficulty. This latter finding occurred when the distance functions were accessed more and for a longer period of time, and most specifically when the questions were of medium difficulty. When subjects used the direction functions, they spent more time looking at the results when the questions were easy or of medium difficulty than when the questions were hard, and they spent more time looking at these results when they were in the qnq and 3Dqnq display conditions. There were no effects for the movement or threat functions.

The integration of VGIS and Saturn is still incomplete since we have not been able to bring VGIS to UC, Irvine. There are plans to do so sometime in October 1999 at which point we should be able to complete the task.

Initial work in scaling studies has consisted of the development of an application for the visualization of large numbers of dynamic objects within an immersive environment (moving the environment closer to VGIS and other specifications). Visualization performance studies using a distributed database piped to the rendering engine shows support of order 10^3 discrete objects without loss of frame rate (and therefore user's realtime interaction). This work is documented in part on our web site: http://www.gis.uiuc.edu/cave/GeoTracker/geotracker.htm.

A report on the scaling studies has been delayed, as the studies are not yet complete.

The integration of conceptual query framework into SATURN is deferred until the framework for conceptual queries is fully developed. We plan to have this completed by the end of the contract period.

In other research, we made significant progress in the related MARS and SATURN projects:

We built a prototype multimedia search engine for the World Wide Web on top of the MARS database entitles WebMARS. The developed system consists of a web crawler, HTML analyzer, image analyzer, an indexer, and the MARS similarity retrieval system. Unlike other research prototype and commercial search engines, WebMARS offers a much more flexible interface for browsing and retrieval, effectively merging both access paradigms into a single powerful mechanism, supporting refinement of user queries using relevance feedback, and a seamless integration of text and image properties for retrieval. Two research papers based on WebMARS were submitted for publication this period.

We built a prototype terrain similarity retrieval system using MARS to support similarity retrieval over terrain databases based on region footprints. The objective was to demonstrate the usefulness of image retrieval techniques to alleviate the task of generating maps of vector data (e.g., buildings, roads, rivers, etc.) from satellite imagery. The developed system captures regions at varying scales and represents them using texture and color properties.

Indexing techniques that scale to very high dimensionality by exploiting correlated clusters (that is, clusters which can be represented using lower dimensional subspaces without much loss of information) in the original data were developed. These are among the most scalable mechanisms for indexing high dimensional feature spaces and have applicability not only to similarity query processing, but also to high dimensional data analysis and data mining tasks.

A continuous query is a time varying sequence of spatio-temporal queries. The following example explains the continuous query. Consider a vehicle (e.g., aeroplane) that navigates in the 3-D spatio-temporal space observing objects (mobile as well as stationary) in its view frustrum. The view frustrum of the observer is essentially a range query to the database storing spatio-temporal location of objects. Notice that the view frustrum of the observer keeps changing as a function of time based on the motion of the observer.

Additionally, based on a suggestion from Bernie Corona during the June review, Dr. Sharad Mehrotra (UCI) has been working with Mr. Rob Stein and Dr. Polly Baker (UIUC) to explore the utility of the query processing techniques being developed in SATURN to the Battleview and the Boeing supported simulation database. Stein has provided Mehrotra with the simulation database as well as some queries with which they are having difficulty in real-time simulation and visualization. Jing Liu, a student working with Mehrotra has conducted initial experiments to evaluate SATURN techniques over the data set and queries provided. The results look very encouraging -- the same query, which takes about 5 minutes to run in Informix (a commercial database management system), runs in a few milliseconds in SATURN. A report based on these experiments has been written (Liu and Mehrotra 1999). At this stage, we are waiting on the input from either the visualization group and/or ARL about how to proceed with this work.

October 1 - December 31, 1999 (FY00Q1)

Goals: Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets. (Reported as incomplete FY99Q2.) Report on scaling studies in battlefield terrain database. (Reported as incomplete FY99Q4.) Conduct display modality experiments using immersive display technologies. (Reported as incomplete FY99Q4.) Initial integration of conceptual query framework (including optimization algorithms) into the SATURN system. (Reported as incomplete FY99Q4.) Complete written report on experiments comparing spatial judgement in 3D immersive environments conducted in 4^th quarter 1999. Expand and demonstrate database implementation and visualization of conceptual query functions representing multi-scalar abstractions and aggregation/disaggregation of database objects through the SATURN object oriented data structure.

Progress: In December 1999, UCI finally acquired the VGIS software necessary for integrating VGIS and SATURN. The integration effort is now underway and should be completed in the coming quarter.

Implementation of algorithms was completed as part of the work leading to our display modality/query support tool experiments in FY99. These algorithms were reported in the dissertation written by Chris Ellis (August, 1998): "The effectiveness of qualitative spatial representation in supporting spatial awareness and spatial decision making."

The integration of conceptual query framework into SATURN is deferred until the framework for conceptual queries is fully developed. We plan to have this completed by the end of the contract period.

The experiments comparing spatial judgement in 3D environments are still ongoing. The report will be available when the experiments are completed.

The expansion and demonstration of database implementation and visualization of conceptual query functions has not yet been completed. It will be completed in the following quarter.

We made progress along the following directions:

We developed a technical report describing how continuous queries are evaluated in SATURN. The report will be submitted for outside publication in the upcoming VLDB conference.

We developed an approach based on dimensionality reduction for high dimensional indexing in MARS. The approach differs from existing global dimensionality reduction approaches. Unlike them, it applies dimensionality reduction at local correlated clusters and achieves a performance that is orders of magnitude better compared to existing techniques. In fact, local dimensionality reduction, combined with our previous work on hybrid trees is among the most scalable techniques for high dimensional indexing in the literature.

We explored efficient query processing techniques for relevance feedback in MARS.

We have continued working on enhancing VGIS support for spatiotemporal objects and have implemented a sliding view window (figure 11). The approach is described in the paper "Database Support for Efficient Visualization" submitted to the ARL symposium.

Figure 11: Sliding view window implemented to enhance VGIS�s
support for spatiotemporal objects.

January 1 - March 31, 2000 (FY00Q2)

Goals: Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets. (Reported as incomplete FY99Q2.) Report on scaling studies in battlefield terrain database. (Reported as incomplete FY99Q4.) Initial integration of conceptual query framework (including optimization algorithms) into the SATURN system. (Reported as incomplete FY99Q4.) Complete written report on experiments comparing spatial judgement in 3D immersive environments conducted in 4^th quarter 1999. (Reported as incomplete FY00Q1) Expand and demonstrate database implementation and visualization of conceptual query functions representing multi-scalar abstractions and aggregation/disaggregation of database objects through the SATURN object oriented data structure. (Reported as incomplete FY00Q1) Complete implementation of SATURN indexing techniques to support moving objects in VGIS. The software will be provided to ARL and can be made an integral part of VGIS. The developed software can also be incorporated into BattleView (module 2.2.3.1) for scaling its performance.

Progress: The task of integration of VGIS with SATURN is still continuing. We expect to complete this quite soon now though. There were some added complications due to mismatch of the interface supported by SATURN's disk-based data structures and the memory-based data structures used in existing VGIS. The work should be completed by summer 2000.

Initial work in scaling studies has consisted of the development of an application for the visualization of large numbers of dynamic objects within an immersive environment (moving the environment closer to VGIS and other specifications). Visualization performance studies using a distributed database piped to the rendering engine shows support of order 10³ discrete objects without loss of frame rate (and therefore user's realtime interaction). This work is documented in part on our web site: http://www.gis.uiuc.edu/cave/GeoTracker/geotracker.htm. A report on the scaling studies has been delayed, as the studies are not yet complete.

In an earlier report, we mentioned that the integration of conceptual query framework into SATURN is deferred until the framework for conceptual queries is fully developed. We have begun implementation of a proof of concept database system that supports similarity queries in SATURN. The system supports extended SQL semantics in which similarity is captured via imprecise predicates -- (e.g., retrieve objects near my current location, where the predicate "near" may be an imprecise predicate). See our paper in the 1998 Fed Lab Symposium Proceedings and "Top K selections in databases based on user feedback" submitted for publication this quarter for detail. We intend to have this framework developed by end of contract period.

When the prototype is complete, SATURN will support imprecise queries -- our hope is that SATURN's imprecise queries model will be powerful enough to support the full spatio-temporal conceptual query framework being developed as a separate effort.

The experiments comparing spatial judgement in 3D environments are still ongoing. The report will be available when the experiments are completed.

The expansion and demonstration of a database implementation has not yet been completed. It will be completed in FY00Q3.

The implementation of SATURN indexing techniques to support moving objects in VGIS is complete. The software for indexing and retrieval of moving objects using R-tree style data structure was completed. It will further be integrated into VGIS.

In this period, we made progress along the following directions:

We explored a novel technique to representing 2-d shapes in databases. The approach explores using an adaptive resolution representation based on quad-tree partitioning. A paper based on this work is to appear in the upcoming International Conference on Multimedia and Expo, 2000.

We began exploring techniques to efficiently support aggregation queries in databases. The work has applicability to decision support, online analysis, as well as spatio-temporal databases in the context of visualization tasks.

We explored a new approach to indexing and similarity retrieval of time series data. The paper based on this has been submitted to the VLDB conference.

We initiated a large effort on integrating imprecise similarity based retrieval into database management systems. Data model extensions as well as query processing techniques in this context are being explored. Reports describing this work will be written in the coming quarter.

April 1 - June 30, 2000 (FY00Q3)

Goals: Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets. (Reported as incomplete FY99Q2-FY00Q2). Report on scaling studies in battlefield terrain database. (Reported as incomplete FY99Q4-FY00Q2). Initial integration of conceptual query framework (including optimization algorithms) into the SATURN system. (Reported as incomplete FY99Q4-FY00Q2). Complete written report on experiments comparing spatial judgement in 3D immersive environments conducted in 4^th quarter 1999. (UIUC) (Reported as incomplete FY00Q1-FY00Q2.) Expand and demonstrate database implementation and visualization of conceptual query functions representing multi-scalar abstractions and aggregation/disaggregation of database objects through the SATURN object oriented data structure. (UIUC) (Reported as incomplete FY00Q1-FY00Q2.) Report on indexing mechanisms of SATURN suited for accessing spatio-temporal data (including concurrent access). Examples include moving objects in the VGIS 3D visualization environment. (UIUC) Performance studies for rendering and query support of database objects will be initiated. (UIUC)

Progress: The complete integration of the VGIS system with SATURN system's spatio-temporal indexing mechanisms should be completed in FY00Q4.

A report on scaling studies in a battlefield terrain database is still incomplete, but should be done FY00Q4.

The integration of a conceptual query framework into the SATURN system is taking longer than anticipated, but will be finished at the end of the contract period.

The report on experiments comparing spatial judgement in 3D immersive environments is still delayed to due a lack of student help. The report will be finished FY00Q4.

The expansion of the database implementation and visualization of conceptual query functions representing multi-scalar abstractions and aggregation/disaggregation of database objects through the SATURN object oriented data structure has been completed. We developed techniques to support multiresolution representation of spatial data using quad-trees and furthermore developed techniques to support aggregate queries of various types using the data structure. We are currently preparing a report based on this task.

The report on indexing mechanisms of SATURN suited for accessing spatio-temporal data is complete. One student wrote a Master's thesis on supporting concurrent operations over multidimensional data structures (Chakrabarti, 2000). Another student wrote a PhD thesis on supporting dynamic (mobile) spatio-temporal objects in databases including techniques to efficiently index and retrieve the data (Porkaew, "Database Support for Similarity Retrieval and Querying Moving Objects", Ph.D. Thesis, July, 2000). The techniques developed are being incorporated into VGIS.

Performance studies for rendering and query support of database objects have been initiated. The initial study is under a simulation environment in which the fly through visualization is simulated over the SATURN's data structures. A more complete test over the impact of these techniques in real fly through over VGIS will have to wait until the integration of VGIS with SATURN is complete.

July 1 - September 30, 2000 (FY00Q4)

Goals: Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets. (Reported as incomplete FY99Q2-FY00Q2) Report on scaling studies in battlefield terrain database. (Reported as incomplete FY99Q4-FY00Q3) Initial integration of conceptual query framework (including optimization algorithms) into the SATURN system. (Reported as incomplete FY99Q4-FY00Q3) Complete written report on experiments comparing spatial judgement in 3D immersive environments conducted in 4^th quarter 1999 (UIUC). (Reported as incomplete FY00Q1-FY00Q3) Report on experiments on indexing techniques developed in SATURN for improving VGIS performance and functionality. (UIUC) Report on SATURN query language and query processing. The report will include techniques to extending DBMS language and query processing to support uncertain queries in the spatio-temporal domain. (UIUC) Complete software development for interactive query and display of spatial relationships and conceptual structures. (UIUC) Begin writing a chapter for the Federated Laboratory Computer Science Handbook on "advanced database management techniques to support interactive 3-D graphics and navigation in complex virtual environments".

Progress: Completing the integration of VGIS with SATURN is still pending, awaiting the port of VGIS to the Sun platform and subsequent installation at UCI. While VGIS has been ported to Sun, the installation at UCI is still not complete. The SATURN software is ready, but the integration has not yet been completed due to this reason.

The scaling studies will be done after the task above is finished.

As mentioned in previous reports, this task will be completed by the end of the contract period.

The report on spatial judgement is underway and will be completed in FY01Q1.

A report entitled "Indexing of Motion in Spatio-temporal Databases" (authors K. Porkaew and S. Mehrotra) was submitted to the International Conference on Data Engineering based on experiments on indexing techniques.

Kriengkrai Porkaew's Computer Science Ph.D. thesis ("Database Support for Similarity Retrieval and Querying Mobile Objects") included mechanisms for query processing in SATURN. Also, a report on imprecise query in data management is being written as a chapter in the upcoming Fed Lab Computer Science handbook.

The software development for interactive query and display of spatial relationships and conceptual structures will be performed once VGIS has been fully installed at UCI.

The Computer Science handbook chapter has been started.

In addition to the above research, we explored two other issues in which significant progress was made. First, we explored techniques to incorporate query refinement and imprecise computing in data management particularly in the context of multimedia databases. A paper on how query refinement can be supported over index structures was submitted to the ICDE conference. Another paper is currently being prepared for the upcoming SIGMOD conference.

Furthermore, we also made progress on the new topic of incorporating the notion of quality in query processing in data management systems. Specifically, we explored answering aggregate queries like Sum, Min, Max, Count, and Avg in an approximate manner. We developed an algorithm for answering such queries in spatial databases using selective traversal of a space partitioning multiresolution aggregate tree structure storing point data. The approach developed provides 100% intervals of confidence on the value of the aggregate and works iteratively, coming up with improving quality answers until some error requirement is satisfied or a time constraint is reached. We believe that such a mechanism is extremely useful for real-time visualization and other scenarios where it is desirable to progressively evaluate answers and an exact value is not necessary. A paper based on this work has been submitted to the ICDE conference.

October 1 - December 31, 2000 (FY01Q1)

Goals: Complete integration of VGIS system with SATURN system's spatio-temporal indexing mechanisms to scale VGIS performance during visualization of large moving object data sets. (Reported as incomplete FY99Q2-FY00Q4) Report on scaling studies in battlefield terrain database. (Reported as incomplete FY99Q4-FY00Q4) Initial integration of conceptual query framework (including optimization algorithms) into the SATURN system. (Reported as incomplete FY99Q4-FY00Q4) Complete written report on experiments comparing spatial judgement in 3D immersive environments conducted in 4^th quarter 1999 (UIUC). (Reported as incomplete FY00Q1-FY00Q4) Complete software development for interactive query and display of spatial relationships and conceptual structures. (UIUC). (Reported as incomplete FY00Q4) Make extensions to VGIS interface to support interactive spatio-temporal queries. VGIS users will be able to pose interactive queries over the spatio-temporal data set during fly-through. Finish writing a chapter for the Federated Laboratory Computer Science Handbook on advanced database management techniques to support interactive 3-D graphics and navigation in complex virtual environments.

Progress: Due to an unsuccessful port of VGIS to the SUN platform and subsequent installation at UCI, we are now attempting the integration of VGIS and SATURN on the SGI version. The SATURN software is ready, but the integration has not yet been completed due to this delay. We expect completion in FY01Q3.

As mentioned in previous reports, the report on scaling studies will be completed by the end of the contract period.

The initial integration of a conceptual query framework into SATURN has now been completed.

Due to delays in finding a suitable graduate assistant, the 3D immersive environment was never completed, therefore a report was never done. This research will not be completed as Doug Johnson has left the project and funding has been redirected.

The software development for interactive query and display of spatial relationships and conceptual structures will be performed once VGIS has been fully installed at UCI.

The extensions made to VGIS to support interactive spatio-temporal queries are now complete.

The chapter for the Federated Laboratory Computer Science Handbook was completed.

Other Research Progress

We made progress on a novel adaptive resolution approach to representing and indexing time series data to support efficient similarity (conceptual) query over such domains. A paper on this topic was submitted to the Sigmod conference.

We made further progress in the work we had described earlier on incorporating the notion of quality in data and query processing in databases. We had worked out a solution to compute aggregate queries at multiple qualities (resolution) that uses a quad-tree based data structure (called MR-tree) to support progressive computation of answers with improving quality. We extended our previous work along the following directions. First, we generalized the approach to work with overlap based data structures such as the R-tree (and submitted a paper to the Sigmod conference). Furthermore, we explored the utility of our work to visualization in the context of VGIS. We have identified numerous interesting visualization-based queries which will benefit from our work.

We developed a general methodology for incorporating similarity (conceptual) queries in databases. In this context, we developed an extended object-relational database model and query processing algorithms. Our model and technique explores how similarity queries over arbitrary data types can be supported in databases and also how query refinement can be incorporated to provide a powerful model for data access. A paper on this topic has also been submitted to the Sigmod conference.

January 1 - March 31, 2001 (FY01Q2)

Progress: The integration of VGIS and SATURN was completed this quarter and the demo based on the integrated system was shown in the ARL symposium. A screen capture of this set up is shown in Figure 12.

Figure 12: Screen Capture of VGIS and SATURN

The task of reporting on scaling studies will be completed by the end of the contract period.

The work on interactive queries was completed this quarter.

Several papers were written this quarter which address the results of our research on interactive queries and display spatial relationships; please see the Publications list.

This quarter we successfully integrated techniques to efficiently implement interactive spatio-temporal queries in VGIS.

We presented a paper and provided a demonstration of our research at the Federated Laboratory Symposium.

April 1 - June 30, 2001 (FY01Q3)

Goals: Report on scaling studies in battlefield terrain database. (Reported as incomplete FY99Q4-FY01Q2). Deploy extended VGIS with support for interactive queries and effective data structures to support efficient rendering during visualization. Report on techniques to optimize interactive spatio-temporal queries in VGIS.

Progress: Scaling studies were included in the report published in 7th International Symposium on Spatial and Temporal Databases.

The VGIS code enhanced with the support for interactive queries was made available via Rob Winkler to ARL.

The report has been submitted to the upcoming VLDB conference. It is also available as a technical report TR-DB-01-07 at UCI.