大规模字符串近似查询批处理算法研究.pdf

《大规模字符串近似查询批处理算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文大规模字符串近似查询批处理算法研究RESEARCHONBATCHPROCESSINGOFAPPROXIMATESTRINGQUERYONLARGE-SCALESTRINGDATASETS周勇伟哈尔滨工业大学2018年6月国内图书分类号：TP391.1学校代码：10213国际图书分类号：004.93密级：公开工程硕士学位论文大规模字符串近似查询批处理算法研究硕士研究生：周勇伟导师：高宏教授申请学位：工程硕士学科：计算机技术所在单位：计算机科学与技术学院答辩日期：2018年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP391.1U.D.C:004.93Disser

2、tationfortheMasterDegreeinEngineeringRESEARCHONBATCHPROCESSINGOFAPPROXIMATESTRINGQUERYONLARGE-SCALESTRINGDATASETSCandidate：YongweiZhouSupervisor：Prof.HongGaoAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：June,201

3、8Degree-Conferring-Institution：HarbinInstituteofTechnology摘要摘要字符串具有多元化的意义，是计算机领域中重要的研究对象。字符串查询在数据分析、生物序列分析等很多领域有着广泛的应用，然而很多因素导致字符串精确查询面临很大困难甚至不可行。例如由于信息因素、技术因素、流程因素和管理因素等多方面的原因造成数据质量问题，给字符串查询处理带来很多困难，因此需要对字符串进行近似查询。字符串近似查询指的是，在一个字符串数据集中，通过一些字符串相似性函数，寻找与待查询字符串满足相似性条件的字符串集合。近年来，研究人员提出了一些基于q-gram模型和倒排索

4、引的方法来解决字符串近似查询问题。目前字符串近似查询都只针对单个字符串的查询，缺少字符串近似查询批处理方法。批处理可以提高字符串查询效率、提高资源利用效率，因此本文将重点研究字符串近似查询的批处理算法。首先将字符串分割成q-gram集合，为gram建立倒排索引，并在内存中建立Trie树对gram进行管理。采用倒排表组织字符串和gram集合，可以相对减少查询的磁盘随机检索代价，使用Trie树方便了在查询时检索gram对应的倒排表。对于近似查询，本文主要基于过滤-验证框架，通过读取相关倒排表得到候选集合，并利用长度、位置信息增强过滤效果，减少验证代价，最后对候选集合进行验证是否满足相似条件约束。本

5、文建立非对称gram选择代价模型，基于多个查询之间共享部分倒排表的策略，设计了字符串近似查询批处理算法来减少查询代价，并从平均查询时间、平均等待时间、读取倒排表个数等多个维度验证算法的有效性。目前字符串近似查询算法假设候选集合可以完全加载到内存中，没有考虑内存限制的情况。设计内存受限情况下的处理框架有利于在字符串查询任务中减少对内存的消耗，因此本文对内存约束下的字符串近似查询批处理进行了研究。在内存受限情况下，需要对字符串近似查询分批次处理。通过对待查询字符串进行聚类，增加同批次待查询字符串拥有相同gram的概率，进而减少读取倒排表的个数。然后建立字符串查询调度的代价模型，利用动态规划算法进行

6、求解，提出在内存受限情况下的字符串近似查询批处理算法，并保证在查询过程中不会超过内存的约束。最后从平均查询时间等多个性能指标考察了算法的有效性以及内存受限程度等实验参数对性能的影响。关键词：倒排索引；字符串近似查询；批处理；内存受限1IAbstractAbstractStringqueryiswidelyappliedindataanalysis,searchengine,biologicalsequenceanalysisandmanyotherfields.However,exactstringqueryisnotfeasibleinmanysituations.Forinstance,t

7、heproblemsofdataqualitycausedbyinformationfactors,technicalfactors,processfactors,andmanagementfactorshavebroughtmanydifficultiesforstringquery.Therefore,itrequirestoresearchonapproximatestringquery.A