# Spatial Query Processing Utilizing Voronoi Diagrams

Google TechTalks

August 10, 2006

Mehdi Sharifzadeh is a PhD student doing research at USC this summer for Google. He will be giving a talk on his research as well as his PhD.

ABSTRACT

Efficient spatial query processing in spatial databases, Geographic Information Systems (GIS), and even on-line map systems requires respecting the geometric characteristics of the space of data (i.e., domain). Extracting the geometry of the data is also the ultimate target in many spatial data mining and knowledge discovery tasks. Geometric concepts such as "œcloseness" mainly depend on the distance metric defined in the space of data. Many spatial queries are seeking to optimize specific functions in terms of this distance metric.

This fact motivated us to seek for a data structure customizable for spatial queries in various data spaces such as road networks. A data structure that nicely captures varieties of distance-based relations in a geometric space is Voronoi diagram!

We show the flexibility of Voronoi diagrams with respect to their two parameters of space and distance and their effectiveness in answering several interesting novel spatial queries as our case studies. We also demonstrate incorporation of some of these queries within on-line map systems.