Download files
Abstract
With the emergence of location-aware mobile device technologies, communication technologies and GPS systems, location-aware queries have attracted great attentions in many important applications such as location based service (LBS) and geographic information system (GIS). The location-aware query has many different types such as k nearest neighbors(kNN), reverse nearest neighbor (RNN), top-k preference query, and skyline set. The spatial database can usually be categorized as certain data and uncertain data. There is a special spatial database, termed spatial database associated with facility types. In this thesis, we focus on investigating the location-aware queries on this special database. In user recommendation web services, the facility types can be supermarkets, pubs, public transport stations, etc. The location-aware queries include top-k preference query and spatial skyline operators.
We first study the top-k preference query on the proposed spatial database. We study the problem of finding the most accessible locations among a set of possible sites. We propose two algorithms, named separate-tree and one-tree to efficiently perform top-k preference query.
We then study the spatial skyline operators on the proposed spatial database. First, we formularize the skyline operators on the proposed spatial database. Then we propose P-GSSKY algorithm that can significantly reduce the number of non-promising objects in the computation, and J-GSSKY that can compute GSSKY efficiently in terms of I/O cost.
We further study the nearest neighbor search and all nearest neighbor search problem in spatial database. We propose a new data structure, termed AVR-tree which intergrates voronoi diagrams to the R-tree structure in order to effectively prune unpromising objects in the highlevel of R-tree.
Last, we study the range search and k nearest neighbor search on uncertain data. We propose a novel index structure, called U-Quadtree, to effectively organize the multi-dimensional uncertain objects with arbitrary probability distribution functions (pdf). Algorithms for performing range search and k nearest neighbor search are provided. Then we provide a cost model and propose efficient optimal U-Quadtree construction algorithm.