IEEE Transactions on Knowledge and Data Engineering · 2016 · 49 citations · 25 references
ComputingComputer ScienceAlgorithmsDatabasesUncertainty QuantificationData WarehousingProbabilistic RetrievalQuery OptimizationQuery ProcessingSearch SystemsProbabilistic RankingProbabilistic Retrieval ModelsPruningTop-k Query Processing
Product selection under uncertainty has been addressed by probabilistic dynamic skyline queries, but these require a threshold, focus only on high‑probability objects, and yield unstable results. This study introduces an uncertain dynamic skyline query and a top‑k favorite probabilistic products query to overcome the limitations of existing PDS queries. We develop pruning strategies and efficient algorithms, including a parallelized TFPP algorithm, to compute the UDS and TFPP queries. Experiments demonstrate that the proposed algorithms are efficient and effective across diverse settings.
With the development of the economy, products are significantly enriched, and uncertainty has been their inherent quality. The probabilistic dynamic skyline (PDS) query is a powerful tool for customers to use in selecting products according to their preferences. However, this query suffers several limitations: it requires the specification of a probabilistic threshold, which reports undesirable results and disregards important results; it only focuses on the objects that have large dynamic skyline probabilities; and, additionally, the results are not stable. To address this concern, in this paper, we formulate an uncertain dynamic skyline (UDS) query over a probabilistic product set. Furthermore, we propose effective pruning strategies for the UDS query, and integrate them into effective algorithms. In addition, a novel query type, namely the top <inline-formula><tex-math notation="LaTeX">$k$</tex-math> </inline-formula> favorite probabilistic products (TFPP) query, is presented. The TFPP query is utilized to select <inline-formula> <tex-math notation="LaTeX">$k$</tex-math></inline-formula> products which can meet the needs of a customer set at the maximum level. To tackle the TFPP query, we propose a TFPP algorithm and its efficient parallelization. Extensive experiments with a variety of experimental settings illustrate the efficiency and effectiveness of our proposed algorithms.
25
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · Journal of Computer and System Sciences · 2003 · 941 citations
Progressive skyline computation in database systems
Dimitris Papadias, Yufei Tao, Greg Fu et al. · ACM Transactions on Database Systems · 2005 · 886 citations
Probabilistic skylines on uncertain data
Jian Pei, Bin Jiang, Xuemin Lin et al. · 2007 · 461 citations
Mehdi Sharifzadeh, Cyrus Shahabi · 2006 · 271 citations
Efficient computation of reverse skyline queries
Evangelos Dellis, Bernhard Seeger · 2007 · 241 citations