Margaret H. Dunham - US grants

This research, sponsored through the Research Opportunities for Women (ROW) initiative, investigates main memory database (MMDB) design. Declining memory costs and demands for fast database access times have spurred great interest in the development of MMDB's, where all or major portions of databases reside in the computer's main memory. The Principal Investigator's previous research into the factors which influence effective, recoverable MMDB design has been embodied in the MARS database system prototype. The research conducted here will develop further the requirements and characteristics of design support, including such elements as the novel addressing scheme using a set associative access to the stable memory. The overall objective of the MARS project is to actually implement a prototype MMDB system based upon this initial design. While that project will take several years, the purpose of this funded research is to produce a much more detailed design of the system. The importance of this research is that, by eliminating input/output bottlenecks, main memory databases may greatly improve the performance of knowledge based computer systems. This project represents one of the first efforts aimed specifically at designing, implementing, and evaluating a MMDB prototype.

This is the first of a three year continuing award. The increasing size and decreasing cost of semiconductor memory has prompted research into databases which are memory resident. These Main Memory DataBase (MMDB) systems are aimed at high throughput applications such as airline reservation systems, phone switching databases, and other real time systems where the availability of the memory resident data is crucial. To achieve this high availability with volatile RAM requires a backup archive database on disk as well as efficient algorithms to checkpoint the database to the archive and to recover it from the archive to main memory after a system failure. It has been shown that MMDB systems often perform better with deferred update techniques where data to be updated is first placed in a special nonvolatile shadow area and only at transaction commit time is placed in main memory. The authors are investigating both checkpointing and reloading of MMDB databases with the use of more conventional immediate update (IU) techniques as well as deferred update (DU) strategies. The best checkpointing approaches are to be determined as are partial reloading strategies. A partial reload allows the database to be brought online after a system failure faster because not all of the MMDB is reloaded prior to bringing the system up. This research represents the first examination of techniques for partial reloading of MMDB systems. Due to the volatility of RAM, the high throughput needs of MMDB applications, and the potential for partial reloading to dramatically increase the uptime of database systems, the results and impact of this research are both widespread and significant.

9417907 Eich This award will partially support travel, living expenses and publication costs for Dr. Margaret H. Eich and a graduate research assistant from Southern Methodist University to conduct cooperative research with Dr. Maria Orlowska and Dr. Robert Colomb, of the Department of Computer Science at the University of Queensland in Brisbane, Australia. The collaborative research will focus on developing new checkpointing and recovery algorithms aimed at distributed databases. Database checkpointing saves the state of a database on a stable memory separate from the primary database copy. In the event of a failure of a primary copy, the loss can be restored using the backup copy of the log. Checkpointing techniques so far examined by the Southern Methodist group require no synchronization between transactions and checkpointing, and also facilitate a partial recovery of the database after failure. These features are desirable for both a high throughput Main Memory Database (MMDB) system, and also for a distributed database environment. Objectives for this cooperative work are to examine techniques for extending MMDB recovery to distributed databases. The specific work to be conducted will apply partition checkpointing to distributed database environments, will expand commit and partial recovery algorithms for distributed environments, and will perform initial analytic studies validating the developed approaches. ***

9724517 Dunham, Margaret Barr, Richard Southern Methodist University MRI: A Laboratory for Telecommunications Management Network Research Southern Methodist University will be acquiring four ATM switches and associated network hardware to establish a telecommunications laboratory which will support research in the areas of database, optimization and network planning, fault tolerant and distributed processing, and visualization. Southern Methodist University plans to use the telecommunications laboratory to support graduate student research as well as an experimental testing facility for graduate level courses such as Operating Systems, Parallel and Distributed Processing, Database Management, Software Engineering, Telecommunication Network Management, and Systems in Telecommunications.

This project develops data mining algorithms, both association rules and prediction, targeted to geospatial data. This GOALI research is performed in collaboration with the SIVAM project underway at Raytheon Systems Company. Raytheon Systems Company, Garland Division, has the responsibility for the hardware and software development of SIVAM (System for the Vigilance of the Amazon). SIVAM's objective is to implement a surveillance and analysis infrastructure, including a very large (multi terabyte) geospatial database and associated visualization tools that will provide the Brazilian Government with the necessary information for the protection and sustainable development of the Amazon region. This research focuses on an important aspect of the overall problem: development of new algorithms for a specific target application. The developed algorithms scale to the massive amounts of data present as well as adapt to the available amount of main memory. In the SIVAM project, data is obtained on an ongoing basis (as time advances). The prediction algorithms are used to predict environmental catastrophes (such as flooding or deforestation) and are incremental in nature. State information is kept which "remembers" previous environmental data collected. As new data arrives, the state is advanced based on the data found. In addition, these structures used to save this state information are modified as learning takes place. The results of this research will advance the field of data mining and provide enabling technologies for the environment research and management.
http://www.seas.smu.edu/~mhd/dm.html

This research project is a collaborative effort of Margaret Dunham, Southern Methodist University (IIS-9979458) and Vijay Kumar, University of Missouri at Kansas City (IIS-9979453) and is supported under the Wireless Information Technology and Networks (WITN) initiative, NSF 99-68. The goal of this research is to develop schemes for processing data that are strongly related to geographical locations, on a mobile computing platform. Unlike conventional data processing systems, in a wireless mobile computing environment the value of data may depend on location, and processing of a transaction at one site may give different results than that at another. This situation identifies a new type of data, which we refer to as Location Dependent Data (LDD). Thus, LDD is a class of data whose value is determined by (a) the geographical location of data storage and (b) the geographical location of the Mobile Unit (MU) where the query originated. For example, when a query from a MU wants to find out information about local hotels, it will get a different answer in Dallas than in Kansas City. It would even be possible for a traveler driving from Dallas to Kansas City to ask the same question en route but specifically request the response using Kansas City data rather than data based on the location from which he requests the query. Although the query may be stated in exactly the same way, it is interpreted in a location-dependent context. The objective of this research is to further explore the concept of LDD, its impact on transaction processing, and develop efficient schemes for its management. As a result of this research, methods will be produced which facilitate the storage of location dependent data at Mobile Units and techniques to efficiently process transactions which access this type of data. The creation of a testbed to is a major objective of the project. It will be used to implement and compare the various strategies proposed during the research.

This research investigates a new architecture designed to provide
data to wireless users using a broadcast technique. The objective of this research is to develop schemes for implementing the concept ``DAta in your space (DAYS)" which combines broadcasting (push) and traditional querying (pull) techniques into one global wireless approach. In this scheme the data broadcasters (special servers) will continuously
broadcast (push) requested data to a set of ``dedicated" wireless
channels, which will be captured by clients (users of the data) at
any time and at any place. The space will thus be used as
persistent storage for all mobile as well as static devices.

A universal wireless broadcast approach requires that mobile users be able to find and use the right broadcast information. Some of the questions to mbe addressed include:
1. How can the mobile user know which channel has the correct data?
2. How is data to be assigned to channels?
3. What techniques can be used to effectively determine the best contents of each channel given many mobile users?
4. Without explicit user queries, how can the mobile user be assured that the needed data is being broadcast?
5. How can the mobile user be assured that the needed data moves with
him?
These issues have to be examined on a global scale.

State-of-the-art data stream clustering algorithms developed by the data mining community do not utilize the temporal order of events and therefore in the resulting clustering all temporal information is lost. This is quite strange as one of the salient features of data streams is temporal ordering of events. In this project we develop a technique to efficiently incorporate temporal ordering into the clustering process and prove its usefulness on large, high-throughput data streams. Temporal ordering is introduced into the data stream clustering process by dynamically constructing an evolving Markov Chain where the states represent clusters. Our approach is based on the previously developed Extensible Markov Model (EMM). The results of this project will provide a framework upon which important stream mining applications such as anomaly detection and prediction of future events are easily implemented.

By showing that state-of-the-art data steam clustering algorithms can incorporate temporal order information efficiently, this project will have a broad impact on many areas where temporal order is essential. As examples, NOAA Hurricane Data and NASA satellite data will be used throughout this project. Results, including open source software will be distributed via the project Web site (http://lyle.smu.edu/ida/tracds).

DESCRIPTION (provided by applicant): Position Sensitive P-Mer Frequency Clustering with Applications to Classification and Differentiation Recent genomic sequencing advances, such as next generation sequencing, and projects like the Human Microbiome Project create extremely large genomic databases. Even though the length of any specific sequence may be much shorter than that of the complete DNA sequence of an organism, looking at enormous libraries of sequences, such as 16S rRNA, presents an equally (if not greater) computational challenge. In traditional genomic analysis, only one sequence may be analyzed at a time. When dealing with metagenomics, thousands (or more) sequences need to be analyzed at the same time. However, to study such problems as environmental biological diversity and human microbiome diversity this is exactly what is needed. Current techniques have several shortcomings which need to be addressed. Techniques involving sequence alignment are typically based on selection of one representative sequence (as is typically done when looking at 16S rRNA data) which introduces selection bias. Genomic databases involving multiple copies of 16S per organism across thousands of organisms, will soon grow too large to practically process just using computationally expensive alignment methods to match sequences, but faster alignment-free methods currently do not provide the needed accuracy and sensitivity. As a complement to existing methods we introduce a novel class of fast high-throughput algorithms based on quasi-alignment using position specific p-mer frequency clustering. Organisms are represented by a directed graph structure that summarizes the ordering between clusters of p-mer frequency histograms at different positions in sequences. This model can be learned using all available 16S copies of an organism and thus eliminates selection bias. Due to the added position information, these algorithms can be used for species (and even strain) classification facilitating the study of strain diversity within species. Our prototype implementation of this new technique shows that it is able to produce compact profiles which can be efficiently stored and used for large scale classification and differentiation down to the strain level. Since the technique incorporates high-throughput data stream clustering, a proven technique in high performance computing, it scales well for very large scale DNA/RNA sequence data as well as massive sets of short sequence snippets collected during metagenomic research. In this project we will develop a suite of tools, profile models, and scoring techniques to model RNA/DNA sequences providing applications of organism classification, and intra/inter-organism similarity/diversity. Our approach provides both the specificity needed to perform strain classification and still avoid the computational overhead of alignment. It is important to note that this is accomplished through dynamic online machine learning techniques without human intervention. PUBLIC HEALTH RELEVANCE: Recent advances in Metagenomics and the Human Microbiome provide a complex landscape for dealing with a multitude of genomes all at once. One of the many challenges in this field is classification of the genomes present in the sample. Effective metagenomic classification and diversity analysis require complex representations of taxa. The significance of our research is that we develop a suite of tools, based on novel alignment free techniques that will be applied to environmental metagenomics samples as well as human microbiome samples. Providing such methods to rapidly classify organisms using our new approach on a laptop computer instead of several multi-processor servers will facilitate the rapid development of microbiome-based health screening in the near future.