Skip to main content

Distance-based representative skyline

Publication ,  Conference
Tao, Y; Ding, L; Lin, X; Pei, J
Published in: Proceedings - International Conference on Data Engineering
July 8, 2009

Given an integer k, a representative skyline contains the k skyline points that best describe the tradeoffs among different dimensions offered by the full skyline. Although this topic has been previously studied, the existing solution may sometimes produce k points that appear in an arbitrarily tiny cluster, and therefore, fail to be representative. Motivated by this, we propose a new definition of representative skyline that minimizes the distance between a non-representative skyline point and its nearest representative. We also study algorithms for computing distance-based representative skylines. In 2D space, there is a dynamic programming algorithm that guarantees the optimal solution. For dimensionality at least 3, we prove that the problem is NP-hard, and give a 2-approximate polynomial time algorithm. Using a multidimensional access method, our algorithm can directly report the representative skyline, without retrieving the full skyline. We show that our representative skyline not only better captures the contour of the entire skyline than the previous method, but also can be computed much faster. © 2009 IEEE.

Duke Scholars

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

July 8, 2009

Start / End Page

892 / 903
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Tao, Y., Ding, L., Lin, X., & Pei, J. (2009). Distance-based representative skyline. In Proceedings - International Conference on Data Engineering (pp. 892–903). https://doi.org/10.1109/ICDE.2009.84
Tao, Y., L. Ding, X. Lin, and J. Pei. “Distance-based representative skyline.” In Proceedings - International Conference on Data Engineering, 892–903, 2009. https://doi.org/10.1109/ICDE.2009.84.
Tao Y, Ding L, Lin X, Pei J. Distance-based representative skyline. In: Proceedings - International Conference on Data Engineering. 2009. p. 892–903.
Tao, Y., et al. “Distance-based representative skyline.” Proceedings - International Conference on Data Engineering, 2009, pp. 892–903. Scopus, doi:10.1109/ICDE.2009.84.
Tao Y, Ding L, Lin X, Pei J. Distance-based representative skyline. Proceedings - International Conference on Data Engineering. 2009. p. 892–903.

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

July 8, 2009

Start / End Page

892 / 903