关键词：
数据处理
数据检索
时空数据
字符串相似度搜索
活动轨迹搜索
集合相似度
编辑距离
摘要：
字符串相似度搜索(String Similarity Search)是数据库系统中最基础功能之一,主要用于数据清理、数据集成等一系列操作。给定一组数据对象、一个相似度函数和一个查询标准,字符串相似度搜索旨在找到在相似度函数下符合查询标准的所有数据对象。由于字符串相似度搜索问题的基础性和重要性,在过去几十年里,该问题得到了深入的研究。但是,随着互联网和信息技术的快速发展,现实世界产生的数据量急剧增长,字符串相似度搜索迎来了新的挑战和机遇。在大规模数据集上,传统字符串相似度搜索技术通常面临时间复杂度高、空间消耗大等问题。同时新技术的涌现,例如机器学习技术、时空数据系统等,也给字符串相似度搜索技术的发展带来了新的前景。因此,如何设计新算法使得字符串相似度搜索更高效,如何利用新技术如机器学习技术来提升字符串相似度搜索性能,如何在新领域如时空数据系统应用字符串技术,都是需要研究的重要问题。基于这三个层次探索字符串相似度搜索技术,研究了不同相似度函数下的查询和连接相关算法,研究了学习索引技术在字符串相似度搜索中的应用,研究了基于字符串技术的活动轨迹查询方法。具体而言:首先,研究了重叠相似度(Overlap Similarity)下字符串相似度top-k连接问题,提出了基于步长(即算法每次迭代访问元素的个数)的算法,在传统算法基础上优化和提升算法查询效率。此研究先分析了步长对算法的影响,表明了大步长的好处,得到存在最优固定步长的结论,并基于此结论提出了固定步长算法。然后,为了使得算法更具可行性,提出了一种自适应步长算法,在算法过程中自动调整步长大小,避免人工设置步长的同时,充分利用了大步长带来的优势。接着,将算法推广到杰卡德相似度、余弦相似度等其他相似度函数。大量实验评估表明提出的算法性能在大规模真实数据集上优于目前最优算法,在不同数据集上查询时间加快了4-14倍。其次,研究了编辑距离下字符串相似度阈值搜索问题,提出了一种基于草图表示法的索引算法,并在索引结构中引入了基于机器学习思想的学习索引技术。其中,草图表示方法用来捕获字符串中主元字符以构建较短的字符串草图表示,该方法能够保证通过草图找到的候选数据具有较高准确度。基于草图表示,设计了精简的索引结构来搜索草图,大大减少算法的空间消耗,并使用学习索引替代索引中的长度过滤结构,加快在索引上的搜索。在真实数据集上大量实验评估表明该方法性能优越,相比于目前最优算法,其空间消耗最高减少了近75%,查询时间最快加快了近60倍。最后,研究了基于字符串技术的活动轨迹搜索问题,提出了一种新的距离定义以及基于字符串编码的网格树阈值算法。首先,结合时间、空间和关键词三个维度提出了一种适用于活动轨迹的距离度量方法,并提出了基于倒排索引的阈值算法作为基线算法。然后,结合字符串编码技术设计了活动网格树索引结构来存储轨迹点,基于活动网格树提出了网格树阈值方法快速过滤空间距离较远、关键词不匹配的候选轨迹。此外,对该方法进行扩展以支持并行计算。最后,大量实验验证了所提出算法的高效性,网格树阈值算法相比于基线算法在不同数据集上查询效率提升了3-10倍。
欢迎来到三峡大学图书馆！
