海量高维向量的并行Top-k连接查询

摘要：

在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.

关键词：高维向量、MapReduce框架、Top-k连接查询、大数据

所属期刊栏目：38

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61379050,91224008;国家“八六三”高技术研究发展计划项目基金2013AA013204;高等学校博士学科点专项科研基金20130004130001;中国人民大学科学研究基金11XNL010;This research was partially supported by the grants from the Natural Science Foundation of China.61379050,91224008;the National High Technology Research and Development Program863 Program of China2013AA013204;Specialized Research Fund for the Doctoral Program of Higher Education20130004130001;the Fundamental Research Funds for the Central Universities,and the Research Funds of Renmin University11XNL010

在线出版日期：2015-04-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：86-98