时空数据库索引研究

时空数据库为了快速访问其庞大的数据量,必须建立有效的时空索引以提高各类时空查询效率.本文提出了一种基于3D R-tree算法的时空索引方法:3D R*-tree.3D R*-tree是利用"退化模型"和R*-tree对3D R-tree进行了有效的扩展,有更好的查询效率且支持在线数据模式,较之3D R-tree和HR-tree在查询效率上有明显的提高,在文中给出了关键的数据结构和试验对比结果.     

一种基于 R* -tree的时空索引

时空数据是一种特殊的多维数据，其每一数据项的时间戳值是单调递增的。3D R-tree把时间看作为空间的另一维，然后利用R-tree进行空间索引，查询效率比较低而且只能处理离线数据。而HR-tree将时间维孤立出来，同时保存每一时间戳的空间数据，查询效率较高但是空间开销大。该文提出了一种基于R*-tree算法的时空索引方法。该方法比3D R-tree有更好的查询效率且支持在线数据模式．较之HR-tree在保证查询效率的同时使用更少的存储空间，最后给出了试验对比结果。     

支持预测查询和部分历史查询的移动对象索引方法

针对TPR*-tree隐含移动对象部分最近历史信息但不能提供历史信息查询的问题,将移动对象创建或更新时间引入到索引树中,提出一种既支持预测查询又支持部分历史信息查询的索引树Basic HTPR*-tree,为全时态查询奠定了坚实的基础.同时,为了支持移动对象的频繁更新,在Basic HTPR*-tree索引树基础上引入内存概要结构和Hash辅助索引结构,提出支持自底向上更新策略的HTPR*-tree索引结构.实验结果表明,HTPR*-tree更新性能优于TPR*-tree和Basic HTPR*-tree(TD_HTPR*-tree),预测查询性能仅仅稍逊于TPR*-tree.     

存取代价模型R-tree优化算法的研究

Guttman的R-tree是在空间数据索引上用处最广泛的动态索引。然而试验显示：R-tree及其变种索引的存储使用率仅仅达到70％左右，插入，删除，查询的平均时间也比较高。本文中，提出一个R-tree空间数据索引的存取数目代价模型，在对该模型分析的基础上提出的一种紧骤R-tree算法，这种算法与其他的R-tree及其变种相比是很有竞争力的：它的存储使用率几乎可以达到100％，同时建造一个紧骤R-tree的代价是最低的。     

位置服务中对移动物体的时空索引

在TPR*-tree的基础上提出了DTPR*-tree索引结构, 引进了事务时间和有效时间.它能索引移动物体过去、当前和未来的位置信息,支持基本位置查询和空间约束查询,有很好的空间、查询和更新效率.     

基于CB+-tree的时态XML索引

针对时态查询与时间属性紧密相关的特点,利用时间区间作为改进后B+-tree的索引关键字建立索引,改进后的B+-tree命名为Changing B+-tree(CB+-tree)。实验证明,在CB+-tree上进行时态查询比B+-tree及基于DOM的XML文档的查询效率有所提高。     

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

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

存取代价模型R-tree优化算法的研究

Guttman的R-tree是在空间数据索引上用处最广泛的动态索引。然而试验显示:R-tree及其变种索引的存储使用率仅仅达到70%左右,插入,删除,查询的平均时间也比较高。本文中,提出一个R-tree空间数据索引的存取数目代价模型,在对该模型分析的基础上提出的一种紧骤R-tree算法,这种算法与其他的R-tree及其变种相比是很有竞争力的:它的存储使用率几乎可以达到100%,同时建造一个紧骤R-tree的代价是最低的。     

COCOMOⅡ--软件项目管理中的成本估算方法

结构化成本模型（COCOMO：Costructive Cost Model)是一种成熟的软件成本估算方法,将介绍其第二版：COCOMOⅡ模型的基本思路和使用方法,以及对原有COCOMO模型的改进。     

基于路网的移动对象动态双层索引结构

为了支持对大规模不确定性移动对象当前及将来位置的查询,亟需设计更加有效和高效的索引结构.当前索引算法主要考虑索引建立和维护的效率问题或关注基于索引进行查询时的准确性,对索引建立维护以及查询时性能综合考虑的研究较少.针对已有方法的不足,提出基于路网的移动对象动态双层索引结构DISC-tree,对静态路网信息采用R~*-tree索引,对实时更新的移动对象运动轨迹采用结点更新代价较小的R-tree进行索引,设计哈希表和双向链表辅助结构对索引协同管理.成都市真实地图数据集上的实验结果表明:相比于经典的NDTRtree,DISC-tree在索引建立和维护方面时间代价平均减少39.1%,移动对象轨迹查询时间代价平均减少24.1%;相比于FNR-tree,DISC-tree的范围查询准确率平均提高约31.6%.     

R*-树空间索引的优化研究

针对大型空间数据库应用的需求及己有空间索引技术的不足，在论述R-树及R*-树索引技术的相关概念、数据结构、算法描述及性能分析的基础上，提出了一种改进的R*-树空间索引结构。研究结果表明：改进后的R*-树与原始的R*-树相比具有更高的性能。     

基于栅格的R树更新缓存与批处理机制

根据对象分布相对稳定的特点,选择与固定栅格对应的、代表对象分布情况的部分叶子节点作为容纳新记录的种子节点,新记录可直接与种子节点合并而无须遍历R树。随机选择部分无法合并的记录作为种子记录,对活动记录进行简单有效的分组,以插入种子记录的代价实现批量插入。上述2种方法考虑了R树的空间聚簇特性,可在一次更新中完成多项插入与删除,减少了对节点的写操作及对R树的遍历次数。实验证明,该机制在降低索引维护I/O开销的同时保证了查询效率。     

基于R树的空间数据索引技术的探索

目前,基于空间数据库管理系统的空间数据索引技术的研究与应用正不断地兴起,且日趋成熟。分析经典的空间数据索引技术R-树和R^＊-树的优势与特点,在R^＊-树索引结构的基础上融合了传统的四叉树索引方法的精髓,提出了一种改进的R^＊-树索引技术一即R^＊Q-树索引方法。设计并实现了R^＊Q-树索引方法中索引构造算法的主要改进部分,并采用大量的随机实验数据验证了改进算法对提高空间数据索引效率的有效贡献。     

基于空间数据不同索引方法的比较

空间索引是空间数据库的关键技术，其性能的高低决定着整个数据库的效率。本文分别对R树及其变形树、四叉树、网格文件作了介绍，并基于空间数据对这几种索引结构的性能作了比较，其结果为今后进一步研究提供了参考依据。     

GLIP: A Concurrency Control Protocol for Clipping Indexing

Multidimensional databases are now beginning to be used in a wide range of applications. To meet this fast-growing demand, the R-tree family is being applied to support fast access to multidimensional data, for which the R+-tree exhibits outstanding search performance. In order to support efficient concurrent access in multi-user environments, concurrency control mechanisms for multidimensional indexing have been proposed. However, these mechanisms cannot be directly applied to the R+-tree because an object in the R+-tree may be indexed in multiple leaves. This paper proposes a concurrency control protocol for R-tree variants with object clipping, namely, Granular Locking for clIPping indexing (GLIP), dubbed an R+-tree variant, the Zero-overlap R+-tree (ZR+-tree). To the best of our knowledge, GLIP is the first concurrency control approach designed specifically for the R+-tree and its variants. The proposed GLIP supports efficient concurrent operations on R+-trees with serializable isolation, consistency, and deadlock-free. Experiment results on both real and synthetic data sets validated the effectiveness and efficiency of the proposed concurrent access framework.     

一种全新的 R树节点选择算法 *

在 R树插入算法中采用全新的节点选择算法 ,一改传统的从根节点开始自上而下的节点选择方案 ,而是从叶节点层开始 ,先自下而上再自上而下地选择叶节点 ,较好地解决了同层节点重叠所导致的查询效率低下的问题。实验证明 ,提出的 R树空间索引方法 ,不仅在查询效率上明显优于 R*树,而且 R树生成的时间开销也减少了 50%左右 ,综合性能超过了 R*树 ,便于扩展到三维甚至多维空间中 ,以实现对空间数据和时空数据的高效查询功能。     

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.     

The DR-tree: A Main Memory Data Structure for Complex Multi-dimensional Objects

An efficient index structure for complex multi-dimensional objects is one of the most challenging requirements in non-traditional applications such as geographic information systems, computer-aided design, and multimedia databases. In this paper we first propose a main memory data structure for complex multi-dimensional objects. Then, we present an extension of the existing multi-dimensional index structure. Among existing multi-dimensional index structures, the popular R*-tree is selected. The R*-tree is coupled with the main memory data structure to improve the performance of spatial query processing. An analytical model is developed for our index structure. Experimental results show that the analytical model is accurate, the relative error being below 15%. The performance of our index structure is compared with that of a state-of-the-art index structure by experimental measurements. Our index structure outperforms the state-of-the-art index structure due to its ability to reduce a large amount of storage.     

TPR^＊树索引构建及其动态维护方法

提出一种新的TPR^＊树索引构建方法,在根节点层利用速度矢量对移动对象集进行划分,根据速度矢量的大小将移动对象聚集到不同子节点中,并逐层构建TPR^＊树。在根节点层用溢出桶存储插入的移动对象记录,同时对TPR^＊树索引进行批量插入更新,以减少其插入更新维护的代价。实验结果表明,该方法是可行的。     

基于惰性聚类分裂的动态R树实现方法

R^＊树是目前公认查询效果很好的R树变体，但是其构造代价较原始R树增加数倍，对于插入删除和更新频繁的空间数据效果不好。为此，本文提出一种基于惰性聚类分裂技术的R树动态实现方法（LR树）。惰性聚类分裂技术是在对象插入节点导致溢出时不立即进行分裂，而是尝试将其插入到邻近的未满节点中，直到邻近节点均已满时，再利用聚类技术进行节点分裂，在邻近节点和分裂节点之间重组入口项。LR树在确保查询性能的前提下，大大降低了构造代价，并且大幅提高了索引结构的空间利用率。最后的分析和实验证明了LR树的高效性。