school

UM E-Theses Collection (澳門大學電子學位論文庫)

check Full Text
Title

Breaking the top-k restriction of the KNN hidden databases

English Abstract

With the increasing development of Location-based services (LBS), the spatial data become accessible on the web. Often, such services provide a public interface which allows users to find k nearest points to an arbitrary query point. These services may be abstractly modeled as a hidden database behind a kNN query interface, we refer it as a kNN hidden database. The kNN interface is the only way we can access such hidden databases and can be quite restrictive. A key restriction enforced by such a kNN interface is the top-k output constraint - i.e., given an arbitrary query, the system only returns the k nearest points to the query point (where k is typically a small number such as 10 or 50), hence, such restriction prevents many third-party services from being developed over the hidden databases. In this paper, we investigate a interesting problem of "breaking" the kNN restriction of such web databases to find more than k nearest point. To our best knowledge, this is the first work to study the problem over the kNN hidden database. We investigate and design a set of algorithms which can efficiently address this problem. Beyond that, we also perform a set of experiments over synthetic datasets and real-world datasets which illustrate the effectiveness of our algorithms

Issue date

2015.

Author

Li, Hong Lin

Faculty

Faculty of Science and Technology

Department

Department of Computer and Information Science

Degree

M.Sc.

Subject

Data protection

Data encryption (Computer science)

Files In This Item

Full-text (Intranet only)

Location
1/F Zone C
Library URL
991000757769706306