基于长度分区的集合相似度查询方法的研究
发布时间：2021-08-10 22:33
集合作为一种高效的数据表示手段,已经应用于很多领域,例如可用于表示用户听音乐的喜好,购物网站的商品,生物信息工程中的基因序列等。近年来,随着电子商务、信息检索、生物信息工程等领域的快速发展,数据集合的规模和复杂度不断增大。快速处理海量且复杂的集合相似度数据已是近年研究的热点。在相似度查询计算中,往往会存在一些因为集合长度太长、或者太短导致两个集合完全不可能满足给定的相似度阈值的情况,对这些集合进行过滤或计算时消耗了大量的不必要的时间与空间。为解决此问题,本文首先提出一种基于长度分区的集合相似度查询方法。将长度分区的思想与经典的相似度查询算法ScanCount相结合,通过数据预处理、长度分区及高效的索引结构LenSegII（Length Segmented Invert Indexes）快速过滤不可能相似度的记录,从而提升算法效率。此外,设计更为精简的计数数组,从而降低了空间开销。在多个数据集上的实验表明本方法具有更高的时间和空间效率。现今大多数集合相似度查询算法都是以CPU串行或CPU并行扫描倒排列表的方式工作的,因而效率以及吞吐量都比较低,难以适应大规模及超大规模集合的快速相似度查询...
【文章来源】：昆明理工大学云南省
【文章页数】：68 页
【学位级别】：硕士
【部分图文】：
GPU和CPU每秒浮点操作数
昆明理工大学硕士学位论文8图1.2GPU和CPU存储器带宽文献[41]介绍了双调排序在集合相似度中的运用。文献[42]提出了在图形处理单元（GPU）上的有效集合相似度连接的方案。提出了一种在GPU上集合相似度连接的新方案：使用MinHash来估计两集合间的Jaccard相似度。其主要思想是基于每个集合的元素创建签名，然后比较签名以估计其Jaccard相似性。如果两个集合具有许多一致的签名部分，则它们具有一定程度的相似性。以这种方式，可以在不对所有元素进行耗时的扫描的同时估计Jaccard相似度。此外，只需要存储签名而不是存储集合的所有元素，这也极大地有助于减少存储空间。通过利用GPU的高并行性和MinHash提供的空间效率，可以实现高性能并且不牺牲太多准确性。实验结果表明，该方法比串行版本的CPU实现方法快两个数量级，比并行版本的CPU实现方法快25倍，同时可以生成高度精确的查询结果。ZhouJ等人[44]提出了一套可针对不同数据类型进行并行集合相似度搜索的通用倒排索引框架，同时并提出了一种新的局部敏感哈希处理方式。GalletB等人[51]提出了几种降低GPU相似度自连接算法负载不均衡的方法。由于数据依赖性等问题，使得系统分配给线程的工作负载存在差异。通过考虑分配给每个线程的总工作负载，并强制GPU的硬件调度程序在同一个warp中对具有类似工作负载的线程进行分组，从而减少线程间的负载不平衡情况。ChauhanSS[52]等人提出了一种使用布隆过滤器（Bloomfilters）来进行并行相似性查询方法，该方法使用布隆过滤器来表示文档的特征并与用户的查询进行比较。FengY[53]等人提出了一种在GPU上的、基于前向列表和反向列表的并行文档相似性自连接算法，该算法分两步分别执行文档不同部分来计算文档的相似
现。实际上，Li[24]等人已经将 MinHash 与 GPU 的并行计算能力的组合，在他们的在线学习应用程序中，处理时间至少减少了一个数量级以上。2.6 GPU 结构与线程网络GPU 与 CPU 的不同之处在于：普通 CPU 核心数为 2 或 4 核，而 GPU 的核心数则普遍在 1000 核心以上，所以 GPU 可以其同时运行成千上万的线程，远超一般 CPU，本节介绍了 GPU 结构及 GPU 的线程网络的基本概念。GPU 是通过 PCI-Express（PCIe）总线连接到主机系统的外围设备。该设备包括GPU处理器和板载显存模块。同时 GPU 还包含与图像处理相关的其他部件，因本文算法未涉及到图像处理，故不进行介绍。
【参考文献】：
期刊论文
[1]CUDA-TP:基于GPU的自顶向下完整蛋白质鉴定并行算法[J]. 段琼,田博,陈征,王洁,何增有. 计算机研究与发展. 2018(07)
[2]加强学风建设 ?防治学术腐败[J]. 郭其云,姜建华. 科研管理. 2016(S1)
[3]GPU通用计算及其在计算智能领域的应用[J]. 丁科,谭营. 智能系统学报. 2015(01)
[4]用户搜索意图视角下的Web网页动态泛化研究[J]. 王亚辉. 信息通信. 2014(12)
[5]大数据环境下并行计算模型的研究进展[J]. 潘巍,李战怀. 华东师范大学学报(自然科学版). 2014(05)
[6]云服务平台负载均衡器的网络设计与实践[J]. 夏斌,杜守国. 计算机应用与软件. 2014(08)
[7]运用学术不端文献检测系统检测医学论文存在的问题及对策[J]. 杨晨晨. 编辑学报. 2014(01)
硕士论文
[1]基于大数据平台的用户搜索日志分析和研究[D]. 梁烜彰.华南理工大学 2018
[2]基于聚类的多层关联规则挖掘算法研究与改进[D]. 何晴.上海师范大学 2017
本文编号：3334904
【文章来源】：昆明理工大学云南省
【文章页数】：68 页
【学位级别】：硕士
【部分图文】：
GPU和CPU每秒浮点操作数
昆明理工大学硕士学位论文8图1.2GPU和CPU存储器带宽文献[41]介绍了双调排序在集合相似度中的运用。文献[42]提出了在图形处理单元（GPU）上的有效集合相似度连接的方案。提出了一种在GPU上集合相似度连接的新方案：使用MinHash来估计两集合间的Jaccard相似度。其主要思想是基于每个集合的元素创建签名，然后比较签名以估计其Jaccard相似性。如果两个集合具有许多一致的签名部分，则它们具有一定程度的相似性。以这种方式，可以在不对所有元素进行耗时的扫描的同时估计Jaccard相似度。此外，只需要存储签名而不是存储集合的所有元素，这也极大地有助于减少存储空间。通过利用GPU的高并行性和MinHash提供的空间效率，可以实现高性能并且不牺牲太多准确性。实验结果表明，该方法比串行版本的CPU实现方法快两个数量级，比并行版本的CPU实现方法快25倍，同时可以生成高度精确的查询结果。ZhouJ等人[44]提出了一套可针对不同数据类型进行并行集合相似度搜索的通用倒排索引框架，同时并提出了一种新的局部敏感哈希处理方式。GalletB等人[51]提出了几种降低GPU相似度自连接算法负载不均衡的方法。由于数据依赖性等问题，使得系统分配给线程的工作负载存在差异。通过考虑分配给每个线程的总工作负载，并强制GPU的硬件调度程序在同一个warp中对具有类似工作负载的线程进行分组，从而减少线程间的负载不平衡情况。ChauhanSS[52]等人提出了一种使用布隆过滤器（Bloomfilters）来进行并行相似性查询方法，该方法使用布隆过滤器来表示文档的特征并与用户的查询进行比较。FengY[53]等人提出了一种在GPU上的、基于前向列表和反向列表的并行文档相似性自连接算法，该算法分两步分别执行文档不同部分来计算文档的相似
现。实际上，Li[24]等人已经将 MinHash 与 GPU 的并行计算能力的组合，在他们的在线学习应用程序中，处理时间至少减少了一个数量级以上。2.6 GPU 结构与线程网络GPU 与 CPU 的不同之处在于：普通 CPU 核心数为 2 或 4 核，而 GPU 的核心数则普遍在 1000 核心以上，所以 GPU 可以其同时运行成千上万的线程，远超一般 CPU，本节介绍了 GPU 结构及 GPU 的线程网络的基本概念。GPU 是通过 PCI-Express（PCIe）总线连接到主机系统的外围设备。该设备包括GPU处理器和板载显存模块。同时 GPU 还包含与图像处理相关的其他部件，因本文算法未涉及到图像处理，故不进行介绍。
【参考文献】：
期刊论文
[1]CUDA-TP:基于GPU的自顶向下完整蛋白质鉴定并行算法[J]. 段琼,田博,陈征,王洁,何增有. 计算机研究与发展. 2018(07)
[2]加强学风建设 ?防治学术腐败[J]. 郭其云,姜建华. 科研管理. 2016(S1)
[3]GPU通用计算及其在计算智能领域的应用[J]. 丁科,谭营. 智能系统学报. 2015(01)
[4]用户搜索意图视角下的Web网页动态泛化研究[J]. 王亚辉. 信息通信. 2014(12)
[5]大数据环境下并行计算模型的研究进展[J]. 潘巍,李战怀. 华东师范大学学报(自然科学版). 2014(05)
[6]云服务平台负载均衡器的网络设计与实践[J]. 夏斌,杜守国. 计算机应用与软件. 2014(08)
[7]运用学术不端文献检测系统检测医学论文存在的问题及对策[J]. 杨晨晨. 编辑学报. 2014(01)
硕士论文
[1]基于大数据平台的用户搜索日志分析和研究[D]. 梁烜彰.华南理工大学 2018
[2]基于聚类的多层关联规则挖掘算法研究与改进[D]. 何晴.上海师范大学 2017
本文编号：3334904
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3334904.html
