【24h】

Parallel Top-k Query Processing on Uncertain Strings Using MapReduce

机译:使用MapReduce对不确定字符串进行并行Top-k查询处理

获取原文

摘要

Top-k query is an important and essential operator for data analysis over string collections. However, when uncertainty comes into big data, it calls for new parallel algorithms for efficient query processing on large scale uncertain strings. In this paper, we proposed a MapReduce-based parallel algorithm, called MUSK, for answering top-k queries over large scale uncertain strings. We used the probabilistic n-grams to generate key-value pairs. To improve the performance, a novel lower bound for expected edit distance was derived to prune strings based on a new defined function gram mapping distance. By integrating the bound with TA, the filtering power in the Map stage was optimized effectively to decrease the transmission cost. Comprehensive experimental results on both real-world and synthetic datasets showed that MUSK outperformed the baseline approach with speeds up to 6 times in the best case, which indicated good scalability over large datasets.
机译:top-k查询是对字符串集合进行数据分析的重要且必不可少的运算符。但是,当不确定性进入大数据时,它需要新的并行算法来对大规模不确定性字符串进行有效的查询处理。在本文中,我们提出了一种基于MapReduce的并行算法,称为MUSK,用于回答大规模不确定字符串上的前k个查询。我们使用概率n元语法生成键值对。为了提高性能,基于新定义的函数gram映射距离,将预期的编辑距离的下限导出到修剪字符串中。通过将边界与TA集成在一起,有效地优化了Map阶段的滤波能力,从而降低了传输成本。在真实数据集和合成数据集上的综合实验结果表明,在最佳情况下,MUSK的性能优于基线方法,最高可达6倍,这表明在大型数据集上具有良好的可伸缩性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号