基于空间结构约束的改进迭代最近点影像配准

提出了一种改进的基于空间结构约束的迭代最近点(ICP)影像配准方法.该方法通过结合特征点的空间结构相似性和特征相似性获得特征点的匹配矩阵,其中特征相似性通过特征点的局部特征描述算子进行计算,空间相似性则通过特征点的空间位置进行计算.特征点之间的空间结构相似性不仅包括了对应特征点之间的空间距离,还包含了特征点到邻近特征点的空间距离.在匹配过程中,分别从参考影像和待配准影像的角度出发,实现了匹配的对称性处理.通过对具有不同影像特征的真实遥感影像进行实验,结果表明该算法具有较高的配准精度.     

空间多样化约束下的移动k近邻查询

考虑为移动中的查询对象连续返回k个距离近并且满足空间多样化约束的对象，提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.在此，满足空间多样化约束代表对象之间的相互距离大于距离阈值.为了高效处理SDC-MkNN查询问题，提出了两种基于安全区域技术的算法.算法均通过减少重新计算查询结果的次数来提高查询效率.其中一种为精确算法EA，可连续返回精确的查询结果；另一种为近似算法ρAA，可连续返回具有近似率保障的近似查询结果.采用真实数据集验证了所提出算法的有效性.     

基于MPB-Tree索引的空间数据多关键词模糊查询算法研究

随着具有定位功能的智能设备的大量使用,产生出海量的空间数据,每条数据中包含的信息越来越多,而以往的查询算法多数仅对单个关键词进行查询,已难以满足用户更为个性化的需求.为此,本文提出一种多空间关键词模糊查询算法,在该算法中,将以往的两维空间距离计算转化为莫顿码匹配提升查询效率,且与模糊查询算法融合支持查询的容错.实验结果表明,该算法的效率及准确性较以往查询算法有较大提高.     

约束的移动对象最近邻轨迹查询

提出了一种新的查询概念,即约束的移动对象最近邻轨迹(constrained nearest neighbor search on moving objects trajectories,简称CNNMOT)查询.针对两阶段算法分阶段处理最近邻查询和范围查询的缺陷,对传统空间最近邻算法进行了改进和扩展,使其能够合并到一步完成,并对传统的mindist定义进行了修改.实验结果表明:该改进算法能较好地克服两阶段算法的缺陷,并在数据量较大时仍保持较高的性能.     

基于窗口查询的轮廓查询算法

轮廓查询在涉及多标准决策的空间数据库应用中起着非常重要的作用,轮廓的计算在数据库通信方面受到很大关注,特别是无需访问所有的数据文件就能很快的返回轮廓中的点的算法.本文提出一种基于窗口查询的轮廓查询算法,通过不断变换查询窗口来缩减查询空间,所访问的空间数据点数目大大减少,查询结果有很好的健全性和完整性.     

分布式网络中 CKNN 查询的 BORA 优化汇聚

针对时空数据库中,移动对象轨迹的连续K近邻查询(continuous K nearest neighbor query,CKNN)的查询效率较低的问题,以及在分布式的移动对象数据库(moving objects databases,MOD)环境下,提升对应查询结果的数据汇聚效率问题进行了研究.在CKNN查询中,设计优化了查询海滩线的更新算法,通过在轨迹数据结构中增加更新标志位,减少了轨迹线段参与的判定运算;同时在假设的类网格覆盖的分布式空间环境下,利用基于Bresenham覆盖的路由汇聚(Bresenham-based overlay for routing and aggregation,BORA)方法,进行查询结果的汇聚;并针对不同近邻参数、轨迹数目、移动对象速度、汇聚方式等对查询时间的影响进行了仿真实验;仿真结果表明,不同参数数值的增加延长了处理时间,基于BORA的汇聚方式比一般的汇聚方式节省了更多的处理时间,提高了系统查询及处理的效率.     

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

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

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法, 解决了海量空间数据集下执行Skyline查询效率低的问题. 通过建立R树索引实现空间数据不同粒度的范围剪枝, 有效降低了分布式Skyline查询需扫描的数据规模, 提高了在MapReduce模型下Skyline查询的执行效率. 在不同数据分布下进行对比实验的结果表明, 该方法比已有算法在执行效率上更具优势.     

A graph-based sliding window multi-join over data stream

Join operation is a critical problem when dealing with sliding window over data streams. There have been many optimization strategies for sliding window join in the literature, but a simple heuristic is always used for selecting the join sequence of many sliding windows, which is ineffectively. The graph-based approach is proposed to process the problem. The sliding window join model is introduced primarily. In this model vertex represent join operator and edge indicated the join relationship among sliding windows. Vertex weight and edge weight represent the cost of join and the reciprocity of join operators respectively. Then good query plan with minimal cost can be found in the model. Thus a complete join algorithm combining setting up model, finding optimal query plan and executing query plan is shown. Experiments show that the graph-based approach is feasible and can work better in above environment.     

A graph based sliding window multi join over data stream

Join operation is a critical problem when dealing with sliding window over data streams. There have been many optimization strategies for sliding window join in the literature, but a simple heuristic is always used for selecting the join sequence of many sliding windows, which is ineffectively. The graphbased approach is proposed to process the problem. The sliding window join model is introduced primarily. In this model vertex represent join operator and edge indicated the join relationship among sliding windows. Vertex weight and edge weight represent the cost of join and the reciprocity of join operators respectively. Then good query plan with minimal cost can be found in the model. Thus a complete join algorithm combining setting up model, finding optimal query plan and executing query plan is shown. Experiments show that the graphbased approach is feasible and can work better in above environment     

基于多核环境的并行性双向枚举连接

基于多核处理器, 结合自底向上和自顶向下两种算法, 提出一种图遍历驱动的双向优化算法, 该算法充分利用两种遍历算法的优点, 并发挥多核环境的优势, 实现了最优查询计划的高性能并行构建, 解决了并行双向枚举连接问题. 实验结果表明, 该算法的性能优于已有算法, 可明显提高数据库查询速度.     

KNN查询处理算法性能研究

KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一,它将k个与查询点最接近的对象作为查询结果返回。对于树型多维索引结构,KNN查询处理算法主要有RKV算法和HS算法。本文针对这两种不同处理算法进行了性能研究,通过试验确定了算法的不同适用场景,最后就应用中的KNN查询实现给出了相应的建议。     

基于传输代价最小原则的分布式数据库查询优化

分布式查询算法的核心部分是全局查询优化算法,将查询请求合理地优化分解为子查询任务,并尽量使子查询任务并行执行。分布式查询的优化需要权衡网络流量、响应时间、服务器负载、算法复杂性等多种因素。本着减少节点之间的数据传输量的目的,本文提出一个复杂度和延迟时间之间进行衡量的全局优化算法。本文就连接查询和复合查询进行了详细的分析,最后提出了一种基于半连接的查询优化算法,并分析了该改进算法的优缺点。     

动态环境下的最近邻居查询

介绍了空间数据库中最近邻居查询的基本概念和算法，并详细说明了时间参数查询和基于位置的最近邻居查询，列出了它们的适用范围，同时也指出了这两种最近邻居查询算法对动态环境的不适用性。在此基础上，提出了一个动态环境下的基于位置的最近邻居查询算法。     

基于传输代价最小原则的分布式数据库查询优化

分布式查询算法的核心部分是全局查询优化算法，将查询请求合理地优化分解为子查询任务，并尽量使子查询任务并行执行。分布式查询的优化需要权衡网络流量、响应时间、服务器负载、算法复杂性等多种因素。本着减少节点之间的数据传输量的目的，本文提出一个复杂度和延迟时间之间进行衡量的全局优化算法。本文就连接查询和复合查询进行了详细的分析，最后提出了一种基于半连接的查询优化算法，并分析了该改进算法的优缺点。     

面向组近邻的Top-k空间偏好查询

空间偏好查询是当前空间查询研究中的一类热点问题,而现有的空间偏好查询不能有效支持面向组用户的位置服务应用.为此,提出一类新型空间偏好查询——面向组近邻的Top-k空间偏好查询(Topk spatial preference query for group nearest neighbor).该查询通过查找特征对象的λ子集组近邻最终为用户返回评分值最高的前k个λ子集.为了高效执行这一查询,给出了两种查询算法:TSPQ-G及TSPQ-G*.其中TSPQ-G*在TSPQ-G的基础上,通过空间剪枝及高效的特征对象索引树遍历策略大幅减少I/O代价,进而有效提高了该查询的执行效率.实验采用多个数据集验证了所提算法在不同参数设置下的有效性.     

缓存模式下的轮廓查询优化方法

研究在缓存模式下,利用一组预存储的临时轮廓快照集来高效等价重构用户新提交的轮廓查询Q,并提出一种新颖的缓存模式下轮廓查询处理算法(APSQCM)来完成该任务.APSQCM算法由两阶段组成,第一阶段捕获Q与缓存中临时轮廓快照间的内在关联,进而获取能够用来等价重构Q的所有轮廓基;而在第二阶段中,APSQCM算法使用轮廓基来快速产生Q的正确结果集.实验结果表明,APSQCM算法具有有效性和实用性.     

基于EMD的概率数据top-k相似性连接

选取EMD(earth mover’s distance)作为度量概率数据相似性的标准.EMD具有抗噪性好,对概率分布间的微小偏移不敏感等优良特性,但却具有三次方的复杂度.针对此问题,提出EMD-kJoin算法,在相似性搜索方面,基于线性规划的对偶理论为概率数据构建索引,避免不必要的EMD求精计算;在处理流程方面,以复杂度较低的范围查询为主要操作,并逐步缩小搜索阈值.通过使用真实数据集对EMD-k Join进行测试,证明EMD-k Join极大提高了基于EMD的概率数据top-k相似性连接操作的执行效率.     

Efficient and power-awareness query over sensor networks

Sensor networks consisted of low-cost, low-power, multifunctional miniature sensor devices have played an important role in our daily life. Light and humidity monitoring, seismic and animal activity detection, environment and habitat monitoring are the most common applications. However, due to the limited power supply, ordinary query methods and algorithms can not be applied on sensor networks. Queries over sensor networks should be power-aware to guarantee the maximum power savings. The minimal power consumption by avoiding the expensive communication of the redundant sensor nodes is concentrated on. A lot of work have been done to reduce the participated nodes, but none of them have considered the overlapping minimum bounded rectangle (MBR) of sensors which make them impossible to reach the optimization solution. The proposed OMSI-tree and OMR algorithm can efficiently solve this problem by executing a given query only on the sensors involved. Experiments show that there is an obvious improvement compared with TinyDB and other spatial index, adopting the proposed schema and algorithm.     

Efficient and power-awareness query over sensor networks

Sensor networks consisted of low-cost, low-power, muhifunctional miniature sensor devices have played an important role in our daily life. Light and humidity monitoring, seismic and animal activity detection, environment and habitat monitoring are the most common applications. However, due to the limited power supply, ordinary query methods and algorithms can not be applied on sensor networks. Queries over sensor networks should be power-aware to guarantee the maximum power savings. The minimal power consumption by avoiding the expensive communication of the redundant sensor nodes is concentrated on. A lot of work have been done to reduce the participated nodes, but none of them have considered the overlapping minimum bounded rectangle （MBR） of sensors which make them impossible to reach the optimization solution. The proposed OMSI-tree and OMR algorithm can efficiently solve this problem by executing a given query only on the sensors involved. Experiments show that there is an obvious improvement compared with TinyDB and other spatial index, adopting the proposed schema and algorithm.