Blog
About

19
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Approximation algorithms for aggregate queries on uncertain data

      Read this article at

      ScienceOpenPublisher
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Analyses of big data sets often require aggregate queries on uncertain data with various types of data that are computationally complex. In this paper, the results of aggregate queries on uncertain data are defined to include all possible values and their corresponding probabilities. Dynamic programming is then used to solve the Distribution Sum (DSUM) algorithm using a Greedy-based Distribution Sum and a Binary Merge based Distribution Sum approximation algorithms, which both can be applied to tuple-level and attribute-level uncertainty models. The time and space complexities of the algorithms are determined theoretically as well as the error range of the results. Tests demonstrates that these two approximation algorithms with a 1% allowable error shorten the execution times by 15%-21% and 22%-32%, respectively.

          Abstract

          摘要 随着大数据时代的到来, 不确定性数据上的聚合查询面临形式多样、计算复杂等挑战。该文将不确定性数据上聚合查询的结果定义为所有可能的值以及对应的概率。基于动态规划思想的求解"和"的分布 (distribution sum, DSUM) 精确算法, 提出贪心的"和"的分布 (greedy distribution sum, GDSUM) 和折半合并的"和"的分布 (binary merge distribution sum, BMDSUM) 的近似算法, 这2种算法都能应用于元组级不确定性模型和属性级不确定性模型; 并通过理论分析, 给出算法的时间和空间复杂度以及最终结果的误差范围。实验结果表明:误差设定为1%时, 2种近似算法分别能缩短执行时间15%~21%和22%~32%。

          Related collections

          Author and article information

          Journal
          J Tsinghua Univ (Sci & Technol)
          Journal of Tsinghua University (Science and Technology)
          Tsinghua University Press
          1000-0054
          15 March 2018
          14 March 2018
          : 58
          : 3
          : 231-236
          Affiliations
          1College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
          2Zhejiang Hongcheng Computer Systems Co., Ltd., Hangzhou 310009, China
          Author notes
          *Corresponding author: CHEN Ling, E-mail: lingchen@ 123456zju.edu.cn
          Article
          j.cnki.qhdxxb.2018.26.015
          10.16511/j.cnki.qhdxxb.2018.26.015
          Copyright © Journal of Tsinghua University

          This is an open-access article distributed under the terms of the Creative Commons Attribution 4.0 Unported License (CC BY-NC 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. See https://creativecommons.org/licenses/by-nc/4.0/.

          Comments

          Comment on this article