基于位置演进模型的两类时空查询算法

为减少历史时间窗时空查询结果偏差,通过假定移动对象在连续位置更新间做匀速直线运动,获取该对象的近似轨迹函数,基于此函数提出简化的位置演进模型。由该模型求解对象轨迹与查询区域边界相交时间点集;由轨迹函数计算对象与查询中心点间距离函数,求解距离函数间相交时间点集。给出基于简化位置演进模型的时间窗时空范围查询、最近邻查询算法。仿真结果表明,与传统算法相比,所提两类查询算法的结果准确度更高。     

移动对象的连续k最优有序路径查询

针对最优有序路径查询问题,提出了移动对象的连续k最优有序路径查询问题,并针对移动查询对象和静态数据对象的情况,通过引入加权相对距离函数的概念提出了SCkOSR算法和DCkOSR算法.SCkOSR算法利用加权相对距离函数确定数据点与移动查询对象的相对关系.DCkOSR算法进一步通过搜索区域的限制减少了计算加权相对距离函数的点的数量.实验表明,动态局部算法具有相对较好的性能.     

基于BACS算法的数据库查询优化

针对布谷鸟算法局部搜索能力弱、寻优精度低等缺陷,提出一种蝙蝠算法和布谷鸟算法相融合的数据库查询优化算法（BACS）。按照布谷鸟优化算法对鸟巢位置进行更新,利用蝙蝠算法的动态转换策略对鸟巢位置进一步更新,避免算法陷入局部最优;最后将BACS应用于数据库查询优化问题求解,并通过仿真实验对BACS的性能进行测试。实验结果表明,BACS加快了数据库查询优化求解的收敛速度,获得了质量更高的查询优化方案。     

最优有序路径关键词查询

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

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

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

基于空间网络数据库的组最近邻居查询

组最近邻居查询是空间数据库在最近邻居查询上的新问题.目前,对组最近邻居查询的研究局限于欧氏空间,考察的只是对象间的相对位置关系,无法处理现实生活中对象间的连通性问题.鉴于此,本文基于空间网络数据库提出以网络距离为度量标准的组最近邻居查询概念,进而提出作为其算法基础的增量最近邻居查询算法INNN,最后构造出算法NMQM.
实验证明,NMQM是一种有效的组最近邻居查询算法.     

支持多种查询的室内移动对象索引

随着室内定位技术的广泛应用,室内位置服务快速发展.移动对象索引技术作为支撑位置服务的核心技术,大多数都基于室外环境,难以直接应用于室内空间.现有的室内移动对象索引,仅关注对移动对象历史数据的查询,且支持的查询类型单一.为此,提出MQII(multiple queries indoor index)索引结构,对移动对象历史和当前位置信息进行索引,能够同时支持对象位置查询、轨迹查询以及时空范围查询.索引采用对象链表和桶链表结构,实现从对象和时空范围2个方面对移动对象数据的管理;提出针对该索引结构的有效更新、查询算法;实验结果表明,与现有室内移动对象索引相比,索引不仅能够支持历史查询和当前查询,还能够同时高效支持对象位置查询、轨迹查询和范围查询.该方法可应用于办公楼、医院等多种室内空间.     

面向存在不确定对象的组最近邻查询方法

组最近邻查询是空间对象查询领域的一类重要查询,通过该查询可找到距离给定查询点集最近的空间对象.由于图像分辨率或解析度的限制等因素,空间对象的存在不确定性广泛存在于某些涉及图像处理的查询应用中.这些对象位置数据的存在不确定性会对组最近邻查询结果产生影响.本文给出面向存在不确定对象的概率阈值组最近邻查询定义,设计了高效的查询处理机制,通过剪枝优化等手段提高概率阈值组最近邻查询效率,并进一步提出了高效概率阈值组最近邻查询算法.采用多个真实数据集对概率阈值组最近邻算法进行了实验验证,结果表明所提算法具有良好的查询效率.     

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

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

基于禁忌GEP的分布式数据库查询优化算法

为了更好地解决分布式查询优化问题,论文在传统GEP算法的基础上,结合禁忌搜索策略,提出了基于禁忌GEP的分布式数据库查询优化算法（DistributeddatabasequeryoptimizationalgorithmbaseduponTabu-GEP,DDQO-TGEP）。仿真实验表明,随着查询关系个数的增加,DDQO-TGEP算法执行查询时所需要的查询优化时间和最优查询策略生成时间都比传统的GA和GP算法显著下降,其中查询优化时间最大下降约42．16％,最优查询策略生成时间最大下降约36．8％。     

基于轨迹聚类的连续查询隐私保护方法

在LBS连续查询的应用场景下,攻击者易利用查询时间序列、区域位置、移动趋势等背景知识发起有效的攻击,以获取用户的真实位置或轨迹,进而可推断出用户生活习惯等各类隐私信息。针对此,提出了一种基于轨迹聚类的连续查询隐私保护方法。该方法基于邻近用户的信息共享与协作,设计了一种匿名区域构造机制,用户在查询过程中,首先通过被共享缓存获取所需服务结果,如未命中,再向LBS服务器发起查询请求。同时,提出了一种邻近用户位置更新算法,提高用户的协作效率并保证缓存的有效性,对于由命中缓存完成的查询,采用提出的基于密度聚类的兴趣区提取算法,生成高混淆度的假查询扰乱整体查询序列顺序,以此增强轨迹隐私的保护效果。实验结果表明,该方法降低了连续查询中的时间代价,提高了位置混淆程度。     

基于连续查询的用户轨迹k-匿名隐私保护算法

随着移动服务和移动网络的持续发展,基于LBS的连续查询服务被广泛应用。基于单点的K-匿名位置隐私保护算法已经不能满足连续查询下用户位置隐私需求。针对用户轨迹隐私保护提出新的保护方法,该方法采用不可信第三方中心匿名器,用户获取自己的真实位置后首先在客户端进行模糊处理,然后提交给第三方匿名器,第三方匿名器根据用户的隐私需求结合用户某时刻的真实位置信息生成虚假用户,然后根据历史数据生成虚假轨迹。为了进一步提高虚假轨迹与用户真实轨迹的相似性,该算法提出了虚假轨迹生成的两个约束条件：虚假轨迹距用户真实轨迹的距离约束和相似性约束。经大量实验证明,该算法与传统的不同时刻K-匿名算法相比,不仅可以满足连续查询的用户轨迹隐私保护而且可以满足基于快照的LBS用户位置隐私保护。     

Exploiting location information for Web search

Most Web pages contain location information, which are usually neglected by traditional search engines. Queries combining location and textual terms are called as spatial textual Web queries. Based on the fact that traditional search engines pay little attention in the location information in Web pages, in this paper we study a framework to utilize location information for Web search. The proposed framework consists of an offline stage to extract focused locations for crawled Web pages, as well as an online ranking stage to perform location-aware ranking for search results. The focused locations of a Web page refer to the most appropriate locations associated with the Web page. In the offline stage, we extract the focused locations and keywords from Web pages and map each keyword with specific focused locations, which forms a set of <keyword, location> pairs. In the second online query processing stage, we extract keywords from the query, and computer the ranking scores based on location relevance and the location-constrained scores for each querying keyword. The experiments on various real datasets crawled from nj.gov, BBC and New York Time show that the performance of our algorithm on focused location extraction is superior to previous methods and the proposed ranking algorithm has the best performance w.r.t different spatial textual queries.     

分布式查询优化的技术实现

针对分布式查询执行的全局处理策略进行优化的问题,从查询执行的效果出发,提出了一种通过统计的方式,不断从最近的查询执行代价学习纠正最近查询执行的统计代价的方法,为查询的全局处理提供参考,以达到优化执行、提高执行效率和速度的目的。     

基于阈值的快速启动Top-k查询处理算法

Top-k查询是搜索引擎领域广泛应用的技术之一,该算法从海量数据中返回最符合用户需求的前k 个结果,在执行时能避免对大部分无关文档的打分处理。Top-k 查询虽然极大提升了查询性能,但其存在的慢启动问题并未得到有效解决。为此,该文首先提取倒排索引的静态Top-k信息,再动态计算针对具体查询词项的初始阈值,在此基础上,结合MaxScore和WAND算法,提出了快速启动的Top-k查询处理算法。实验结果表明,该方法能够有效解决上述问题,具有良好的性能。     

An efficient method for privacy preserving location queries

Recently, the issue of privacy preserving location queries has attracted much research. However, there are few works focusing on the tradeoff between location privacy preservation and location query information collection. To tackle this kind of tradeoff, we propose the privacy persevering location query (PLQ), an efficient privacy preserving location query processing framework. This framework can enable the location-based query without revealing user location information. The framework can also facilitate location-based service providers to collect some information about the location based query, which is useful in practice. PLQ consists of three key components, namely, the location anonymizer at the client side, the privacy query processor at the server side, and an additional trusted third party connecting the client and server. The location anonymizer blurs the user location into a cloaked area based on a map-hierarchy. The map-hierarchy contains accurate regions that are partitioned according to real landforms. The privacy query processor deals with the requested nearest-neighbor (NN) location based query. A new convex hull of polygon (CHP) algorithm is proposed for nearest-neighbor queries using a polygon cloaked area. The experimental results show that our algorithms can efficiently process location based queries.     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

一种扩充语义的实视图重写查询技术

分组聚集查询已成为数据仓库领域研究的核心问题之一,实视图是提高分组聚集查询性能的有效手段。利用维属性间的层次关系,对一般意义上的实视图重写查询进行了扩展,讨论了单一视图重写查询的限制条件,并给出重写方法,在此基础上,提出了一种利用多个实视图重写查询的优化选择算法,并通过实验表明,该算法进一步提高了分组聚集查询效率。     

基于权重标准化SimRank方法的查询扩展技术研究

查询扩展是信息检索中的一项重要技术。传统的局部分析查询扩展方法利用伪相关文档作为候选词集合,然而部分伪相关文档并不具有很高的相关性。该文利用真实的搜索引擎查询日志,建立了查询点击图,经过多次图结构的转化得到能够反映词之间关联程度的词项关系图,并在图结构的相似度算法SimRank的基础上,提出了一种基于权重标准化的改进SimRank方法,该方法利用词项关系图中词项的全局和间接关系,能够有效挖掘与原始查询相关联的扩展词。同时,为降低SimRank算法的计算复杂度,该文采用了剪枝等策略进行优化,使得计算效率有大幅提高。在TREC标准数据集上的实验表明,该文的方法可以有效地选择相关扩展词。MAP指标较局部分析查询扩展方法提高了1.81%,在P@10和P@20指标评价中效果分别提高了5.44%和3.73%。     

基于多本体的网格数据并行查询

对于综合运输中的铁路、公路、水路和航空运输系统中的异构数据源可以使用网格来实现数据的集成。为了提高网格集成环境中用户查询（涉及多异构数据源）的效率和精确性,提出了基于多本体的并行查询处理方法,给出了全局查询的生成算法和基于查询树的全局查询分解算法。