On optimal spatial dominance

Abstract

Speeding up spatial methods using hyperspheres as a core component is very important in the literature. For example, many indexing techniques such as an M-tree and a VP-tree and many uncertain database methods involves hyperspheres as one of the core components for answering many important spatial queries such as similarity search queries. These techniques heavily depends on an important operator called a spatial dominance for pruning in order to speed up spatial queries. In this thesis, we study the dominance problem which has a variety of applications. Given two hyperspheres S_a and S_b and a query hypersphere S_q, we want to determine whether S_a dominates (or is closer than) S_b with respect to S_q. There are many existing methods relying on this operator. Unfortunately, the well-known conventional pruning technique which makes use of the maximum distance and the minimum distance is insufficient for the dominance problem. Motivated by this, we propose a novel method which is optimal and efficient for the problem. In addition, we give a list of existing applications which can benefit from this operator. Finally, we show the effectiveness and efficiency of our proposed method on real datasets.

Date of Award	2013
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology