论文部分内容阅读
随着GPS技术的快速发展和移动智能设备的日益普及,出现了越来越多的基于地理位置的服务(LBS)。这些服务产生了大量的空间文本数据,既包括空间地理位置,又包括文本描述。这给传统的以文本型数据为主的查询处理技术带来了极大的挑战,主要体现在两个方面:(1)查询效果的好坏通常与底层数据的质量密切相关,针对空间文本数据,如何有效的从多个数据源获取数据并去除其中冗余的部分。(2)在处理各类查询请求时,如何充分的利用空间坐标和文本关键词来优化查询算法,提高搜索性能。本文的主要研究内容及贡献点如下:1.空间文本数据的融合:传统的数据融合算法只针对纯空间数据或者纯文本数据。为了解决这个问题,本文提出一种基于混合前缀签名的融合技术。一方面,针对空间部分,设计最小包围矩形(MBR)前缀剪枝算法,利用空间相似性阈值,为每条数据选取特定的子区域来产生空间签名,由于该区域远远小于原有MBR,因此能够更快速的定位到候选数据;另一方面,设计混合前缀签名算法,通过合并非频繁的关键词来增加索引利用率,并根据关键词的地理分布特点产生不同的空间划分,最后自适应的结合空间和文本前缀来产生混合签名,加强剪枝能力,快速的找到在空间和文本上都非常相似的数据。2.空间文本数据的Top-k检索:传统的Top-k检索算法没有针对文本部分进行优化。为了解决该问题,本文提出一种基于划分的检索算法。它利用TA的思想,增量的找到当前空间相似性最高或文本相似性最高的数据,并动态的合并它们得到候选结果。在建立索引时,按照空间区域和文本相似性区间将数据划分成桶,以桶为整体估计数据的相似性,在每个桶内部搜索Top-k结果并进行合并。通过这种方式,优先定位到相似度高的桶,避免访问大量的无用数据。3.空间文本数据的Top-k近似检索:传统的Top-k近似检索算法不能同时支持“字符级别的容错”和“Top-k”这两种需求。针对该问题,本文设计一种混合型层次索引结构(HLtree)。它能够根据数据分布动态的选择路标,并利用路标来指引数据进行层次划分,保证同一划分内的数据在空间和文本上彼此接近。为了支持多关键词检索,算法增量的找到与每个查询关键词相近的数据,并按照一定策略进行合并。此外,为了避免依次计算数据与路标之间的相似性,算法设计了字符删除策略,利用索引结构来产生数据划分,加速建立索引和查询处理的过程。