TY - GEN
T1 - Escaping a dominance region at minimum cost
AU - Kim, Youngdae
AU - You, Gae Won
AU - Hwang, Seung Won
PY - 2008
Y1 - 2008
N2 - Skyline queries have gained attention as an effective way to identify desirable objects that are "not dominated" by another object in the dataset. From market perspective, such objects can be viewed as marketable, as each of such objects has at least one competitive edge against all the other objects, or not dominated. In other words, non-skyline objects are not marketable, as there always exists another product excelling in all the attributes. The goal of this paper is, for such non-skyline objects, to identify the cost-minimal enhancement to become a skyline point to gain marketability. More specifically, we abstract this problem as a mixed integer programming problem and develop a novel algorithm for efficiently identifying the optimal solution. Through extensive experiments using synthetic datasets, we show that our proposed framework is both efficient and scalable over extensive experiment settings.
AB - Skyline queries have gained attention as an effective way to identify desirable objects that are "not dominated" by another object in the dataset. From market perspective, such objects can be viewed as marketable, as each of such objects has at least one competitive edge against all the other objects, or not dominated. In other words, non-skyline objects are not marketable, as there always exists another product excelling in all the attributes. The goal of this paper is, for such non-skyline objects, to identify the cost-minimal enhancement to become a skyline point to gain marketability. More specifically, we abstract this problem as a mixed integer programming problem and develop a novel algorithm for efficiently identifying the optimal solution. Through extensive experiments using synthetic datasets, we show that our proposed framework is both efficient and scalable over extensive experiment settings.
UR - http://www.scopus.com/inward/record.url?scp=52949113484&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=52949113484&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-85654-2_72
DO - 10.1007/978-3-540-85654-2_72
M3 - Conference contribution
AN - SCOPUS:52949113484
SN - 3540856536
SN - 9783540856535
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 800
EP - 807
BT - Database and Expert Systems Applications - 19th International Conference, DEXA 2008, Proceedings
T2 - 19th International Conference on Database and Expert Systems Applications, DEXA 2008
Y2 - 1 September 2008 through 5 September 2008
ER -