Paper Info
Title
An efficient approach to finding potential products continuously.
Abstract
Skyline points and queries are important in the context of processing datasets with multiple dimensions. As skyline points can be viewed as representing marketable products that are useful for clients and business owners, one may also consider non-skyline points that are highly competitive with the current skyline points. We address the problem of continuously finding such potential products from a dynamic d-dimensional dataset, and formally define a potential product and its upgrade promotion cost. In this paper, we propose the CP-Sky algorithm, an efficient approach for continuously evaluating potential products by utilizing a second-order skyline set, which consists of candidate points that are closest to regular skyline points (also termed the first-order skyline set), to facilitate efficient computations and updates for potential products. With the knowledge of the second-order skyline set, CP-Sky enables the system to (1) efficiently find substitute skyline points from the second-order skyline set only if a first-order skyline point is removed, and (2) continuously retrieve the top-k potential products. Within this context, the Approximate Exclusive Dominance Region algorithm (AEDR) is proposed to reduce the computational complexity of determining a candidate set for second-order skyline updates over a dynamic data set without affecting the result accuracy. Additionally, we extend the CP-Sky algorithm to support the computations of top-k potential products. Finally, we present experimental results on data sets with various distributions to demonstrate the performance and utility of our approach. HighlightsAn efficient approach to solving the problem of continuously potential products from a dynamic d-dimensional dataset.Efficiently finding substitute skyline points from the second-order skyline set only if a first-order skyline point is removed.The Approximate Exclusive Dominance Region algorithm (AEDR) is proposed to reduce the computational complexity of determining a candidate set for second-order skyline updates over a dynamic data set.Numerous experiments with various distributions indicating that our proposed algorithm outperform existing approaches when continuously finding potential products.
Year
DOI
Venue
2017
10.1016/j.is.2016.10.003
Inf. Syst.
Keywords
Field
DocType
Skyline Queries,Query Processing,Multi-dimensional Databases,Data Management
Skyline,Data mining,Data set,Computer science,Upgrade,Dynamic data,Data management,Multiple time dimensions,Database,Computation,Computational complexity theory
Journal
Volume
Issue
ISSN
65
C
0306-4379
Citations 
PageRank 
References 
0
0.34
28
Authors
4
Name
Order
Citations
PageRank
Yu-Ling Hsueh1709.56
He Ma2122.56
Chia-Chun Lin312815.00
Roger Zimmermann41735147.98