A UNIFIED FRAMEWORK FOR COLLECTIVE SPATIAL KEYWORD QUERIES

MPhil Thesis Defence


Title: "A UNIFIED FRAMEWORK FOR COLLECTIVE SPATIAL KEYWORD QUERIES"

By

Mr. Kai Ho CHAN


Abstract

With the proliferation of spatial-textual data such as location-based 
services and geo-tagged websites, spatial keyword queries become popular 
in the literature. One example of these queries is the collective spatial 
keyword query (CoSKQ) which is to find a set of objects in the database 
such that it covers a set of given keywords collectively and has the 
smallest cost. In the literature, different algorithms were proposed for 
different cost functions, in which CoSKQ using these existing cost 
measurements are known to be NP-hard. In this thesis, we propose a unified 
framework for CoSKQ based on not only all known costs studied by previous 
studies but also some other new costs proposed by us. We prove that CoSKQ 
with three of the new cost functions as the cost measurement are NP-hard.

This unified framework contains two algorithms, an exact algorithm and an 
approximate algorithm. Our exact algorithm has a comparable execution time 
as the best-known exact algorithm for CoSKQ based on any existing cost 
function. Our approximate algorithm has a similar execution time as the 
best-known approximate algorithm but with the approximate ratio at most 
the best-known approximate ratio for CoSKQ based on any existing cost 
functions. Our experimental results show that our proposed algorithms 
under this unified framework out-perform some adapted methods, originally 
designed for other cost measurements, in both real datasets and synthetic 
datasets.


Date:			Thursday, 20 August 2015

Time:			10:00am - 12:00noon

Venue:			Room 2129C
 			Lift 19

Committee Members:	Dr. Raymond Wong (Supervisor)
 			Prof. Dit-Yan Yeung (Chairperson)
 			Dr. Ke Yi


**** ALL are Welcome ****