Events Calendar

PhD Defense - Seyed Jalal Kazemitabar Amirkolaei - "Scalable Processing of Spatial Queries"

Speaker: Seyed Jalal Kazemitabar Amirkolaei, PhD Candidate

Talk Title: Scalable Processing of Spatial Queries

Abstract: In recent years, geospatial data have been produced in mass e.g., through billions of smartphones and wearable devices. Current exponential growth in data generation by mobile devices on the one hand, and the rate and complexity of recent spatial queries on the other hand, highlights the importance of scalable query processing techniques. Traditional database technology, which operates on centralized architectures to process persistent and less dynamic spatial objects does not meet the requirements for scalable geospatial data processing.

In this thesis, we specifically focus on two primary challenges in scaling spatial queries, i.e., the communication and computation costs, while guaranteeing the correctness of query results. We utilize techniques such as batch processing and use of parallelized framework to address these challenges.

We address the location tracking cost towards achieving scalability in communication-intensive queries. The location tracking cost between the moving objects and the query processing server is a key factor in processing many moving object continuous queries. The challenge is that increasing the number of queries and objects would require frequent location updates which results in draining the battery power on mobile devices. Thus, existing approaches would not scale unless query correctness is compromised. In this thesis, we propose batch processing of spatial queries as a method to optimize the location tracking cost to scale to large numbers of queries and objects without either compromising the query correctness or using excessive battery power. In our approach, the queries are categorized into independent groups and then processed in parallel. We specifically apply our approach to the proximity detection query and optimize the communication cost while processing millions of queries.

Processing some spatial queries has become more resource-intensive in recent years. This is due to various reasons such as the introduction of queries that are more computationally complex compared to the classic ones, as well as an increase in the input size (e.g., the number of GPS-enabled devices). In this thesis, we propose optimized algorithms and utilize MapReduce to process a complex spatial problem, i.e., the Multi-Criteria Optimal Location (MCOL) problem. First, we formalize it as a Maximal Reverse Skyline (MaxRSKY) query. For the first time, we present an optimized solution that scales to millions of objects over a cluster of MapReduce nodes. Specifically, rather than batch processing the query which is typical of a MapReduce solution, we first partition the space and run a precomputation phase where we identify potential regions hosting the optimum solution, and then load balance the regions across the Reducers in a dynamic way to reduce the total execution time.


Host: Seyed Jalal Kazemitabar Amirkolaei

Location: Henry Salvatori Computer Science Center (SAL) - 213

Audiences: Everyone Is Invited

Contact: Ryan Rozan