集合空间关键字内聚组查询方法

给定一个道路网络和社交网络,集合空间关键字查询的目的是找到一组兴趣点,该组兴趣点的文本信息包含所有查询关键字,与查询的位置较近且彼此之间的距离较小。内聚组查询的目的是找到在地理位置和社交关系上紧密联系的一组用户;而集合空间关键字内聚组查询的目的是找到满足查询要求的一对最佳匹配的兴趣点集合和用户集合。针对这一问题,提出一种新的集合空间关键字内聚组查询处理模式。首先通过快速贪心查询过程获得候选兴趣点集合,然后使用core-tree结构存储(k,c)-core核心分解的结果,从而提高内聚组查询效率,并且保证查询结果能够同时满足用户之间的社会关系约束和兴趣点之间的空间位置约束。通过在真实数据集上开展实验,结果表明提出的方法比枚举方法的查询效率快1~2个数量级,并且具有较高查询准确性。

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

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

路网中空间关键字连续范围查询算法研究

空间关键字查询相对传统的位置相关查询而言更能满足实际查询处理的需要。着重探讨路网中结合距离和关键字相似度两个因素的空间关键字查询处理问题,提出解决路网中空间关键字连续范围查询(CRSKQ)的有效方法。提出了一个综合考虑了路网上的道路、对象和路网的连通性的路网模型以支持CRSKQ查询的处理。为了实现连续监控,所提出的算法包括两个阶段,即初始结果获取和查询结果连续监控。初始结果监控阶段,通过路网扩展和关键字匹配寻找满足要求的结果对象;在连续监控阶段,充分利用前面时刻的查询结果来减小连续监控的代价。模拟实验表明,所提出的算法是有效的。

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

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

路网上范围受限的Top-k空间关键字查询

空间关键字查询是现在数据库领域的研究热点,查询时同时考虑对象与查询点的位置相关性和文本相关性.本文提出了路网上范围受限的Top-k空间关键字查询,查询返回在约束范围R内,满足关键字要求,并且距离查询点最近的前k个对象.尽管范围受限的近邻查询在欧式空间已经被研究过,但在路网中并没有关于这方面的研究.基于此,本文提出一种有效的算法.首先,为路网中的顶点建立标签索引,然后,为对象建立网格索引,查询时利用网格索引锁定查找范围,利用标签索引计算查询点与对象间的距离.最后,通过实验验证了该算法的有效性.

传感器网络空间关键字近似Top-k查询算法

提出了一种基于节点剪枝的Top-k査询算法.定义集合支配区域与剪枝规则,根据用户查询位置的变动,按照给定的剪切规则,对传感器网络节点进行剪枝处理,将符合规则的节点预先筛除,运用统计学抽样理论,设计了空间关键字近似Top-k查询算法.在2个真实数据集上进行验证.实验结果表明,该算法能够满足传感器网络环境中用户的需求,并且相比于边界距离增量算法(IBD)与基于改进的MW-Voronoi区域的空间关键字查询算法(MSK-uvr),其网络通信开销较低.

空间关键字查询综述

近年来,带有位置和文本信息的空间-文本数据的规模迅速增长。社交网络中的社交数据和移动互联网中的交易数据等都是空间-文本数据的重要来源,这些数据具有海量、异构、多维等特点。以空间-文本数据为背景的空间关键字查询技术目前得到广泛的研究与应用,给定一个查询位置(用经度和纬度表示)和一组查询关键字,返回距离查询位置最近且与查询关键字相关性较高的空间对象。对空间-文本数据的相关查询技术进行综述,主要包括查询处理模式、索引结构、语义近似查询、基于路网的查询、路线规划查询、基于社交网络查询、基于影响约束下的查询等。

Top-k集合空间关键字近似查询方法

近年来,带有位置和文本信息的空间-文本数据的规模迅速增长,以空间-文本数据为背景的空间关键字查询技术得到广泛的研究与应用。现有大多数空间关键字查询方法通常以单个空间对象作为查询结果的基本单元,最近有少数研究工作提出以一组空间对象作为查询结果的基本单元,这组空间对象联合满足用户的查询需求,但却没有考虑组内空间对象之间的关联关系。针对上述问题,提出一种top-k集合空间关键字近似查询方法。提出一种基于关联规则的空间对象之间的关联访问度评估方法,设计了一种结合距离和组内空间对象关联访问度的评分函数;提出了一种基于VP-Tree的剪枝策略,用于快速搜索空间对象的局部邻域,进而加快查询匹配速度;利用评分函数计算候选空间对象组合的得分,并以此选取top-k组空间对象作为查询结果。实验结果表明,提出的空间对象关联度评估方法具有较高的准确性,提出的剪枝策略具有较高的执行效率,获取的top-k组空间对象具有较高的用户满意度。

无线数据广播环境下的空间关键字查询

在移动计算环境下,无线数据广播是一种可拓展性强、节能、适合用户数量大的信息发布技术.提出了一个在无线数据广播环境下支持空间关键字检索的框架,并提出了一种基于网格索引与倒排表结合的空中索引:IRGI(information retrieval grid index).IRGI的优点是:1)相对文档的大小,索引本身很小,因此可以在一个周期内分布多次索引,以降低访问延迟,增强用户体验效果;2)通过网格索引和倒排表,用户可以剪枝落在区域外的或者不包含感兴趣关键字的文档,从而使用户保持监听状态的时间大大减小,降低能量消耗.最后通过人工生成的数据和真实地图的数据进行了实验模拟,实验结果证明了该方法不但访问延迟低,而且能量消耗小.

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

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

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

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

基于Hadoop的空间关键字索引方法

随着移动互联网的兴起,在移动端产生了海量的数据,这些数据除了含有传统的文本信息外还含有空间位置信息。为了能够高效地处理和利用这些数据,高效的空间关键字索引方法已经成为业界研究的热点。但现有的空间关键字索引方法,在面对海量空间数据时还存在缺乏伸缩性和可扩展性、易产生查询热点等问题。为此,本文提出一种基于Hadoop的空间关键字索引方法,并对索引并行化算法进行优化,与已有的空间关键字索引方法进行对比。实验结果验证了本文提出的空间关键字索引方法的有效性。

路网中空间关键字连续k近邻查询算法研究

研究了路网中空间关键字连续k近邻查询问题(CkSKQ),提出了包含一棵PMR-quad树和三个内存表的数据结构以存储和索引路网结构信息、对象的位置和关键字信息.空间关键字查询综合了查询点和待查询对象间的路网距离和关键字相似程度两个因素,提出了可调节的综合距离值计算公式,以满足各种具体应用对关键字相似度和路网距离不同的侧重程度.为了实现查询的连续处理,通过监控有关候选对象的综合距离值的变化来对查询结果进行修正,以保证查询结果的持续有效性.实验验证表明所提出算法的性能明显优于对照算法.

路网移动对象空间关键字连续Top-k查询

为了克服现有空间关键字查询方法大多只适用于欧氏空间查询处理的局限性,提出了一种渐增监控查询处理方法(CMA),以高效处理路网中移动对象空间关键字连续top-k查询问题(CMkSK).该方法用一棵组合扩展树CEtree来界定查询的监控范围,通过识别、处理监控范围内对查询结果有影响的查询点和移动对象的位置更新对相应的CEtree进行修正,以保证查询结果的持续有效性.所提出的方法考虑了现实生活中对象的可移动性,可以处理查询点和数据对象在路网中自由移动的情形.最后,通过模拟实验证明了所提出算法较参照算法的性能提高约1.1倍.

带关系属性的空间关键词并行查询处理算法

移动互联网、物联网的快速发展产生了大量带关系属性的空间文本对象数据。面向网页文本数据的搜索引擎仅支持文本关键词查询,无法处理包含地理位置信息、文本信息、关系属性的混合数据。现有面向空间关键字的查询处理技术未将关系属性作为过滤条件,且是基于单机实现的,无法满足查询性能的要求。为解决上述问题,提出了一种新颖的将关系属性、空间和关键字3种属性映射成文本数据的Baseline算法(Baseline Algorithm of Distributed Keywords and Location-aware with Relational Attributes Query,BADKLRQ),利用分布式倒排文本索引对转换后的文本数据进行并行索引。针对带关系属性、空间和关键字的查询请求,将查询请求转换成映射空间中的多个文本关键字,对转换后的文本数据进行查询,并提出基于Baseline算法的改进算法MGDKLRQ,以改进空间属性转换成文本关键字的算法。实验结果表明,在索引时间和查询时间上,BADKLRQ算法比现有算法提升了10%~15%,MGDKLRQ算法比现有算法提升了20%~30%。

基于位置-文本关系的空间对象top-k查询与排序方法

针对普通的空间关键字查询通常会导致多查询结果的问题。本文提出了一种基于空间对象位置-文本相关度的top-k查询与排序方法,用于获取与给定空间关键字查询在文本上相关且位置上相近的典型空间对象。该方法分为离线处理和在线查询处理2个阶段。在离线阶段,根据空间对象之间的位置相近性和文本相似性,度量任意一对空间对象之间的位置-文本关系紧密度。在此基础上,提出了基于概率密度的代表性空间对象选取算法,根据空间对象之间的位置-文本关系为每个代表性空间对象构建相应的空间对象序列。在线查询处理阶段,对于一个给定的空间关键字查询,利用Cosine相似度评估方法计算查询条件与代表性空间对象之间的相关度,然后使用阈值算法(threshold algorithm,TA)在预先创建的空间对象序列上快速选出top-k个满足查询需求的典型空间对象。实验结果表明:提出的空间对象top-k查询与排序方法能够有效地满足用户查询需求,并且具有较高的准确性、典型性和执行效率。

面向空间兴趣区域的路线查询

广泛的位置感知应用产生了大量的空间文本数据,其中既包含位置信息,也包含空间文本属性.为了利用这些丰富的信息来描述用户对路线的偏好,提出了面向空间兴趣区域的路线查询(region of interests oriented route query, ROIR).给定空间关键字集合及路线长度约束,ROIR检索满足长度约束和最高收益的由空间兴趣区域组成的路线.与传统的空间关键字路线查询相比,ROIR的对象由空间兴趣点扩展为兴趣区域,增加了用户的选择空间,使得查询结果的适用性更好.针对多种类型的海量空间兴趣点(point of interests, POI)及相关文本信息,设计了2层数据组织模型,模型中集成了POI对象的空间位置、关键字及POI对象间的转移关系.基于2层数据组织模型,提出了综合空间对象位置、转移图以及关键字3类信息的索引结构,同时预计算了关键字的收益统计值,并以签名方式存储在转移结点上.设计了ROIR路线查询精确算法.ROIR是一个NP难问题,为了有效地实现ROIR提出了近似率为1/ε的近似算法.利用真实数据集进行了详细的实验分析,评估了所提出算法的有效性.

已知社交和文本的Top-k位置查询

空间关键字查询处理是数据库领域近年来的研究热点,为进一步提高用户的满意度,将用户的社交信息应用于空间关键字查询中.提出已知社交和文本的Top-k位置查询,给定用户社交关系、位置和多个关键字,为用户返回k个用户可能感兴趣的对象,这k个对象的选择依赖于三个方面:空间邻近、文本相似度和社交相似度.用rank函数作为衡量的标准,返回k个得分最高的对象.在查询算法中,提出了三种裁剪策略,包括距离、文本和社交的裁剪,提高了查询速度,并通过实验验证了本文所提方法的有效性.

基于贪心策略的最近邻Top-k偏好查询方法

传统Top-k空间关键字查询忽略了兴趣对象周围的基础设施属性对于用户偏好的影响,针对该问题,研究了基于影响区域约束关系的Top-k空间关键字偏好查询问题,设计了一种基于贪心策略的最近邻算法GS-NNA(Greedy Strategy based Nearest Neighbor Algorithm)。该算法采用R^*-tree和倒排文件两种索引结构,结合贪心思想和最近邻算法,每次选择分值最高的兴趣对象作为候选结果集,并利用阈值判定条件对R^*-tree进行剪枝。实验结果表明,GS-NNA算法与现有相关算法相比,有效提高了查询效率。