TY - GEN
T1 - Identifying the most endangered objects from spatial datasets
AU - Lu, Hua
AU - Yiu, Man Lung
PY - 2009/8/27
Y1 - 2009/8/27
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=69049096390&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02279-1_43
DO - 10.1007/978-3-642-02279-1_43
M3 - Conference article published in proceeding or book
SN - 3642022782
SN - 9783642022784
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 608
EP - 626
BT - Scientific and Statistical Database Management - 21st International Conference, SSDBM 2009, Proceedings
T2 - 21st International Conference on Scientific and Statistical Database Management, SSDBM 2009
Y2 - 2 June 2009 through 4 June 2009
ER -