Identifying the Most Endangered Objects from Spatial Datasets

Hua Lu, Man Lung Yiu

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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, New Orleans, LA, USA, June 2-4, 2009, Proceedings
EditorsMarianne Winslett
Number of pages19
Publication date2009
ISBN (Print)978-3-642-02278-4
ISBN (Electronic)978-3-642-02279-1
Publication statusPublished - 2009
Externally publishedYes
Event21st International Conference on Scientific and Statistical Database Management - New Orleans, United States
Duration: 2 Jun 20094 Jun 2009
Conference number: 21


Conference21st International Conference on Scientific and Statistical Database Management
Country/TerritoryUnited States
CityNew Orleans
SeriesLecture Notes in Computer Science


  • Quality Attribute
  • Neighborhood Distance
  • Spatial Object
  • Skyline Query
  • Spatial Query

Cite this