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

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

利用覆盖区域设计与实现移动对象索引

对移动对象索引频繁更新问题进行了研究,提出了一种基于区域覆盖的空间索引结构虚拟网格四分树(virtual grid quadtree,VGQ);通过索引移动对象所在的区域而非移动对象本身来减少由于移动对象位置的改变而引起的索引结构的改变,并给出了近似连续范围查询算法及增量和自底向上优化策略。实验结果表明,VGQ在查询效率和空间使用上是一种有效的索引方法。     

网络受限移动对象不确定性轨迹的索引

近年来,人们对于如何表示和处理移动对象的不确定性进行了研究,提出了一些较为有效的模型和算法.但是,在如何索引移动对象的不确定时空轨迹方面,相关的研究工作十分有限.为了解决上述问题,本文提出了一种网络受限移动对象不确定轨迹的索引结构(UTR-Tree),并给出了相关的索引更新及查询算法.在该索引结构的支持下,移动对象数据库不仅可以快速地处理对移动对象过去可能位置的查询,而且能够对其现在及将来的可能位置进行高效的查询处理.     

一种混合的时空数据库索引机制

近年来,时空数据库的应用得到迅速发展,在动态时空环境里,维持持续移动对象的位置信息是一个挑战。本文提出了一种新的索引机制,采用两种不同类型的索引结构,一种索引移动对象历史轨迹,一种能够有效地索引移动对象现在、最近、将来的位置信息,而且随着时间的推移,能够将两种索引结构内容快速过渡。在实现移动对象历史轨迹的完整或局部的有效查询的同时,又保证了移动轨迹的空间紧密性。     

移动对象数据库的索引和查询

该文首先概述了移动对象数据库(Moving Objects Database,MOD)的特点;接着,针对移动对象数据库的索引方法展开,根据移动对象索引空间的不同,将移动对象索引分为无限制空间移动对象索引和网络空间移动对象索引,阐述了几种主要的移动对象索引技术的发展情况;然后,分析了一下移动对象数据库中的查询技术,指出对查询策略的评价应多方面,多角度考虑;最后简述了移动对象索引和查询的发展方向。     

一种基于受限网络的移动对象索引结构

为了提高受限网络中移动对象索引效率和满足近邻查询需求,基于FNR-Tree索引结构和Geohash编码算法,提出一种能够满足近邻查询的移动对象索引结构RNR(restricted network R-Tree).通过添加哈希表、链表等辅助索引结构来提升索引结构操作效率,融合Geohash编码和相关算法来使得索引结构能高效满足近邻查询的需求.通过将指定区域按一定规则划分,可使得索引结构具备在不规则范围查询的能力.使用旧金山市地理数据和移动对象数据对索引结构性能进行了测试,结果表明RNR具有较高索引结构操作效率,并且能够高效地提供窗口查询和近邻查询的功能.     

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

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

一种基于城市交通网络的移动对象全时态索引

高效地管理移动对象以支持查询是一个重要课题.为了支持在城市交通网络上的移动对象过去、现在和将来位置查询,提出了一种新的索引技术.首先提出基于模拟预测的位置表示模型来改进对移动对象将来运动轨迹的预测精度;其次根据城市交通网的特征,设计了一种全新的动态结构自适应单元(AU),将其开发为一个基于R树的索引结构(current-Au);最后在AU的基础上进行扩展(past-AU)使其支持移动对象历史轨迹查询并且避免了大量的死空间.实验证明,AU索引优于传统的TPR树和TB树索引.     

路网环境下的移动对象查询技术研究综述

随着基于定位服务（Loaction-Based Service,简称LBS）在移动设备上的广泛应用,移动对象在路网中的查询成为时空数据检索领域的一个研究热点.本文从索引结构、查询方法和隐私保护三层面对基于路网的移动对象查询技术进行了分类讨论.索引结构分为分层索引、分布式索引和广播索引并对三种索引进行对比和分析;查询方法分为单对象连续查询、多对象并行查询、最短路径查询和路网关键字查询并归纳了每种查询的解决策略;此外,阐述了路网移动对象查询中采用的隐私安全保护措施.最后,分析了未来路网移动对象查询研究所面临的挑战.     

基于受限移动对象当前及将来时刻检索的时空索引结构研究

在给定的空间及时间范围内,如何构建高效的时空索引结构,以实现对移动对象快速有效的检索,是实现定位服务、智能交通、数字化战争等诸多应用中所迫切需要解决的问题.本文依据移动对象的运动特点,提出了一种面向当前及将来时刻快速更新及有效检索的索引结构—PQR树.PQR树是综合PMRQuad树和R*树的结构,首先依据道路分布用PMRQuad树将移动对象的索引空间实行粗略的层分割,将所有快速移动对象与道路相关联.然后用R*树索引分布在各个子空间块内的类静止对象.实验结果表明PQR树具有良好的更新和查询性能.     

A taxonomy for moving object queries in spatial databases

In the past decade, many works have focused on the development of moving object database indexing and querying. Most of those works have concentrated on the common spatial queries which are used with static objects as well. However, moving objects have different features from static objects which may lead to a variety of queries. Therefore, it is important to understand the full spectrum of moving object queries, even before starting to build an index structure for such objects. The aim of this paper is to provide a complete picture of the capabilities of moving object queries. Thus motivated, in this paper we propose a taxonomy of moving object queries, comprising five perspectives: (i) Location perspective, (ii) Motion perspective, (iii) Object perspective, (vi) Temporal perspective and (v) Patterns perspective. These give an overall view of what moving object queries are about. In this work, each perspective is described and examples are given.     

Indexing moving objects for directions and velocities queries

Moving object databases are required to support different types of queries with a large number of moving objects. New types of queries namely directions and velocity queries (DV queries), are to be supported and covered. The TPR-tree and its successors are efficient indexes that support spatio-temporal queries for moving objects. However, neither of them support the new DV queries. In this paper, we propose a new index for moving objects based on the TPR*-tree, named Direction and Velocity of TPR*-tree or DV-TPR*-tree, in order to build data a structure based on the spatial, direction and velocity domains. DV-TPR*-tree obtains an ideal distribution that supports and fulfils the new query types (DV queries). Extensive performance studies show that the query performance of DV-TPR*-tree outperforms the TPR-tree and its successors.     

Processing moving queries over moving objects using motion-adaptive indexes

This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore, we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme to evaluating moving continual k-nearest neighbor (kNN) queries. Our experiments show that the proposed motion-adaptive indexing scheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries.     

一种新的道路网络连续查询处理方法

基于道路网络的连续k近邻查询是移动对象数据库领域的研究重点和热点.提出了一种新的道路网络有向图模型,通过引入有向网络空间度量,利用基于内存的格网索引和线性链表结构来对移动对象当前位置和道路网络有向图模型进行存储和管理;基于有向距离度量提出了单向网络扩展(DNE)算法,以减少连续k近邻查询的网络扩展搜索代价.实验结果表明,DNE算法性能优于现有的连续k近邻查询处理算法.     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

Fast Nearest-Neighbor Query Processing in Moving-Object Databases

A desirable feature in spatio-temporal databases is the ability to answer future queries, based on the current data characteristics (reference position and velocity vector). Given a moving query and a set of moving objects, a future query asks for the set of objects that satisfy the query in a given time interval. The difficulty in such a case is that both the query and the data objects change positions continuously, and therefore we can not rely on a given fixed reference position to determine the answer. Existing techniques are either based on sampling, or on repetitive application of time-parameterized queries in order to provide the answer. In this paper we develop an efficient method in order to process nearest-neighbor queries in moving-object databases. The basic advantage of the proposed approach is that only one query is issued per time interval. The time-parameterized R-tree structure is used to index the moving objects. An extensive performance evaluation, based on CPU and I/O time, shows that significant improvements are achieved compared to existing techniques.     

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.

     

Main Memory Evaluation of Monitoring Queries Over Moving Objects

In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit-rate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*-trees.     

路网数据流的预测聚集查询新方法研究

时空数据流的聚集查询技术已经成为数据库领域的研究热点。到目前为止,还没有一种有效的全时态聚集索引适用于非欧氏空间的路网数据流聚集查询。实现路网数据流的全时态聚集查询,必须解决:(1)路网的非欧氏空间特性问题;(2)路网上移动对象的重复计数、非均匀分布以及预测聚集问题。Sketch RR-tree解决了非欧氏空间特性和重复计数问题;为解决非均匀分布问题,借鉴草图划分思想,提出动态草图索引结构DynSketch:采用AMH智能划分Sketch RR-tree,使每个划分区域内车辆均匀分布,以提高聚集查询质量;同时,基于DynSketch,结合ES预测模型,提出了路网数据流的预测聚集查询算法。     

Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks

Recent research has focused on Continuous K Nearest Neighbor (CKNN) queries in road networks, where the queries and the data objects are moving. Most existing approaches assume the fixed velocity of moving objects. The release of fixed moving velocity makes the query process slowly due to the significant repetitive query cost. In this paper, we study CKNN queries over moving objects with uncertain velocity in road networks. A Distance Interval Model (DIM) is designed to calculate the minimal and maximal road network distances between moving objects and query point. Furthermore, we propose a novel Possibility-based Vague KNN (PVKNN) algorithm to process the query efficiently, which determines the CKNN query results with possibility within each division time subinterval of given time interval by applying the vague set theory. In the PVKNN algorithm, the query efficiency can be improved significantly with the pruning, distilling and possibility-ranking phases. With these phases, the objects candidates are scaled down and the given time interval is divided into subintervals to reduce the repetitive query cost. In addition, an index structure TPR^uv-Tree is designed to efficiently index moving objects with uncertain velocity in road network by involving edge connection and moving objects information. Experiments with simulation and comparison show that significant improvement in the performance of efficiency can be achieved with our proposed algorithms.