众包环境下多谓词查询优化

• 作者: 冯剑红 冯建华 翁学平 胡卉芪
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 众包选择查询 采样 选择性
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 理论与研发
• 页码范围: 7-13
• 页数: 7页
• 分类号: TP391
• 字数: 7247字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1507-0174

摘要

近年来，众包查询优化得到了数据库领域的广泛关注。主要研究了众包多谓词选择查询问题——借助于人力找到满足多谓词查询条件的对象。一种简单的方法是枚举数据集中的对象，对于每个对象判断是否满足每条谓词。它产生的代价是|R|?n，其中|R|为数据集中对象的数量，n为谓词的数量。很显然，当处理大数据集或者查询包含较多谓词的时候，简单方法的代价是非常昂贵的。由于不同的谓词具有不同的选择性，如果首先验证高选择性的谓词，那么在验证剩余谓词的时候，就可以避免验证不满足高选择性谓词的对象。因此，采用一个好的谓词顺序实现众包选择查询可以显著减少人工代价。然而，实际中很难获得最佳的谓词序列。针对该问题，提出了一种基于采样的框架来获得高质量的查询序列。为了控制查询序列生成的成本，设计了基于随机序列的最优选择方法，该方法通过随机选择序列获得最终的谓词顺序。由于基于随机序列的选择方法可能产生较大的代价，为了减少开销，提出了一种基于过滤的序列选择方法。通过在众包平台上使用真实数据集评测了提出的方法，实验结果表明，该方法能够显著减少查询序列生成的代价，同时获得高质量的查询序列。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	冯建华	清华大学计算机科学与技术系	51	794	13.0	27.0
2	冯剑红	清华大学计算机科学与技术系	2	147	2.0	2.0
3	胡卉芪	清华大学计算机科学与技术系	2	2	1.0	1.0
4	翁学平	清华大学计算机科学与技术系	1	2	1.0	1.0