Spatial skyline queries: An efficient geometric algorithm

Wanbin Son; Mu Woong Lee; Hee Kap Ahn; Seung Won Hwang

doi:10.1007/978-3-642-02982-0_17

Spatial skyline queries: An efficient geometric algorithm

Wanbin Son, Mu Woong Lee, Hee Kap Ahn, Seung Won Hwang

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

28 Citations (Scopus)

Abstract

As more data-intensive applications emerge, advanced retrieval semantics, such as ranking and skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm VS ², despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and VS ² in several aspects.

Original language	English
Title of host publication	Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings
Pages	247-264
Number of pages	18
DOIs	https://doi.org/10.1007/978-3-642-02982-0_17
Publication status	Published - 2009
Event	11th International Symposium on Spatial and Temporal Databases, SSTD 2009 - Aalborg, Denmark Duration: 2009 Jul 8 → 2009 Jul 10

Publication series

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

Other

Other	11th International Symposium on Spatial and Temporal Databases, SSTD 2009
Country/Territory	Denmark
City	Aalborg
Period	09/7/8 → 09/7/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-02982-0_17

Cite this

Son, W., Lee, M. W., Ahn, H. K., & Hwang, S. W. (2009). Spatial skyline queries: An efficient geometric algorithm. In Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings (pp. 247-264). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5644 LNCS). https://doi.org/10.1007/978-3-642-02982-0_17

@inproceedings{0ff869ad0ae94b44a6d3c6b1857f4298,

title = "Spatial skyline queries: An efficient geometric algorithm",

abstract = "As more data-intensive applications emerge, advanced retrieval semantics, such as ranking and skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm VS 2, despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and VS 2 in several aspects.",

author = "Wanbin Son and Lee, {Mu Woong} and Ahn, {Hee Kap} and Hwang, {Seung Won}",

year = "2009",

doi = "10.1007/978-3-642-02982-0_17",

language = "English",

isbn = "3642029817",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "247--264",

booktitle = "Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings",

note = "11th International Symposium on Spatial and Temporal Databases, SSTD 2009 ; Conference date: 08-07-2009 Through 10-07-2009",

}

Son, W, Lee, MW, Ahn, HK & Hwang, SW 2009, Spatial skyline queries: An efficient geometric algorithm. in Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5644 LNCS, pp. 247-264, 11th International Symposium on Spatial and Temporal Databases, SSTD 2009, Aalborg, Denmark, 09/7/8. https://doi.org/10.1007/978-3-642-02982-0_17

Spatial skyline queries: An efficient geometric algorithm. / Son, Wanbin; Lee, Mu Woong; Ahn, Hee Kap et al.
Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings. 2009. p. 247-264 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5644 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Spatial skyline queries

T2 - 11th International Symposium on Spatial and Temporal Databases, SSTD 2009

AU - Son, Wanbin

AU - Lee, Mu Woong

AU - Ahn, Hee Kap

AU - Hwang, Seung Won

PY - 2009

Y1 - 2009

N2 - As more data-intensive applications emerge, advanced retrieval semantics, such as ranking and skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm VS 2, despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and VS 2 in several aspects.

AB - As more data-intensive applications emerge, advanced retrieval semantics, such as ranking and skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm VS 2, despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and VS 2 in several aspects.

UR - http://www.scopus.com/inward/record.url?scp=70350352537&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350352537&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02982-0_17

DO - 10.1007/978-3-642-02982-0_17

M3 - Conference contribution

AN - SCOPUS:70350352537

SN - 3642029817

SN - 9783642029813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 247

EP - 264

BT - Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings

Y2 - 8 July 2009 through 10 July 2009

ER -

Son W, Lee MW, Ahn HK, Hwang SW. Spatial skyline queries: An efficient geometric algorithm. In Advances in Spatial and Temporal Databases - 11th International Symposium, SSTD 2009, Proceedings. 2009. p. 247-264. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-02982-0_17

Spatial skyline queries: An efficient geometric algorithm

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this