一种基于HBase的空间关键字查询算法

针对传统关系数据库处理海量空间文本数据的不足,基于HBase数据库提出了一种结合Geohash编码与分词技术的空间文本索引方案,并基于该空间文本索引提出了一种多边形区域内的空间关键字查询算法。通过与传统经纬度索引方案的实验比较,验证了算法的高效性和可扩展性。     

空间关键字个性化语义近似查询方法

现有的空间关键字查询处理模式大都仅支持位置相近和文本相似匹配,但不能将语义相近但形式上不匹配的对象提供给用户;并且,当前的空间-文本索引结构也不能对空间对象中的数值属性进行处理。针对上述问题,本文提出了一种支持语义近似查询的空间关键字查询方法。首先,利用词嵌入技术对用户原始查询进行扩展,生成一系列与原始查询关键字语义相关的查询关键字;然后,提出了一种能够同时支持文本和语义匹配,并利用Skyline方法对数值属性进行处理的混合索引结构AIR-Tree;最后,利用AIR-Tree进行查询匹配,返回top-k个与查询条件最为相关的有序空间对象。实验分析和结果表明,与现有同类方法相比,本文方法具有较高的执行效率和较好的用户满意度;基于AIR-Tree索引的查询效率较IRS-Tree索引提高了3.6%,在查询结果准确率上较IR-Tree和IRS-Tree索引分别提高了10.14%和16.15%。     

一种支持动态XML文档上关键字查询的索引结构

在关键字查询领域,目前提出的大多数索引结构主要考虑的是静态的XML文档.当XML文档出现频繁更新时,这些索引结构可能面临着大范围的重新编码,从而增加了数据库索引维护的代价.为了能在XML文档动态更新的环境下保持其索引结构的稳定,提出了一种支持动态XML文档上关键字查询的索引结构DLSS( DDE Level Structure Summary).该索引结构采用了一种针对动态更新改进的Dewey编码,该编码只需在文档更新时对新的节点赋予相应的编码,而不需要调整原有的编码结构.实验证明,DLSS索引结构可以在XML文档频繁更新或者较少更新时都能保持索引结构的相对稳定,并能在其上实现较高的关键字查询效率.     

一种新的面向集合的空间关键字查询方法

面向集合的空间关键字查询处理是数据库领域近年来的热点研究课题.针对已有查询的不足,定义一种新的描述集合质量的Cost函数,提出一种新的面向集合的空间关键字查询方法,并证明基于该Cost函数的查询问题是NP完全问题.对于给定的对象数据集D={o1,o2,…,on},q为包含位置信息和关键字集合的查询点,查询返回的是在对象数据集D中,既满足查询点q的全部关键字,又能成为q的近邻且较紧凑的对象集合.为处理该查询,利用最小圆覆盖包含全部关键字的对象集合,并采用有效的裁剪策略分别实现了该查询的近似查询算法和精确查询算法.最后通过实验验证了所提算法的有效性.     

带排斥关键字的空间关键字查询

定义了一种新的空间关键字查询模式,即带排斥关键字的空间关键字查询,它在普通空间关键字查询基础上添加了排斥关键字(即不需要的关键字),提高的查询的灵活性并使得查询场景更贴近真实情形。为这种新的关键字查询模式设计了混合空间索引以加速查询处理。混合空间索引由二叉树和R-树组成(文中称之为BIR树),并设计了相应的查询剪枝算法以加速查询。实验证明在这种空间关键字查询模式下,BIR树有着相当高的查询效率。     

一种基于HBase的高效空间关键字查询策略

随着移动定位技术的发展以及智能手机的普及,互联网中空间文本对象的数量正在急速增长,如何在规模庞大且动态增长的空间文本对象中进行高效的空间关键字查询成为了许多空间关键字查询应用所关心的问题.现有的方法通常利用基于R树和倒排索引的混合索引结构来处理空间关键字查询,然而,面对数量巨大而且不断增长的空间文本对象,这些方法往往难以为空间关键字查询的高效性和扩展性提供支持.对此,提出一种基于HBase的空间文本数据索引结构SK-HBase.SK-HBase以HBase作为数据存储,通过有效的数据分配策略对空间文本对象的空间信息和文本信息同时进行索引.在SK-HBase的基础上,本文提出了两种空间关键字查询算法,以保证不同空间范围下的空间关键字查询的高效性和可扩展性.实验证明,我们的方法能够在海量数据下进行高效的空间关键字查询并具有良好的可扩展性.     

RM树:一种支持字符串相似性操作的索引

字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点:内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符串聚类,在查询处理过程中导致了较大的I/O代价.该文设计了支持多种字符串相似性操作的RM树...     

OIQ-tree:一种支持大规模空间文本数据流上连续k近邻查询的索引

空间文本数据流上连续k近邻查询(Continuous k-nearest neighbor Queries over Spatial-Textual data streams,CkQST)能在空间文本对象组成的数据流上检索并实时更新k个包含指定关键字的空间邻近对象,是空间文本数据流上连续查询(Continuous Qu...     

一种支持高效XML 路径查询的自适应结构索引

提出了一种新的自适应结构索引:AS-Index(adaptive structural index),能够克服现有静态索引和自适应索引的缺陷,具备高效的查询和调整性能.AS-Index 建立在F&B-Index 的基础之上,其索引结构包括F&B-Index,Query-Table 和Part-Table.Query-Table 能够记录频繁查询,避免了查询过程中的冗余操作.并且,在Query-Table 的基础上提出了自底向上的查询处理过程,能够充分利用现有的频繁查询高效地回答非频繁查询.Part-Table 用于优化包含祖先后裔边的查询,进一步提高了查询性能.现有的自适应结构索引的调整粒度是XML 元素节点,调整过程往往需要遍历整个文档.而AS-Index 是基于F&B-Index 节点的增量调整,其过程是局部的,高效的,并且能够支持复杂分支查询的调整.实验结果表明,AS-Index 在查询和调整性能上优于现有的XML 结构索引.同时,相比于现有的自适应结构索引,AS-Index 针对大规模文档具有更加优良的可扩展性.     

空间关键词搜索研究综述

由于越来越多的数据具有位置和文本双重属性,空间关键词查询(spatial keyword query,简称SKQ)应运而生.一个SKQ以一个地理位置和若干关键词作为参数,返回满足空间与文本约束的结果,这些结果往往根据指定公式排列.对现有的空间关键词搜索技术进行了梳理,首先对问题进行了描述,对挑战进行了分析;然后分析了基本空间关键词搜索技术.将文献中提出的各种空间关键词查询进行了划分,对现有的查询处理技术进行分类,对每种类型的技术,从索引技术和查询算法两个方面进行了总结,并从多个角度对它们进行了比较.其后介绍了扩展空间关键词搜索技术,还介绍了与该问题相关的其他研究工作.最后指出了研究中存在的不足以及以后的研究方向.     

一种语义增强的空间关键词搜索方法

空间关键词搜索立足于查找满足用户查询意图且空间距离相近的兴趣点(point of interest, POI),在地图搜索等领域有着广泛的应用.传统的空间关键词搜索方法仅考虑关键词与POI点在文本上的匹配程度,忽略了查询的语义信息,因而会导致相关结果丢失以及无关结果引入等问题.针对传统方法的局限,提出了语义增强的空间关键词搜索方法S3(semantic-enhanced spatial keyword search).该方法对查询关键词中包含的语义信息进行分析,并结合语义相关性和空间距离对POI点进行有效的排序.S3方法主要有以下2个技术挑战：1)如何对语义信息进行分析.为此,S3引入了知识库对POI数据进行语义扩充,并提出了一种基于图的语义距离度量方式.结合语义距离和空间距离,S3给出POI点的综合排序方案.2)如何在大规模数据上即时地返回top-k搜索结果.针对这一挑战,提出了一种新型的语义-空间混合索引结构GRTree(graph rectangle tree),并研究了有效的剪枝策略.在大规模真实数据集上的实验表明,S3不仅能够返回更为相关的结果,而且有着很好的效率和可扩展性.     

空间数据上Top-k关键词模糊查询算法

基于位置的服务(LBS)变得日益普及,越来越多的研究开始关注如何对空间中的兴趣点(POI)做有效的检索.现有的方法提出了空间数据上的关键词检索,研究如何根据查询的位置和关键词找到相关的POI点.然而,现有方法主要对查询关键词进行精确匹配,不能支持模糊查询:当查询关键词与底层数据存在微小差异的时候,LBS系统不能返回相关的结果.为了满足移动用户的模糊查询需求,文中对空间数据上的Top-k关键词模糊查询问题进行研究:给定一组POI点,检索与查询关键词近似匹配且空间上距离相近的Top-k个结果.为了提供高效的模糊查询,文中首先定义了一种新型的相关性函数,综合考虑了文本相似性和空间距离,进而提出了一种有效的索引结构RegionTrie,并基于RegionTrie设计了高效的Top-k算法.真实数据集上的实验结果表明,文中提出的Top-k算法十分高效,性能远好于对比方法.     

支持关键词搜索的空间连接查询研究

近年来,许多实际应用不仅需要支持空间连接查询而且需要具备关键词搜索功能,以帮助用户查找那些既满足空间连接条件又包含指定关键词的空间对象组合.正是在这种需求的驱动之下,定义了一种具备关键词搜索功能的空间连接查询(Spatial Join with Keyword Search,缩写SJKS),并提出了一种基于IR2-Tree的SJKS查询处理算法(IR2-TreeSJKS算法),旨在实现关键词搜索与空间连接查询的高效结合.实验表明,本算法可有效支持具有关键词搜索功能的空间连接查询处理.     

一种基于预先索引的关系数据库关键词搜索方法

关系数据库的关键词搜索面临的最大挑战在于满足需求的答案可能来自多个关系的元组的组合。现有主流方法通过定位每个关键词对应的元组并动态发现元组之间的关联来得到搜索结果。然而当数据库规模较大或模式复杂时,这些方法存在搜索效率低的问题;此外,这些方法因只能支持简单的关键词查询而实用性受到限制。为此,提出对元组的组合进行预先索引从而加快搜索,此外还对其索引效率及查询能力进行改进以提高系统的可用性。首先,为了提高搜索和索引效率,提出基于模式图的元组连接枚举技术,该技术利用无环模式图枚举合适的关系连接,将其转换为SQL语句在数据库中执行以得到可能的元组连接;其次,为了保证结果的紧致性,提出了1到m元组连接的预先索引与顺序搜索机制,该机制对元组连接进行由小到大的搜索,并限制所有包含已有结果的元组连接都不再参与搜索;最后,为了支持复杂查询,提出基于域的索引结构,为每个元组连接建立面向不同查询类型的域,通过查找多个域并对结果进行逻辑组合得到最终结果。实验表明,相比于已有技术,本技术具有较快的索引速度与较高的查询效率,并能提供如布尔查询、属性查询等的复杂查询能力。     

关系数据库中支持语义的Top-K关键字搜索

为了增强关系数据库中的关键字搜索查询结果,考虑了多表之间以及元组之间的语义关系,提出了一种语义评分函数.该语义评分函数不仅涵盖了当前的评分思想,并且加入新指标来衡量查询结果与查询关键字之间的相关性.基于该评分函数,提出两种以数据块为处理单位的Top-K搜索算法,分别为BA(blocking algorithm)算法和EBA(early-stopping blocking algorithm)算法.EBA在BA基础上引入了过滤域值,以便尽早终止算法的迭代次数.最后实验结果显示语义评分函数保证了搜索结果的高查准率和查全率,所提出的BA算法和EBA算法改善了现有方法的查询性能.     

一种基于XLCA的XML关键字搜索方法

关键字搜索是大多数普通用户搜索信息的有效手段,因为他们不需要学习复杂的查询语言,也不需要了解底层数据的结构.本文研究了针对XML文档的关键字搜索问题,首先指出前人基于SLCA的结果集定义的不完备性,进而提出基于XLCA的结果集定义,使得其能够包含所有可能的结果.基于这样的结果集定义,给出了一种精简的索引结构以及相应的搜索算法,并实现了这两种不同的方法,实验证明本文提出的方法在性能以及可扩展性方面均有较大的提高.     

支持OR语义的高效受限Top-k空间关键字查询技术

近些年,随着定位系统和移动设备的普及,空间文本对象的数量日益庞大,基于位置的地理信息服务在人们的生活中发挥着越来越重要的作用.对于空间关键字查询搜索的研究亦如火如荼.然而,现有许多研究工作只适用于AND语义,支持OR语义的搜索研究相对较少.当用户放松对关键字匹配的要求时,支持OR语义的搜索技术显得尤为重要.针对这一问题,在聚集线性四分树的基础上,利用线性四分树上物理存储的Morton码与逻辑空间位置的对应性,提出了基于虚拟网格的VGrid算法.该算法可同时支持OR语义和AND语义.最后,通过在真实数据集上进行大量实验,验证了所提算法的有效性和高效性.