多版本TPR_TREE

为了解决连续移动物体的全部历史空间信息的索引问题，综合TR树和TPR树的结构，提出了一种新的时空索引结构——多版本TPR树(MVTPR)，对MVTPR的结构和操作进行了说明，并通过实例形象化描述了MVTPR的结构和操作，指出了下一步研究方向。     

频繁更新移动对象的索引方法

在时空数据库中,频繁更新会导致TPR树更新与查询性能下降。针对该问题,提出MAH—TPR索引方法,分别对预处理过程、索引结构及更新算法进行优化。在构建索引及更新操作时,通过使用空间聚类来减少节点间空间区域的交叠几率。引入基于磁盘的Hash辅助存储结构,在直接访问叶节点的基础上进一步减少磁盘I／O的操作。引入基于内存的移动对象辅助存储结构,用于存储发出频繁更新请求,以避免主索引结构节点的合并和分裂。实验结果表明,MAH—TPR索引方法的查询性能优于HTPR方法和LGU方法,更新性能优于HTPR索引方法。     

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

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

面向移动对象的高效预测范围聚集查询方法

预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集TPR树索引,通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价.PRA树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性.提出了一种增强预测范围聚集查询EPRA算法,采用更精确的剪枝搜索准则,减少了查询所需要访问的节点代价.实验结果与分析表明,基于PRA树索引的EPRA查询算法具有良好的查询性能,优于通用的TPR*树索引.     

基于速度分布的移动对象混合索引方法

TPR*树是目前广泛使用的移动对象当前及未来位置预测索引技术,但是其频繁更新及查询性能随着时间变化而急遽下降.文中提出了一种基于速度分布的移动对象混合索引HVTPR树,综合考虑移动对象在速度域和空间域中的分布,首先在速度域中对移动对象集进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶,每个速度桶中移动对象具有相近的速度矢量;对每个速度桶中的移动对象,则利用TPR树进行索引.HVTPR树索引增加了一个建于移动对象标识上的Hash辅助索引结构,并采用增强的自底向上更新(EBUU)算法以提高其频繁更新性能,具有很好的动态更新性能和并发性.实验表明,采用EBUU算法的HVTPR树索引动态更新及查询性能优于TPR*树等通用索引技术.     

移动对象数据库预测范围聚集查询技术研究

针对预测范围聚集查询处理技术，提出了一种面向移动对象的聚集TPR树索引。聚集TPR树索引在TPR树中间节点中加入移动对象聚集信息以减少预测范围聚集查询所需要的节点访问代价。并增加了一个建于移动对象标识上的哈希辅助索引结构以支持自底向上的删除搜索算法，具有很好的动态更新性能和并发性。提出了一种EPRA查询算法，采用更精确的剪枝搜索准则，大大减少了查询所需要访问的磁盘节点，具有良好的查询性能。     

时空数据库中移动对象查询的选择性估算

目前,用来估算查询选择性的最有效的技术是直方图技术。通过特定的改进,直方图也可应用到时空查询优化中。TPR 树在对未来预测的时空索引中显示了很好的优越性。结合TPR 树索引结构,构建满足时空查询的直方图,估算时空查询的选择性。     

基于TPR树的索引技术研究

分析了移动对象位置的索引技术,介绍了可以有效的索引移动对象的当前和未来位置的索引结构——TPR树(time-parameterized R tree),并对其进行改进,改善了其查询性能。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

面向海量点云快速显示的叠加型金字塔索引结构研究

针对激光雷达三维点云数据量大,当计算机内存有限时进行点云读取与处理存在严重滞后的问题,提出了一种叠加型金字塔索引结构。首先,采用一种基于点云最小外包络的不均匀分块策略,将点云数据划分成若干独立的数据块;待分块完成后,利用提出的叠加型索引结构对每个分块构建金字塔;最后,将生成的金字塔按照指定的文件结构存储,生成索引文件。利用机载实测点云数据开展了验证实验,结果表明:该算法有效地降低了索引文件占据的计算机空间资源,实现了海量三维点云数据在有限内存空间的快速显示。     

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.     

用卫星数据域改善高维数据的相似性检索性能

提出了一种新的高维数据空间的索引结构XSA—tree．它扩展了现有索引结构SA—tree，提出了卫星数据域的思想，以增强索引的过滤能力．通过对根节点中数据点选取进行优化，以得到相对平衡的索引树．文中给出了该索引结构并详细介绍了相关索引算法．实验结果表明，该索引结构显著提高了高维数据空间中相似性检索性能．是一种有效的高维索引结构．     

Exploiting geographic references of documents in a geographical information retrieval system using an ontology-based index

Both Geographic Information Systems and Information Retrieval have been very active research fields in the last decades. Lately, a new research field called Geographic Information Retrieval has appeared from the intersection of these two fields. The main goal of this field is to define index structures and techniques to efficiently store and retrieve documents using both the text and the geographic references contained within the text. We present in this paper two contributions to this research field. First, we propose a new index structure that combines an inverted index and a spatial index based on an ontology of geographic space. This structure improves the query capabilities of other proposals. Then, we describe the architecture of a system for geographic information retrieval that defines a workflow for the extraction of the geographic references in documents. The architecture also uses the index structure that we propose to solve pure spatial and textual queries as well as hybrid queries that combine both a textual and a spatial component. Furthermore, query expansion can be performed on geographic references because the index structure is based in an ontology.     

一种并行计算平台KD-60上的可实时更新文本搜索

实时性是影响搜索引擎性能的重要因素.针对这个因素,提出一种可实时更新的倒排索引结构并将其应用于国产万亿次高性能计算平台KD-60.该方案采用主、辅倒排索引和内容过滤索引相结合的方式,实现了搜索过程的实时性.同时,我们将其应用于高性能绿色计算平台KD-60,使之在一定的程度上实现了搜索的高效能.实验证明,基于KD-60平台的倒排索引结构有效的解决了搜索引擎的实时性问题,并可作为绿色计算的实际应用的一个典型实例.     

一种快速的子序列匹配算法

提出一种在时间序列上快速匹配子序列的算法,该算法不同于FRM算法,而是采用VA-file这种索引结构,将数据点直接存储在索引上,并在该索引的基础上设计了一种进行范围查询的方法.实验采用了三种时间序列数据集,从不同的角度验证算法的有效性,结果表明该算法大大提高了查询性能.     

KDT树:一种多维空间数据索引结构

通过扩展KD树索引结构,提出了一种新的多维空间数据索引结构——KDT树,给出了数据结构和算法描述,并通过与当前流行的空间数据索引结构——R树的对比,对其性能进行了测试与评估。实验表明,作为一种主存索引结构,KDT树在时间效率方面明显优于R树,并且此种优势随着索引记录数量的增多而越加明显。此外,KDT树亦能较好地解决常规KD树在索引占据一定空间范围的空间对象(如:线、面、体等)时存在的问题。     

有效支持全文本检索的XML索引技术研究

在XML文档上进行全文本检索已经成为很多研究课题的基础问题,例如Web信息检索,信息抽取等。有效的XML索引结构对于加速检索速度是至关重要的,在文献[1]的基础上全面地构建和实现了一个可以有效的支持XML全文本检索的索引结构。实验表明提出的索引结构在索引构建时间、空间等性能指标上均有很好的表现。     

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

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