The goal of this project is to research and develop techniques for the correct conceptual evaluation, processing, and optimization of multi-predicate spatial (MPS) queries in support of location-based services. The project achieves its goal using the following approaches: (1) Study the characteristics of MPS queries and develop a new consistent and provably correct conceptual evaluation strategy for MPS queries similar to the one for relational SQL queries; (2) Develop various query transformation rules that not only retain correctness but also transform MPS query execution plans into more efficient ones; (3) Investigate the validity of well-known relational optimization heuristics in the context of MPS queries and develop innovative optimization algorithms unique to MPS queries; (4) Develop a cost model to aid the query optimizer in selecting the best query execution plans for MPS queries and study the impact of the variation on temporal and spatial moving object distributions on MPS query execution plans; (5) Develop new adaptive spatiotemporal query processing techniques that can cope with the dynamic nature and scale of moving object environments; (6) Prototype an MPS location server that reflects the correct evaluation and efficient optimized execution of continuous and adaptive MPS operators; and (7) Develop simulators and analytical models to evaluate the performance of the developed techniques. The research results are beneficial to many applications including location servers, intelligent transportation systems, smart cities, supply chain management, and emergency response and recovery.

This project supports Ph.D. students to pursue research in the areas of spatiotemporal data management systems and advanced location servers, and involves undergraduate students in related research projects. The project develops and introduces a new entry-level undergraduate programming course around 2D and 3D map operations and queries that utilizes MPS queries and integrates the research results from the project to increase the interest in programming of students from Computer Science as well as from other Science disciplines. The project involves minority students through the Discovery Learning Center at Purdue Discovery Park and the Louis Stokes Alliance for Minority Participation (LSAMP) project and Alliances for Graduate Education Program (AGEP). Publications, technical reports, software and experimental data from this research are available at the project web site (

Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
Purdue University
West Lafayette
United States
Zip Code