基于单指令级并行的快速求交算法
宋省身1,杨岳湘1,江宇21. 国防科学技术大学计算机学院, 湖南 长沙 410000;2. 西北核技术研究所, 陕西 西安 710024
收稿日期:2017-07-04出版日期:2018-03-20发布日期:2018-03-13作者简介:宋省身(1990— ),男,博士研究生,研究方向为搜索引擎数据结构设计与查询效率优化. E-mail:songxingshen@nudt.edu.cn基金资助:湖南省自然科学基金资助项目(2016JJ2007)Efficient multiple sets intersection using SIMD instructions
SONG Xing-shen1, YANG Yue-xiang1, JIANG Yu21. College of Computer, National University of Defense Technology, Changsha 410000, Hunan, China;
2. Northwest Institute of Nuclear Technology, Xian 710024, Shaanxi, China
Received:2017-07-04Online:2018-03-20Published:2018-03-13摘要/Abstract
摘要： 布尔查询中的求交操作被广泛应用于各种信息系统中,是进行文档检索的基本操作之一。其基本形式可以视作多个有序整数序列的交集问题,而提高求交运算的效率是当前研究的重点。在传统求交算法的基础上,利用单指令多数据流(single instruction multiple data, SIMD)并行指令集,针对其核心的搜索步骤,提出了两种基于SIMD的跳跃式搜索算法。该算法在提高性能的同时,能有效适配在传统多倒排链求交算法中。实验证明,优化后的算法相比未使用SIMD的情况下有了很大的提升,甚至优于SIMD优化后的两两相交算法,性能最高提升37.3%。
PDF全文下载地址:
http://lxbwk.njournal.sdu.edu.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=2916
