On computing farthest dominated locations

Hua Lu, Man Lung Yiu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)


In reality, spatial objects (e.g., hotels) not only have spatial locations but also have quality attributes (e.g., price, star). An object p is said to dominate another one p′, if p is no worse than p′ with respect to every quality attribute and p is better on at least one quality attribute. Traditional spatial queries (e.g., nearest neighbor, closest pair) ignore quality attributes, whereas conventional dominance-based queries (e.g., skyline) neglect spatial locations. Motivated by these observations, we propose a novel query by combining spatial and quality attributes together meaningfully. Given a set of (competitors') spatial objects P, a set of (candidate) locations L, and a quality vector \Psi as design competence (for L), the farthest dominated location (FDL) query retrieves the location ε L such that the distance to its nearest dominating object in P is maximized. FDL queries are suitable for various spatial decision support applications such as business planning, wild animal protection, and digital battle field systems. As FDL queries cannot be readily solved by existing techniques, we develop several efficient R-tree-based algorithms for processing FDL queries, which offer users a range of selections in terms of different indexes available on the data. We also generalize our methods to support the generic distance metric and other interesting query types. The experimental results on both real and synthetic data sets disclose the performance of those algorithms, and reveal the most efficient and scalable one among them.
Original languageEnglish
Article number5432173
Pages (from-to)928-941
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
Publication statusPublished - 5 May 2011


  • database management
  • query processing
  • Spatial objects

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this