THESIS
2015
xii, 82 pages : illustrations ; 30 cm
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-...[
Read more ]
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.
Post a Comment