Determining Top-K Candidates by Reverse Constrained Skyline Queries

Ruei Sian Jheng, En Tzu Wang, Arbee L. P. Chen

2015

Abstract

Given a set of criteria, an object o is defined to dominate another object o' if o is no worse than o' in each criterion and has better outcomes in at least a specific criterion. A skyline query returns each object that is not dominated by any other objects. Consider a scenario as follows. Given three types of datasets, including residents in a city, existing restaurants in the city, and candidate places for opening new restaurants in the city, where each restaurant and candidate place has its respective rank on a set of criteria, e.g., convenience of parking, we want to find the top-k candidate places that have the most potential customers. The potential customers of a candidate place is defined as the number of residents whose distance to this candidate is no larger than a given distance r and also regard this candidate as their skyline restaurants. In this paper, we propose an efficient method based on the quad-tree index and use four pruning strategies to solve this problem. A series of experiments are performed to compare the proposed method with a straightforward method using the R-tree index. The experiment results demonstrate that the proposed method is very efficient, and the pruning strategies very powerful.

Paper Citation

in Harvard Style

Jheng R., Wang E. and Chen A. (2015). Determining Top-K Candidates by Reverse Constrained Skyline Queries . In Proceedings of 4th International Conference on Data Management Technologies and Applications - Volume 1: DATA, ISBN 978-989-758-103-8, pages 101-110. DOI: 10.5220/0005498601010110

in Bibtex Style

@conference{data15,
author={Ruei Sian Jheng and En Tzu Wang and Arbee L. P. Chen},
title={Determining Top-K Candidates by Reverse Constrained Skyline Queries},
booktitle={Proceedings of 4th International Conference on Data Management Technologies and Applications - Volume 1: DATA,},
year={2015},
pages={101-110},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005498601010110},
isbn={978-989-758-103-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of 4th International Conference on Data Management Technologies and Applications - Volume 1: DATA,
TI - Determining Top-K Candidates by Reverse Constrained Skyline Queries
SN - 978-989-758-103-8
AU - Jheng R.
AU - Wang E.
AU - Chen A.
PY - 2015
SP - 101
EP - 110
DO - 10.5220/0005498601010110