An Efficient Method for Version Control of a Tree Data Structure

A new method for version controlling of a tree structure is presented. The key feature of the method is that the latest state of a tree is retained and other versions are constructed from it on request, and information on the change history of a node is maintaind in its parent node. Several algorithms for efficient manipulation of the tree have been developed, and it has been demonstrated that they correctly manipulate the tree. The performance of these algorithms has been compared with those of other tree-based methods, and found to be nearly optimal in all aspects of the comparison. © 1997 John Wiley & Sons, Ltd.     

Z树：一个高维度的数据索引结构

Z树能够高效地处理对高维度数据集的矩形区域查询和最邻近搜索。它按照节点的形状变化量优化数据的插入位置，使节点形状趋于合理。文章给出了一个新的无重叠分裂算法，减少超级节点的产生。引入了动态剪枝和重新插入策略，压缩超级节点的数量和体积。提出了矩形节点的球形化方法和最优子树搜索算法。实验表明Z树的矩形区域查询和最邻近搜索的效率远远高于X树和SR树。     

一种有效的实现分裂合并算法的数据结构

针对现有分裂合并分割算法数据结构存在的问题，本文设计了一种新的数据结构。这种数据结构能非常方便地实现分裂合并算法的每一步骤以及动态地分配内存，从而显著地减少了计算时间并在内存需求上有一定的改善。实验结果表明用这种数据结构实现分裂合并分割算法是有效的。     

一种树型结构的数据恢复功能的实现方案

本论文首先描述了一种数据恢复功能的总体设计思想;在此基础上,根据树型数据结构的特点,具体化总体设计思想,设计出一套高效数据恢复功能的实现方案,达到时间和空间上的优化;最后,以接近C 的伪代码方式,描述了该方案实现的部分算法。     

通用树形结构设计

本文介绍了通用树的设计原理和实现方法,并运用数据库技术、.NET编程技术对通用树形结构组件进行了模型设计、编程实现。该通用树形结构的实现,对于实现软件代码的重用,增强应用系统的灵活性和伸缩性,具有重要作用。     

一种适于网格生成环境的有效数据结构

设计了一种适于描述网格对象的称为扩展的翼面结构的数据结构,它同时表达一个面片的二个有向面,并通过边句柄对整个网格对象进行操作;进而采用面向对象的程序设计技术,设计并实现了一个集成平面、曲面以及体网格的网格生成与分析系统,并在航空业中得到了成功应用。     

基于OBB树的无网格几何数据处理

提出一种新的基于有向包围盒树(Oriented Boundmg Box,OBB树)的处理无网格几何数据方案.与最常用的八叉树比较,它具有三方面优点:首先,OBB树反映了统计意义上的几何模型空间分布,它不仅提供了辅助的层次结构,其本身还可以用于生成原始几何模型的形状逼近;其次,OBB树的节点数目和所需内存比八叉树少,且更贴近几何模型;其三,遍历OBB树的代价略高于八叉树,收敛速度却更快.针对点云模型,作者将OBB树结构应用于点云模型的自适应绘制.实验结果验证了OBB树的上述优点.     

Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation

In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, notably sparse matrices. In particular, we demonstrate that for any matrix, the BDD representation can be no larger than the corresponding sparse-matrix representation. Further, the BDD representation is often smaller than any other conventional special-case representation: for the n×n Walsh matrix, for example, the BDD representation is of size O(log n). No other special-case representation in common use represents this matrix in space less than O(n²). We describe termwise, row, column, block, and diagonal selection over these matrices, standard an Strassen matrix multiplication, and LU factorization. We demonstrate that the complexity of each of these operations over the BDD representation is no greater than that over any standard representation. Further, we demonstrate that complete pivoting is no more difficult over these matrices than partial pivoting. Finally, we consider an example, the Walsh Spectrum of a Boolean function.     

ZDC-tree:一种支持面向数据流Skyline查询的高效索引结构

数据流上的Skyline查询是近年来数据管理与数据挖掘领域的研究热点.该文针对数据流场景下基于滑动窗口Skyline查询问题,采用基于剪枝策略和分而治之思想,并结合Z-order曲线的性质,提出一种可以在一个分支上进行查询和更新操作的ZDC-tree索引结构,并给出可有效维护Skyline查询计算的ZDCSK算法.算法采用自底向上的方式,归并递归返回Skyline结果集,具备较好的Skyline查询效率.论文从理论和实验上证明了在ZDC-tree上进行Skylike查询的高效性、稳定性及可扩展性.     

A Valid and Efficient Trinomial Tree for General Local-Volatility Models

Computational Economics - The local-volatility model assumes the instantaneous volatility is a deterministic function of the underlying asset price and time. The model is very popular because it...     

一种用于多模式匹配的高效二叉检索树

网络环境的文本检索往往是同时面向大量用户的,传统的单模式匹配算法无法应付数量巨大的关键字,而一般的基于Trie树的多模式匹配算法又存在空间复杂度不良、结构复 杂等问题。针对这种检索大量关键字的应用,本文通过修改Trie树节点的结构得到一种更为简单的多模式匹配算法。该算法既有多模式匹配的性能,又具有高效的空间利用率,并且非常容易实现。     

Dynamic Tubular Grid: An Efficient Data Structure and Algorithms for High Resolution Level Sets

Level set methods [Osher and Sethian. Fronts propagating with curvature-dependent speed: algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79 (1988) 12] have proved very successful for interface tracking in many different areas of computational science. However, current level set methods are limited by a poor balance between computational efficiency and storage requirements. Tree-based methods have relatively slow access times, whereas narrow band schemes lead to very large memory footprints for high resolution interfaces. In this paper we present a level set scheme for which both computational complexity and storage requirements scale with the size of the interface. Our novel level set data structure and algorithms are fast, cache efficient and allow for a very low memory footprint when representing high resolution level sets. We use a time-dependent and interface adapting grid dubbed the “Dynamic Tubular Grid” or DT-Grid. Additionally, it has been optimized for advanced finite difference schemes currently employed in accurate level set computations. As a key feature of the DT-Grid, the associated interface propagations are not limited to any computational box and can expand freely. We present several numerical evaluations, including a level set simulation on a grid with an effective resolution of 1024³     

通用结构下的位置相关丛生树模型

在并行查询处理研究中,人们提出了三种基本的查询规划树表示形式,即左深树,右深树和丛生树形式。丛生树由于其搜索空间巨大,实际应用中往往需要对其搜索空间加以某种限定。结合通用并行结构的特点,利用数据位置相关特性首次提出了一种新的受限丛生树结构。即位置相关丛生树。     

树形网络中的一种有效视频内容分发算法

随着互联网中视频内容比重的迅速增加,视频业务随之也在不断的增加,这些视频业务将占据大量的互联网带宽.如何节约带宽和提高视频服务质量已成为互联网研究中的重要研究课题,而提高视频业务服务质量的两个主要途径是增加网络带宽和增加网络中缓存视频服务器的容量.为了使得视频服务商对增加带宽和增加缓存容量的投入最小化,就要决定网络视频内容在网络服务器中如何放置和分发.在本文中,首先我们基于内容放置和内容传输代价对树形网络中的视频内容放置问题进行数学建模,其次我们根据该数学模型提出一种有效的动态规划算法.该算法不仅可以有效解决了我们提出模型中的整数规划问题,而且其时间复杂度为O(NP).     

数据结构二叉排序树的应用研究

随着图书商城的大型化,顾客对图书信息的检索量也随之俱增,如何提高图书信息检索效率已成为急需解决的问题。本文研究基于数据结构二叉排序树的图书信息动态检索方法,采用这种方法可提高图书信息的检索效率。     

基于树结构的Web信息抽取

信息提取就是从大量的数据中检索出有用的信息,但一般的Web信息提取技术都是基于对Web上HTML文档的分析.文中提出了一种先将HTML转化为XML形式,再提取信息的方法.XML是用于描述在Intemet网上用于数据交换的数据文档的格式的一种语言标准,它将结构、内容和表现分离.数据可被XML唯一标识,从而有利于用户对数据的组织和检索.这种方法能够达到较高的正确率,同时随着文档的增大,方法也能够保证线性的时间复杂度.     

RB+树——一种列存储数据的树型索引结构

索引技术是提高海量数据查询效率的关键技术之一.传统索引如B+树等在更新事务环境中具有较好的性能,然而在面向列存储的分析型数据仓库查询环境下,时间空间代价较大.根据列存储数据仓库查询环境的特点,提出一种新型树型索引--RB+树(reduced B+-tree).该索引对传统B+树结构进行了改进,并结合自底向上创建索引树的方法,使得索引的空间利用率、创建和查找效率得到显著的提高.进一步将RB+树应用于列存储数据仓库中,建立了行号索引、列值索引,特别地为解决星型模型中多表连接问题提出连接索引,有效地提高了列存储数据仓库中元组重构与多表连接的效率.在数据仓库基准数据集SSB上的实验验证了方法的有效性.     

一种高效的海量数据储存方案

为解决传统地理信息系统在离线状态下无法正常运行的问题,设计本地缓存机制,提出一种基于四叉树索引的海量数据储存方案。采用四叉树文件系统管理本地缓存,包括数据的添加、读取、查询和删除,避免传统Windows文件系统储存大量小文件时存在的文件操作耗时长的弊端。实验结果证明,该方案能实现数据加密,提高地理信息数据的安全性,与Windows文件系统相比,更适用于本地缓存。     

一种应用于闪存数据库的高效B+树索引机制

为解决现有闪存数据库索引机制无法同时具备高索引更新性能和高检索性能的问题,提出一种应用于闪存数据库的高效B+树索引机制。该机制采用日志方式更新索引,利用日志缓存区保证日志快速写入闪存。针对日志方式检索效率低的缺陷,设计节点日志映射表,通过哈希映射直接索引节点更新记录,避免全局搜索节点日志。将更新日志整合为B+树逻辑节点,使索引检索转化为B+树深度搜索,在此基础上设计节点缓存区,提高节点检索效率。实验结果表明,该机制相比日志型索引机制BFTL,更新效率提高了51%、检索效率提高了2.3倍,相比基于Nand闪存转换层的B+树索引机制,在保证与其相当的高检索效率的同时,更新效率提高了2.4倍。