Identifying the most endangered objects from spatial datasets

Hua Lu, Man Lung Yiu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

Real-life spatial objects are usually described by their geographic locations (e.g., longitude and latitude), and multiple quality attributes. Conventionally, spatial data are queried by two orthogonal aspects: spatial queries involve geographic locations only; skyline queries are used to retrieve those objects that are not dominated by others on all quality attributes. Specifically, an object p i is said to dominate another object p j if p i is no worse than p j on all quality attributes and better than p j on at least one quality attribute. In this paper, we study a novel query that combines both aspects meaningfully. Given two spatial datasets P and S, and a neighborhood distance δ, the most endangered object query (MEO) returns the object s∈ ∈S such that within the distance δ from s, the number of objects in P that dominate s is maximized. MEO queries appropriately capture the needs that neither spatial queries nor skyline queries alone have addressed. They have various practical applications such as business planning, online war games, and wild animal protection. Nevertheless, the processing of MEO queries is challenging and it cannot be efficiently evaluated by existing solutions. Motivated by this, we propose several algorithms for processing MEO queries, which can be applied in different scenarios where different indexes are available on spatial datasets. Extensive experimental results on both synthetic and real datasets show that our proposed advanced spatial join solution achieves the best performance and it is scalable to large datasets.
Original languageEnglish
Title of host publicationScientific and Statistical Database Management - 21st International Conference, SSDBM 2009, Proceedings
Pages608-626
Number of pages19
DOIs
Publication statusPublished - 27 Aug 2009
Externally publishedYes
Event21st International Conference on Scientific and Statistical Database Management, SSDBM 2009 - New Orleans, LA, United States
Duration: 2 Jun 20094 Jun 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5566 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Scientific and Statistical Database Management, SSDBM 2009
Country/TerritoryUnited States
CityNew Orleans, LA
Period2/06/094/06/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this