Framework for Integrating Geospatial and Online Data to Respond
to Unexpected Events
This project is collaboration between IMSC, ISI, and the Department of Geography at USC. It is focused on developing a framework in which traditional structured data (such as relational databases), semi-structured data (such as xml files), and spatio-temporal data (such as bus schedules and road networks) can be integrated and queried in such a way as to produce results that would be otherwise difficult or impossible to acquire through other means. We have a framework that supports rapid and dynamic integration of online and geospatial data sources, and now are moving to enhance and extend data types, operations and functionality of the framework. At InfoLab we are now working on integrating path finding and route planning (we are starting by implementing some basic algorithms like shortest path finding) into the framework to allow these utilities to be used seamlessly from within the query framework system:
• K-Nearest Neighbors: An important class of queries in GIS applications is the class of K-Nearest Neighbor queries, where a set of K closest points of interest (e.g., hospitals or restaurants) to a query point is requested. Real-world applications often result in the formulation of new variations of the KNN queries each demanding new a solution in presence of problem constraints. The challenge in all of these queries is to process the query as fast as possible when: 1) The dataset is usually large, and hence, conventional techniques usually lead to very long query processing time. 2) The distance function is usually computationally complex, which again usage of conventional approaches will be impractical. Different approaches to address these challenges have been proposed. These approaches are usually based on approximation of the actual distance function with a simpler one (e.g., using Euclidean distance instead of shortest path) and utilization of spatial index structures. The problem with these approaches is that the simple distance function may not (and often does not) provide an acceptable approximation for the distance function. At USC InfoLab, we focus on nearest neighbor problem for road networks, where the distance function between two points is usually their shortest path. We address this problem from different angles. First, we propose a more accurate (compared to Euclidean distance) approximation of the shortest path distance function by transforming the original network to a higher dimensional space.
• Optimal Sequenced Route:
We are studying an unexploited and novel form of KNN queries named Optimal Sequenced Route (OSR) query in both vector and metric spaces. OSR strives to find a route of minimum length starting from a given source location and passing through a number of typed locations in a specific sequence imposed on the types of the locations. Our experiments verified that our algorithms significantly outperform the naive approach in terms of processing time (up to two orders of magnitude) and required workspace (up to 90% reduction on average).