Efficient pruning for top-K ranking queries on attribute-wise uncertain datasets

详细信息    查看全文

• 作者：Jianwen Chen ; Ling Feng
• 关键词：Pruning ; Top ; K ranking query ; Uncertain dataset
• 刊名：Journal of Intelligent Information Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：48
• 期：1
• 页码：215-242
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Information Storage and Retrieval; Data Structures, Cryptology and Information Theory; Artificial Intelligence (incl. Robotics); IT in Business; Document Preparation and Text Processing;
• 出版者：Springer US
• ISSN：1573-7675
• 卷排序：48

文摘

Top-K ranking queries in uncertain databases aim to find the top-K tuples according to a ranking function. The interplay between score and uncertainty makes top-K ranking in uncertain databases an intriguing issue, leading to rich query semantics. Recently, a unified ranking framework based on parameterized ranking functions (PRFs) has been formulated, which generalizes many previously proposed ranking semantics. Under the PRFs based ranking framework, efficient pruning approach for Top-K ranking on datasets with tuple-wise uncertainty has been well studied in the literature. However, this cannot be applied to top-K ranking on datasets with attribute-wise uncertainty, which are often natural and useful in analyzing uncertain data in many applications. This paper aims to develop efficient pruning techniques for top-K ranking on datasets with attribute-wise uncertainty under the PRFs based ranking framework, which has not been well studied in the literature. We first develop a Tuple Insertion Based Algorithm for computing each tuple’s PRF value, which reduce the time cost from the state of the art cubic order of magnitude to quadratic order of magnitude. Based on the Tuple Insertion Based Algorithm, three pruning strategies are developed to further reduce the time cost. The mathematics of deriving the Tuple Insertion Based Algorithm and corresponding pruning strategies are also presented. At last, we show that our pruning algorithms can also be applied to the computation of the top-k aggregate queries. The experimental results on both real and synthetic data demonstrate the effectiveness and efficiency of the proposed pruning techniques.