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 $\epsilon$ and required confidence $\mu$. 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.


翻译:图形基本特征估计是估算数据图表中查询图表嵌入数量的问题。例如,在子谱匹配算法的查询规划中,出现这一根本问题。有两个主要方法可以解决问题:抽样和简要说明; 概要(或摘要)法是快速和准确的,如果对图表信息进行综合,如果对图表进行精确的收集; 然而,这些方法由于总和和和固有假设中的信息丢失而存在大量错误。 抽样方法是公正的,但因样本空间大而存在很大的估计差异。 为了解决这些限制,我们建议了Alley,这是一种混合方法,将取样和合成结合起来。 Alley使用的一种混合方法。 一种新型抽样战略,即随机行走和交叉,有效地缩小样本空间,2个分支法是快速和准确的,3 一种新颖的采矿方法,即提取和指数,作为必然难以通过抽样估计的组合。通过在网上估计阶段使用这些方法,我们可以有效地减少样本空间,同时确保公正性。我们确定,All$最差的运行和接近性质量保证,所有美元的运行和接近性质量保证,一个州级的试验需要所有最差的基数。

0
下载
关闭预览

相关内容

【论文推荐】文本摘要简述
专知会员服务
68+阅读 · 2020年7月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
107+阅读 · 2020年5月15日
【陈天奇】TVM:端到端自动深度学习编译器,244页ppt
专知会员服务
85+阅读 · 2020年5月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
100+阅读 · 2019年10月9日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
1+阅读 · 2021年5月18日
Arxiv
4+阅读 · 2018年3月14日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员