专栏首页arxiv.org翻译专栏[技术报告]将抽样和概要与最坏情况下的最佳运行时间和质量保证相结合的图形模式基数估计

[技术报告]将抽样和概要与最坏情况下的最佳运行时间和质量保证相结合的图形模式基数估计

图模式基数估计是估计查询图在数据图中的嵌入数量的问题。例如,在子图匹配算法的查询计划期间会出现此基本问题。解决问题有两种主要方法:抽样和提要。如果概要能够很好地捕获图形信息,则基于概要(或摘要)的方法将快速而准确。但是,由于这些方法在汇总和固有假设期间会丢失信息,因此会出现较大的错误。基于采样的方法没有偏见,但由于样本空间较大,因此存在较大的估计方差。

为了解决这些局限性,我们提出了Alley,一种结合了采样和概要的混合方法。 Alley采用了1)一种新颖的采样策略,即随机走步与相交,有效地减少了样本空间; 2)分支以进一步减少方差; 3)一种新颖的挖掘方法,将纠结的模式提取并索引为概要,这些概要固有地难以估计通过采样。通过在在线估计阶段使用它们,我们可以有效减少样本空间,同时仍确保无偏见。我们确定,对于任何给定的误差范围ϵ和所需的置信度μ,Alley都具有最坏情况下的最佳运行时间和近似质量保证。除了Alley的理论方面之外,我们的大量实验还表明Alley与最新技术相比,其准确度和效率都高出几个数量级。

原文题目:[Technical Report] Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation

原文:Graph pattern cardinality estimation is the problem of estimating the number of embeddings of a query graph in a data graph. This fundamental problem arises, for example, during query planning in subgraph matching algorithms. There are two major approaches to solving the problem: sampling and synopsis. Synopsis (or summary)-based methods are fast and accurate if synopses capture information of graphs well. However, these methods suffer from large errors due to loss of information during summarization and inherent assumptions. Sampling-based methods are unbiased but suffer from large estimation variance due to large sample space.

To address these limitations, we propose Alley, a hybrid method that combines both sampling and synopses. Alley employs 1) a novel sampling strategy, random walk with intersection, which effectively reduces the sample space, 2) branching to further reduce variance, and 3) a novel mining approach that extracts and indexes tangled patterns as synopses which are inherently difficult to estimate by sampling. By using them in the online estimation phase, we can effectively reduce the sample space while still ensuring unbiasedness. We establish that Alley has worst-case optimal runtime and approximation quality guarantees for any given error bound ϵ and required confidence μ. In addition to the theoretical aspect of Alley, our extensive experiments show that Alley outperforms the state-of-the-art methods by up to orders of magnitude higher accuracy with similar efficiency.

原文链接:https://arxiv.org/abs/2103.13681

原文作者:Kyoungmin Kim, Hyeonji Kim, George Fletcher, Wook-Shin Han

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [技术报告]将抽样和梗概与最坏情况下最佳运行时间和质量保证用于图模式基数估计(CS)

    图模式基数估计是估计查询图在数据图中嵌入的数量。这个基本问题就产生在,比如说,子图匹配算法中的查询规划。解决这个问题有两种主要方法:采用和概要。如果概要能很好地...

    用户8440711
  • 基于知识图谱的APT组织追踪治理

    高级持续性威胁(APT)正日益成为针对政府和企业重要资产的不可忽视的网络空间重大威胁。由于APT攻击往往具有明确的攻击意图,并且其攻击手段具备极高的隐蔽性和潜伏...

    绿盟科技研究通讯
  • 【PMP】八、项目质量管理

    6.测试与检查规划 7.会议 1.质量管理计划 2.质量测量指标 3.项目管理计划更新

    心跳包
  • 6.2万字报告剖析「智能写作」全貌,从落地产品看NLP商业化突破

    语言是人与人交流的工具,也是网络用户与互联网连接的方式。传统人类写作是以表达和传递为目的的对主观和客观世界的记录,从日常生活到资讯、法律、办公、金融等行业都有广...

    机器之心
  • PMP需要掌握的139个工具和技术

    版权声明:欢迎交流,菲宇运维!

    菲宇
  • 探索 | 用于云服务和应用程序的网络安全可编程性的数据日志管理

    在本文中,我们提出了用于访问安全上下文的灵活抽象层概念。它旨在通过部署在云应用程序和IoT设备中的轻量级检查和执行挂钩来编程和收集数据。

    CloudBest
  • 深度 | 2017CV技术报告:从3D物体重建到人体姿态估计

    机器之心
  • 机器学习模型中的 bug 太难找?DeepMind 呈上了三种好方法!

    AI 科技评论按:计算机编程发展至今,bug 和软件就一直如影随形。多年来,软件开发人员已经创建了一套在部署之前进行测试和调试的最佳方法,但这些方法并不适用于如...

    AI研习社
  • 机器学习模型中的 bug 太难找?DeepMind 呈上了三种好方法!

    AI 科技评论按:计算机编程发展至今,bug 和软件就一直如影随形。多年来,软件开发人员已经创建了一套在部署之前进行测试和调试的最佳方法,但这些方法并不适用于如...

    AI科技评论
  • 详解数据仓库的实施步骤

    建立数据仓库是一个解决企业数据问题应用的过程,是企业信息化发展到一定阶段必不可少的一步,也是发展数据化管理的重要基础。数仓的知识市面上的书籍和文章不少,但是实际...

    大数据学习与分享
  • 渗透测试概述·什么是渗透测试

    渗透测试(penetration test,pentest)是实施安全评估(即审计)的具体手段。

    C4rpeDime
  • 【ICML2018】63篇强化学习论文全解读

    【导读】一年一度的国际机器学习会议( ICML ),于7月15日在瑞典斯德哥尔摩闭幕,ICML 的会议日程之紧凑,会议内容之丰富,令人目不暇接。今年从2,473...

    AI科技大本营
  • 【干货】ICML2018:63篇强化学习论文精华解读!

    【新智元导读】机器学习顶会ICML 2018从2473份提交论文中接收了621篇,其中有63余篇强化学习相关论文,作者将这些论文分成了多个类别,并对每篇文章的核...

    新智元
  • 原创重磅!数据分析在交易欺诈领域的应用

    一 交易欺诈简介 1.1 交易欺诈简介 交易欺诈一般是指第三方欺诈,即所发生的交易非持卡人本人意愿的交易。通常是不法分子利用各种渠道窃取卡信息,进行伪造卡作案。...

    CDA数据分析师
  • 史上最全《知识图谱》2020综述论文,18位作者, 130页pdf

    在本文中,我们对知识图谱进行了全面的介绍,在需要开发多样化、动态、大规模数据收集的场景中,知识图谱最近引起了工业界和学术界的极大关注。在大致介绍之后,我们对用于...

    新智元
  • 深度学习模型的不确定性

    本文由Google的研究科学家Jasper Snoek和Google的研究工程师Zachary Nado发布于GoogleAI博客,atyun编译。

    AiTechYun
  • 12个场景应用,百余种算法,AI是如何攻占经济学的?

    2020年2月7日,在第34届美国人工智能协会年会AAAI 2020现场,深度学习三巨头齐聚,“计算机视觉”与“机器学习”分座两旁,对最佳论文虎视眈眈。

    AI科技评论
  • 李飞飞等ICLR2019论文:构建人类眼睛感知评估

    我们引入了两种变体:一种是在自适应时间约束下测量视觉感知,以确定模型输出显示为真实的阈值(例如250毫秒),另一种是在无时间约束的假图像和真实图像上测量人为错误...

    新智元
  • 新时代运维监控能力的进化——天网云用户体验监控平台实践

    运维团队审视业务质量监控能力时,有九个问题值得思考,九问运维后,我们重新审视传统的运维监控能力是否仍然能够满足业务对质量的要求,结合当下移动互联网与新兴的业务形...

    织云平台团队

扫码关注云+社区

领取腾讯云代金券