Comprehensive Spatial Query Containment Framework for Minimizing Redundancy

Open Access
- Author:
- Unger, Brandon Michael
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- April 06, 2009
- Committee Members:
- Wang Chien Lee, Thesis Advisor/Co-Advisor
Wang Chien Lee, Thesis Advisor/Co-Advisor
John Joseph Hannan, Thesis Advisor/Co-Advisor
Daniel Kifer, Thesis Advisor/Co-Advisor - Keywords:
- region query
database
data management
containment framework
auxiliary scope
containment scope
spatial query
nearest neighbor query
reverse nearest neighbor query - Abstract:
- Spatial data management has received significant attention from the database research community in recent years because of its huge application to our daily lives. Several impacted areas include business intelligence operations, geographic information systems, and location-based services. While these services are valuable to users, they frequently must operate on systems with limited processing capability and bandwidth capacity. To minimize unnecessary resource consumption, an effective strategy is to avoid the execution of redundant queries based on results previously obtained by the client. This work introduces the concept of spatial query containment as a means to identify when a new query can be answered solely using results from an existing query. For the approach proposed in this thesis, query containment has been engineered to support a variety of popular spatial query types, including range, window, k-nearest neighbor, and reverse k-nearest neighbor. Each query Q has an associated containment scope area such that any future query Q’ both semantically contained by Q and issued at a point inside of the containment scope of Q can be answered using only the results from Q. Theoretical and experimental analysis indicate that the containment scope processing framework outperforms existing techniques under a wide variety of datasets, query loads, and computing environments. The substantial reduction in redundant query evaluations provided by the spatial query containment framework supports the deployment of novel, data rich applications in challenging environments while maintaining sufficient scalability, reliability, and performance.