Spatial query processing using Voronoi diagrams | Posted on:2008-08-07 | Degree:Ph.D | Type:Dissertation | University:University of Southern California | Candidate:Sharifzadeh, Mehdi | Full Text:PDF | GTID:1448390005973526 | Subject:Computer Science | Abstract/Summary: | | Spatial query processing in spatial databases, Geographic Information Systems (GIS), and on-line maps attempts to extract specific geometric relations among spatial objects. As a prominent category of spatial queries, the class of nearest neighbor queries retrieve spatial objects that minimize specific functions in terms of their distance to a given object (e.g., closest data point to a query point). The most efficient algorithms that address nearest neighbor queries utilize the R-tree index structure to avoid I/O operations for the groups of data objects that do not contain the final query result. However, they still result in unnecessary I/O operations as R-trees are not efficient in elaborate exploration of the portion of data space that includes the result.In this dissertation, we propose a new index structure, termed VoR-tree, that incorporates Voronoi diagrams into the R-tree index structure for I/O-optimal processing of nearest neighbor queries on point datasets. The neighborhood information encoded in Voronoi diagrams allows a VoR-tree-based algorithm to optimally explore the data space towards the result. We complement our efforts by proposing I/O-optimal algorithms for k nearest neighbor, reverse k nearest neighbor, k aggregate nearest neighbor, and spatial skyline query types. These algorithms perform the least amount of I/O with respect to the information provided in their underlying VoR-tree. Therefore, they find the query result with less I/O operations than their best competitor for each query type. | Keywords/Search Tags: | Query, Spatial, I/O operations, Processing, Nearest neighbor, Result, Voronoi, Data | | Related items |
| |
|