An efficient approach to finding potential products continuously. (April 2017)

• Record Type: Journal Article
• Authors: Hsueh, Yu-Ling; Ma, He; Lin, Chia-Chun; Zimmermann, Roger
• Is Part Of: Information systems. Volume 65(2017)
• Page Start: 22
• Page End: 35
• Publication Date: 2017-04
• Subjects: Skyline Queries -- Query Processing -- Multi-dimensional Databases -- Data Management; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2016.10.003
• Languages: English
• ISSNs: 0306-4379

Abstract

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. Abstract : Highlights: An 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.