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

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

关键词最优路径查询的分段拓展算法

关键词最优路径查询（KOR）查找在满足关键词全覆盖和路径长度约束条件下,时间开销最小的路线常用于旅行规划。现有优化算法虽然采用各种剪枝策略缩小搜索规模,但是本质上是广度优先搜索,在查找长路径时,搜索规模依然过大,执行时间长。针对该问题,提出一种关键词最优路径查询的分段拓展算法（SE-KOR）。SE-KOR算法根据关键词倒排索引表构建关键词顶点路径,将路径划分为多段分别拓展,降低搜索规模,从而缩短执行时间。该算法在路径拓展时给出路径走向,而现有剪枝策略不控制路径拓展方向,因此提出局部代价阈值剪枝,控制路径的走向沿关键词顶点路径拓展,并综合运用近似支配、可行解目标值剪枝和全局优先拓展策略加速拓展。实验结果表明,在不损失精度的情况下,该算法执行时间分别在不同关键词个数、代价阈值与查询图规模下至少缩短8.0%、61.0%和57.7%。     

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

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

一种基于关键词搜索的空间连接查询

许多实际的应用需要同时支持空间连接查询和关键词搜索。在给出基于关键词的空间连接（KSJ）查询定义的基础上,对参与KSJ查询的空间数据集建立MIR2-树索引结构,并结合一些高效的搜索剪枝策略,提出一种基于宽度优先的KSJ查询算法。实验结果表明该算法可有效支持基于关键词的空间连接查询处理。     

大规模路网图下关键词覆盖最优路径查询优化

游客倾向于采用个性化的旅游路线,规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询（KOR）就是用于规划这样的路线的一类查询,其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大,现有算法预处理所需内存开销急剧上升,由于内存不足,导致较大规模的路网不能处理;路径拓展搜索空间快速膨胀,应用场景可扩展性与查询实时性难以保证.针对这些问题,提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图,仅保存子图内路径和子图之间路径的信息,以减小预处理所需内存.在路径拓展阶段,综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化,以高效地搜索近似最优解.采用美国各地区的路网图,在16G内存环境下进行实验,突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明,KORL算法具有良好的可扩展性.     

面向移动对象的高效组最近邻居查询方法

组最近邻居查询是移动对象数据库重要的查询类型之一。本文提出了一种基于网格索引结构的剪枝搜索策略,将空间区域划分为网格,通过对象点的网格单元标识减少组最近邻居查询所需要的节点访问代价。用步长迭代法得到查询对象集的质心,提出了一种移动对象组最近邻居查询MOGNN算法,采用更精确的裁剪搜索空间准则,减少了查询所需要访问的节点数目。实验结果与分析表明,基于网格索引的MOGNN查询算法具有良好的查询性能。     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

一种有效的历史移动对象轨迹的k最近邻居查询算法

近10多年来,研究者们已经在k最近邻居(kNN)查询方面做了很多工作,但是对于移动对象轨迹的kNN查询处理却研究得很少.鉴于此,研究了在存储有历史移动对象轨迹信息的TB树结构上的kNN查询问题,并且提出了一种有效的基于最佳优先搜索范例的kNN(k≥1)查询算法,称为BFPkNN.BFPkNN是一种I/O最佳的算法,即它仅仅访问有可能包含最终结果的结点.同时,为了减少存储空间和CPU代价,又提出了若干有效的剪枝策略.大量的实验证明BFPkNN在效率和可扩展性上均大大胜过其他同类算法.     

一种面向不确定对象的可见k近邻查询算法

真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻(PVkNN)查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.     

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

空间文本数据流上连续k近邻查询(Continuous k-nearest neighbor Queries over Spatial-Textual data streams,CkQST)能在空间文本对象组成的数据流上检索并实时更新k个包含指定关键字的空间邻近对象,是空间文本数据流上连续查询(Continuous Queries over Spatial-Textual data streams,CQST)的一种,以预订(subscribe)的方式广泛应用于广告定位、微博分析、地图导航等领域.求解CkQST采用CQST的求解框架——构建空间文本混合索引组织查询,利用索引的空间过滤和文本过滤能力,为不断到来的对象匹配查询.该框架的求解效率取决于索引的过滤能力,提高索引过滤能力的主要途径是将查询的空间搜索范围映射到索引结构的最小区域,减少需要验证的查询数量.这一途径适用于查询空间搜索范围很少变化的情况.对于CkQST,覆盖k个最邻近对象的空间范围随着符合文本匹配条件的对象的数量的变化而变化,与之对应的索引项需要同步更新,代价高.针对这一问题,本文选择能够高效支持空间范围变化的Quad-tree和关键字查找的倒排索引,构成空间文本混合索引,组织CkQST.在空间过滤方面,提出内存代价模型VUMBCM(Verification and Update of Memory-Based Cost Model),通过平衡索引更新代价和验证代价,优化查询空间搜索范围到Quad-tree节点的映射.在文本过滤方面,采用基于块的有序倒排索引,组织Quad-tree节点内的查询,以快速定位需要验证的查询,避免对倒排列表中大量不可能匹配查询的访问;批量处理包含共同文本项的对象,提高文本验证时的对象吞吐量.由此构建的混合索引,称为OIQ-tree.实验表明,OIQ-tree中的代价模型及基于块的有序倒排索引能够支持CkQST的高效求解.与目前先进的索引技术相比,当查询规模达到2000万时,因数据流中对象的变化导致的索引平均更新时间降低了 46％,数据流中对象的平均处理时间降低了 22％.     

Density-based spatial keyword querying

With the rocket development of the Internet, WWW(World Wide Web), mobile computing and GPS (Global Positioning System) services, location-based services like Web GIS (Geographical Information System) portals are becoming more and more popular. Spatial keyword queries over GIS spatial data receive much more attention from both academic and industry communities than ever before. In general, a spatial keyword query containing spatial location information and keywords is to locate a set of spatial objects that satisfy the location condition and keyword query semantics. Researchers have proposed many solutions to various spatial keyword queries such as top-K keyword query, reversed kNN keyword query, moving object keyword query, collective keyword query, etc. In this paper, we propose a density-based spatial keyword query which is to locate a set of spatial objects that not only satisfies the query’s textual and distance condition, but also has a high density in their area. We use the collective keyword query semantics to find in a dense area, a group of spatial objects whose keywords collectively match the query keywords. To efficiently process the density based spatial keyword query, we use an IR-tree index as the base data structure to index spatial objects and their text contents and define a cost function over the IR-tree indexing nodes to approximately compute the density information of areas. We design a heuristic algorithm that can efficiently prune the region according to both the distance and region density in processing a query over the IR-tree index. Experimental results on datasets show that our method achieves desired results with high performance.     

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

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

移动空间安全区域关键字查询算法

随着时代的飞速发展,人们对智能生活的追求不断提高,空间查询也被人们愈来愈重视。移动空间关键字查询,作为一种主要的连续空间查询类型,受到了广泛的研究。在最新的顶尖会议文刊中,提出了一种新的查询类型,称为移动集合空间关键字查询(MCSKQ)。这种类型的查询不断报告一组对象,这些对象在查询移动时共同覆盖查询关键字。同时,返回的对象也必须靠近查询对象并且彼此靠近。计算精确的结果集是一个NP-hard的问题。为了降低查询处理的成本,本文提出了基于安全区域技术的算法,在查询对象移动时,保持精确的结果集。在其基础上,本文基于MCKSQ的思想提出新的优化策略,以降低查询处理成本的方法。     

Approximate range query processing in spatial network databases

Spatial range query is one of the most common queries in spatial databases, where a user invokes a query to find all the surrounding interest objects. Most studies in range search consider Euclidean distances to retrieve the result in low cost, but with poor accuracy (i.e., Euclidean distance less than or equal network distance). Thus, researchers show that range search in network distance retrieves the results with high accuracy but with a vast amount of network distance computations. However, both of these techniques retrieve all objects in a given radius with a high number of false hits. Yet, in many situations, retrieving all objects is not necessary, especially when there are already enough objects closer to the query point. Also, when the radius of the search increases, a demotion in the performance will occur. Hence, approximate results are valuable just as the exact result, and approximate results can be obtained much faster than the exact result and are less costly. In this paper, we propose two approximate range search methods in spatial road network, namely approximate range Euclidean restriction and approximate range network expansion, to reduce the number of false hits and the number of network distance computations in a considerable manner. After the verification, these two methods are shown to be robust and accurate.     

三维GIS空间对象层次细节比例变换综合算法

提出了一种基于改进的Reactive-Tree数据结构的空间地理信息数据组织策略Improved Reactive-Tree（简称IR-Tree）及其相关算法,该算法在预处理中建立基于三维空间对象静态质量的IR-Tree;然后在具体的三维GIS场景绘制过程中,根据不同的视点和视角计算考虑当前视距的空间对象动态质量,从而调整空间对象的优先级顺序;再通过文中算法2和算法3动态地计算和输出当前比例和视点下的空间形体,实验结果表明：考虑视点因素的层次细节比例变换算法能取得更好的显示效果,从而满足当前三维GID应用的需求．     

最优有序路径关键词查询

为了实现最优有序路径关键词查询,提出了基于动态阈值的OSRK迭代算法,通过不断缩小阈值来过滤不可能出现在最优有序路径中的空间对象,同时在迭代添加路径时,删除不包含给定关键词的空间对象,能够有效地减少候选空间数据集的大小,提高查询响应性能。通过实验验证了算法的有效性。     

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.     

Approximate algorithms for static and continuous range queries in mobile navigation

For many years, spatial range search has been applied to computational geometry and multimedia problems to find interest objects within a given radius. Range search query has traditionally been used to return all objects within a given radius. However, having all objects is not necessary, especially when there are already enough objects closer to the query point. Furthermore, expanding the radius may give users better results, especially when there are a lot of objects just outside the search boundary. Therefore, in this paper, we focus on approximate range search, where the query results are approximate, rather than exact. We propose approximate static range search (ARS) which combines two approaches, namely (i) lowerbound approximate range search, and (ii) upperbound approximate range search. Using ARS, we are able to deliver a better performance, together with low false hit and reasonable false miss. We also extend ARS in the context of a continuous query setting, in which the query moves. This is particularly important in spatial databases as a mobile user who invokes the query is moving. In terms of continuous range search, the intention is to find split points—the locations where the query results will be updated. Accordingly, we propose two methods for approximate continuous range search, namely (i) range search minimization, and (ii) split points minimization. Our performance evaluation which compares our methods with the traditional continuous range search shows that our methods considerably reduce the number of split points, thereby improving overall performance.     

基于耦合相关度的空间数据查询结果自动分类方法

由于空间数据库通常蕴含海量数据,因此一个普通的空间查询很可能会导致多查询结果问题。为了解决上述问题,提出了一种空间查询结果自动分类方法。在离线阶段,根据空间对象之间的位置相近度和语义相关度来评估空间对象之间的耦合关系,在此基础上利用概率密度评估方法对空间对象进行聚类,每个聚类代表一种类型的用户需求;在在线查询处理阶段,对于一个给定的空间查询,在查询结果集上利用改进的C4.5决策树算法动态生成一棵查询结果分类树,用户可通过检查分类树分支的标签来逐步定位到其感兴趣的空间对象。实验结果表明,提出的空间对象聚类方法能够有效地体现空间对象在语义和位置上的相近性,查询结果分类方法具有较好的分类效果和较低的搜索代价。     

Semantic-aware top-k spatial keyword queries

The fast development of GPS equipped devices has aroused widespread use of spatial keyword querying in location based services nowadays. Existing spatial keyword query methodologies mainly focus on the spatial and textual similarities, while leaving the semantic understanding of keywords in spatial Web objects and queries to be ignored. To address this issue, this paper studies the problem of semantic based spatial keyword querying. It seeks to return the k objects most similar to the query, subject to not only their spatial and textual properties, but also the coherence of their semantic meanings. To achieve that, we propose novel indexing structures, which integrate spatial, textual and semantic information in a hierarchical manner, so as to prune the search space effectively in query processing. Extensive experiments are carried out to evaluate and compare them with other baseline algorithms.