Le Gruenwald - US grants

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.

EIA-9973465
University of Oklahoma
POWRE: A Transaction Management Technique for Nomadic Multidatabases
Gruenwald, Le

This project allows the PI to venture into the new research areas of mobile databases and mutlidatabases that are recently determined to be of extreme importance for future database research. The proposal addresses development of a pre-serialization transaction management technique for the mobile multidatabase environment that addresses disconnection and migration. Further, the PI proposes development of an analytical model and a simulation model that will be used to compare the performance of the proposed technique to that of other techniques found in the literature, and to provide guidelines to assist both users and designers.

This grant funds investigation of scalable techniques for real-time order promising by discrete build-to-order environments facing dynamic order arrivals. The algorithms to be developed in this project for calculating due dates consider current time-phased availability of resources and material, existing commitments, and the current system state. The presence of various alternate resources or materials increases the combinatorial complexity of the problem. To increase performance, a combination of both
optimal algorithms with good scalability such as shortest path and computational heuristics will be considered. One of the heuristics to be examined is based on a novel, even controversial, idea: for the purposes of promising, the time when a resource will be able to process an operation can be estimated with sufficient accuracy by considering only a partially ordered resource task plan. Current support for this principle is grounded in practical experience but little scientific evidence. Joint research occurring at the intersection of Industrial Engineering and Computer Science is necessary in this project because algorithmic and computational aspects are intertwined when performing research in a large-scale systems context.
Algorithms will be implemented in an object-oriented, memory-resident, multi-threaded architecture for detailed study and empirical evaluation. A key tenet of this project is that the results be highly scalable.

Order promising is perhaps the most important operational-level activity. The ability to make tight, yet achievable, promises in response to requests from consumers or other businesses is a fundamental business requirement. Surprisingly, very little research has been done in this area. Results of this research will increase the accuracy and speed with which these promises can be made. This research is directly applicable to manufacturers that increasingly are selling built-to-order products direct to customers via the Internet and to a future where collaborative commerce freely occurs among dynamically recombinant business partners.

This Scalable Enterprise Systems Phase II grant funds an investigation of scalable techniques for real-time order promising by discrete build-to-order environments facing dynamic order arrivals. The algorithms to be developed in this project for calculating due dates accurately consider current time-phased availability of resources and materials, prior order commitments, and the current system state. The presence of various alternates (resource paths or material sources) creates combinatorial complexity. To increase performance, the promising algorithms will integrate (1) theoretically sound heuristic techniques developed through research, (2) scalable optimal algorithms such as shortest path, and (3) computational technology. One of the heuristics to be examined is based on a novel, even controversial, idea-- for the purposes of promising, the time when a resource will be available to process an operation can be estimated with sufficient accuracy by considering only a partially ordered task plan. Current support for this principle is based on practical experience but little scientific evidence. A key tenet of this project is that the results be highly scalable. Consequently, joint research occurring at the intersection of Industrial Engineering and Computer Science is both necessary and synergistic in this project since the algorithmic aspects of promising and advanced computational approaches for technological realization are intertwined when research is performed in a large-scale systems context. Algorithms will be implemented in an object-oriented, event-driven, memory-resident, multi-threaded architecture for detailed study and empirical evaluation.

One of the most important short-term customer service decisions is making accurate promises in response to requests from customers or business partners. Surprisingly, very little research has been done in this area. While a vast body of literature exists on scheduling to meet prescribed due dates, very little work addresses how due dates that are tight yet achievable may be assigned. Results of this research will increase the accuracy and speed with which these due date promises can be made, which in turn will have a very significant impact on revenues, operating expenses, and customer satisfaction. This research is directly applicable to manufacturers that increasingly are selling built-to-order products direct to customers via the Internet and to a future where collaborative commerce freely occurs among dynamically recombinant business partners.

This research project proposes to develop a transaction management technique for a mobile multidatabase management system that takes energy restriction, transaction real-time constraints, and ad-hoc networks into consideration. This technique is aimed at reducing the overall energy consumption and providing a balance in individual mobile host (MH) energy consumption, while at the same time reducing the number of transactions that must be aborted due to deadline violations. It considers both firm real-time and soft real-time transactions, and three modes that an MH can be in: active, doze, and sleep. It treats time as the most important factor in handling firm transactions while energy as the most important factor in handling soft transactions. It uses this principle to locate MHs, schedule transactions, and commit/abort transactions. It handles disconnection and migration by introducing a suspended state into global transactions to ensure that transactions of mobile users whose status is unknown will not be aborted until they obstruct the execution of other transactions. A prototype will be developed to evaluate the performance of the proposed technique for real-life applications and to provide guidelines to assist both users and designers.

Query response time and system throughput are the most important metrics when it comes to database and file access performance. Because of data proliferation, efficient access methods and data storage techniques have become increasingly critical to maintain an acceptable query response time and system throughput. One of the common ways to reduce disk I/Os and therefore improve query response time is database clustering, which is a process that partitions the database/file vertically (attribute clustering) and/or horizontally (record clustering). To take advantage of parallelism to improve system throughput, clusters can be placed on different nodes in a cluster machine.

This project develops a novel algorithm, AutoClust, for database/file clustering that dynamically and automatically generates attribute and record clusters based on closed item sets mined from the attributes and records sets found in the queries running against the database/files. The algorithm is capable of re-clustering the database/file in order to continue achieving good system performance despite changes in the data and/or query sets. The project then develops innovative ways to implement AutoClust using the cluster computing paradigm to reduce query response time and system throughput even further through parallelism and data redundancy. The algorithms are prototyped on a Dell Linux Cluster computer with 486 compute nodes available at the University of Oklahoma. For broader impacts, performance studies are conducted using not only the decision support system database benchmark (TPC-H) but also real data recorded in database and file formats collected from science and healthcare applications in collaboration with domain experts, including scientists at the Center for Analysis and Prediction of Storms (CAPS) at the University of Oklahoma. The project also makes important impacts on education as it provides training for graduate and undergraduate students working on this project in the areas of national critical needs: database and file management systems, and high-end computing and applications. The developed algorithm and prototype, real datasets and performance evaluation results are made available to the public at the Website: http://www.cs.ou.edu/~database/AutoClust.html.

Earth's seasonality produces a flow of energy, information, and biodiversity between tropical and temperate regions. Much of this flow occurs through the aerosphere is a broad diversity of migratory animals. Long distance migration and dispersal is an important contributor to the rapid seasonal redistribution of productivity, spread of disease, and shifts in biodiversity across and among continents. Visualizing and modeling the collective behaviors of the diversity of animals that use the aerosphere for foraging, dispersal, and migration is pivotal to understanding and forecasting continental macroecological dynamics; and will be a core focus of this project. This EAGER award will focus on a high-risk approach building a mechanistic understanding of macroecological dynamics in the aerosphere based on the NEXRAD network of weather surveillance radars. The combination of recent and ongoing advances in radar technology, computation capabilities and data processing workflows, primarily in meteorology, have brought researchers to the edge of a revolution in the capacity to use weather radars as a biological sensors system. However, outside of meteorology, this resource is vastly under-used due to a general lack of analysis tools and data sets tailored to biologists. This EAGER award will focus on improved infrastructure and validation on providing radar-based metrics of distribution, density, and diversity of animals in the aerosphere. This project will include an integrated series of observational, experimental, and modeling studies that will result in a set of tools, products, and applications that enable transformative science in aeroecology.

The broader impacts of this award will increase the availability and interpretability of radar data for investigations in environmental biology and building an interdisciplinary training environment at the interface of ecology, spatial modeling, computer science and meteorology. The radar tools and products that are developed will be widely distributed and make major contributions to basic understanding of aeroecology, which will be useful in (1) minimizing the impact of wind power development; (2) aviation safety; and (3) evaluation of ecosystem services. This project will lead a growing culture of interdisciplinary research by supporting a post-doc and student in an interdisciplinary group project with co-advisors and committee members from different disciplines (i.e. biology, computer science, and meteorology).

Innovative mobile technologies offer interesting opportunities in many domains, such as health care, transportation, and commerce. They enable distant monitoring and permit consideration of parameters such as patient's and physician's mobility. This makes it possible to develop novel applications, such as mobile health services for telemedicine and assisted ambient living (particularly in rural areas) and mobile traffic services. Nevertheless, the amount of data to be generated and queried is very large and diverse and is collected from multiple sources. The combination of big data and mobility leads to a major challenge: how to efficiently process queries from a myriad of mobile devices on a large amount of data, especially when the data are to be stored in a novel data management system supplied by several cloud providers with possibly different pricing models? To solve this challenge, this project develops novel mobile cloud data management architectures and novel query processing algorithms that leverage mobile users' storage and computation power and take mobile users' mobility, disconnection, energy limitation, and cloud service providers' pricing models into consideration in order to improve query response time, while reducing the amount of money that must be paid to the cloud service providers. The research is evaluated using both real and synthetic datasets by means of prototyping.

The project is an international collaboration effort between the University of Oklahoma (OU) and Blaise Pascal University in France. For research, both universities participate in the design, prototype and evaluation of the architectures and algorithms. For education, via Skype, OU provides lectures on mobile and big data management for the Big Data Management course at Blaise Pascal University, while Blaise Pascal University provides lectures on cloud data management for the Advanced Database Management course at OU. The students in both courses participate in testing the constructed prototype as a part of their class assignments. The project makes important impacts not only on research but also on education as it provides training for graduate and undergraduate students in the areas of critical national needs: cloud and mobile database management systems, big data and high-end computing. The developed architectures, algorithms, prototype, datasets and performance evaluation results are made available to the public at the Website: http://cs.ou.edu/~database.

Although locating and navigation devices embedded in smartphones have already generated large volumes of location and trajectory data, the next generation of consumer electronics are likely to generate even larger volumes of location-dependent data where spatial and trajectory data management techniques will play critical roles in understanding the data to facilitate decision making. Modern Graphics Processing Units (GPUs) are capable of general computing. Current generation of commodity GPUs have large numbers of processing cores, support even larger numbers of current threads and provide high memory bandwidth, yet are available at affordable prices. The massively data parallel computing power of GPUs makes the hardware ideal for spatial and trajectory data management which is both data and computing intensive.

This project develops parallel indexing structures and query processing algorithms for spatial and trajectory data on GPUs to provide high performance which is crucial in speeding up existing applications and enabling new scientific and business inquiries. The project achieves its goals by developing: 1) novel spatial indexing techniques on GPUs; 2) novel spatial joins on GPUs; 3) novel trajectory segmentation and indexing techniques and trajectory similarity query processing techniques on GPUs; and 4) an end-to-end prototype system incorporated with open source database and GIS systems for performance evaluations and real world applications. Compared with existing spatial and trajectory data management systems that are mostly disk-resident and adopt a serial CPU computing model, the performance of GPU accelerated main-memory based systems is expected to achieve several orders of magnitude speedup and brings the performance of spatial and trajectory queries to a new level. The research results are beneficial to many applications, such as transportation, urban planning, wild bird ecology, and epidemiology of infectious diseases. Collaboration is carried out with transportation engineers at the University Transportation Research Center in New York City and ecology scientists at the University of Oklahoma?s Earth Observing and Modelling Facility. The project also makes important impacts on education as it provides training for students in the areas of national critical needs: database research, high performance computing, GPU programming, GIS, transportation, mobile and ecology applications. The developed algorithms and prototype system, real datasets and performance evaluation results are made available to the public at the Website: http://www.cs.ou.edu/~database.

This project provides travel support for undergraduate and graduate students enrolled at universities in the U.S. to attend the 16th IEEE International Conference on Mobile Data Management (MDM 2015) on June 15-18, 2015 in Pittsburgh, PA. MDM is a premier conference sponsored by the IEEE Computer Society. It encompasses all aspects of mobility. Given the broad sense of mobility, MDM brings together researchers from databases, networking and ubiquitous and pervasive computing, to present and discuss the progress of science in these areas of critical national needs. The conference relies on the experience of senior members of the community, but also aims to generate fresh ideas, foster new collaborations, and expose new people to emerging research opportunities. Attendance at MDM is very beneficial to students. The conference makes for an excellent forum for exchange of ideas and future collaborations. Students also have opportunities to meet distinguished researchers and be inspired by them to follow careers in mobile data management research.

The conference provides opportunities for four days of exciting discussions on topics of mobile data management. The theme of MDM 2015 is the Internet of Things (IoT) and Mobile Cloud Computing. In addition to research paper presentations, MDM includes tutorials, demos, workshops and panels on emerging topics and industrial applications. To encourage students to participate in the exciting technical program, this project provides support to defray the travel expenses for student attendees. Calls for MDM 2015 student travel support applications are advertised nationwide through the MDM 2015 website (http://mdmconferences.org/mdm2015/index.html) and other venues including DBWORLD. Students from underrepresented groups (women, minorities and disabled students) are especially encouraged to apply. The project details can be found at the project website http://www.pitt.edu/~kpele/nsf-mdm.html.