基于分段地址结构的快速路由查找算法

根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法。根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中。不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度。     

B+树算法的Java实现方法研究

随着人们对移动数据处理和管理需求的不断提高,与各种手持设备能够紧密结合在一起的嵌入式数据库逐渐成为人们研究的热点。而B+树作为一种成熟的数据结构,在数据库索引构建以及文件索引数据组织方面具有极其广泛的应用。为深入研究嵌入式数据库中B+索引的构建机制,文中使用Java语言实现了基于内存的B+树,并对其性能进行了评估测试。测试结果表明,该B+树具有良好的数据处理能力。     

双数组Trie树索引的可操作性研究①

双数组是组织和实现Trie树的一种数据结构。双数组Trie树索引实现的是一种线性时间复杂度的搜索机制,因此被广泛的应用于信息检索和中文分词等领域。然而双数组Trie树索引建立后不易于更新,限制了这种索引的现实应用。在前人的双数组Trie树优化索引构造的基础上,分析了插入和删除操作的所有可能情况,提出了对双数组Trie树索引进行相关操作的算法。最后分析了其时间和空间开支,并用实验结果证明了其可行性。     

基于SSD的Key-Value系统优化设计与实现

随着互联网技术的迅猛发展,越来越多的非结构化数据涌入到人们的生活中,为这些数据建立高效的索引面临极大的挑战.键值数据库Key-Value以其结构简单和高扩展性而引起人们的广泛关注,已成为海量数据存储系统中的重要组成部分.由于Key-Value系统对吞吐量要求较高,而基于Flash的固态硬盘(solid state drive,SSD)能够提供很高的随机读性能,在SSD上构建Key-Value系统已成为海量数据存储领域的一大研究热点.鉴于Flash具有非定点更新、寿命有限等特性,基于SSD的KeyValue系统必须针对Flash的特性作专门优化.以一种称为SkimpyStash的基于SSD的Key-Value系统为基础,提出了一种新的Key-Value系统低延迟存储系统(low latency store,LLStore).LLStore使用内存文件映射技术来减少针对SSD的IO请求,除此之外,针对SkimpyStash中低效的压缩策略,提出一种改进方法,可以在少量增加内存开销的情况下极大地减少查询时间.通过与原系统的性能比较实验,LLStore在平均查询时间上可以获得至少12%的加速.     

一种改进的IPV6最长前缀匹配路由查找算法

本文就是在研究已有算法的基础上,结合IPv6地址的特征以及路由表中前缀的分布规律,提出了一种改进的、基于索引表和Trie树的查找算法,该算法在时间复杂度和空间复杂度上表现出了较好的性能。     

基于有限状态机和Trie数的分级地址模型

针对地理编码系统中地址正确性校验、地址不规则命名和地址跳跃的问题,提出了运用有限状态机理论建立分级地址的转换模型,同时用Trie树来建立有限状态机中各个地址的转换函数,给出了转换函数的初始化和训练过程。测试数据对模型的验证表明,使用有限状态机和Trie树建立的地址模型,初步解决了地理系统编码中的地址校验、不规则命名和地址跳跃的问题。     

基于分布式内存数据库的移动对象全时态索引

针对现有移动索引仅对内存/磁盘两层结构进行优化,忽略了索引节点在内存中的缓存敏感性,提出一种基于分布式内存数据库的全时态索引结构DFTB^x树。该索引结构针对存储器Cache、内存和磁盘3层结构进行优化,根据Cache行、指令数量和TLB失配数等多个条件设计内存索引节点的大小。同时,根据磁盘数据页的大小设计历史数据迁移链节点的大小,使得Cache和内存能够一次读取索引节点和迁移链节点数据,避免多次读取数据带来的延迟。此外,构建历史数据迁移链,实现历史数据持久化,从而支持移动对象全时态索引。实验结果表明:与B^x树、B^dual树、TPR*树和STRIPES算法相比,DFTB^x树具有较高的查询和更新效率。     

基于Linux内核的Key-Value存储系统——KStore

Key-Value存储系统在各种互联网服务中被广泛使用,但现有的Key-Value存储系统通常在用户态空间设计和实现,因为频繁的模式切换和上下文切换,导致访问接口、事务处理效率不高,在高并发、低延迟的数据存储需求中尤为突出.针对该问题,给出了一个内核态Key-Value存储系统的实现--KStore:提供内核空间的索引和内存分配机制,并在此基础上,通过基于内核Socket的远程接口以及基于文件系统的本地接口,保证了KStore的低延迟;同时,通过基于内核多线程的并发处理机制,保证了KStore的并发性.实验结果表明,与Memcached相比,KStore在实时性和并发性方面都取得显著优势.     

一种新的快速IPv6路由查找算法

在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。     

内存数据库系统SwiftMMDB索引机制的设计与实现

T树结合了平衡二叉树(AVL树)和B树的优点,可以有效地组织索引数据,从而为内存数据库提供优良的存储效率和查询性能。结合自主开发的一个内存数据库系统SwiftMMDB介绍T树索引的设计与实现,并通过节点分裂、填充等方法改进了经典T树的插入和删除操作,减少了T树中平衡旋转的次数,从而进一步提高内存数据库检索的效率和性能。     

基于NOR Flash实现KV数据库的应用研究

为在水文自动测报系统遥测站的遥测终端机中基于NOR Flash存储器可靠地存放系统运行参数,分析遥测终端机中常用固态存储器的读写特点和KV键值数据库的实现方式,设计一种基于W25Q256存储器实现KV键值数据库的解决方案.方案充分应用NOR Flash存储器的读写特点,针对同一个地址重复写入的最小编程颗粒度为1 bit,结合KV键值实现一个键值对状态的顺序变化,进而通过在存储器的一段空间内顺序增加地址存放KV键值对,实现KV键值对的新增、修改、删除和检索操作,达到磨损均衡和异常掉电恢复效果.在嵌入式系统中,相较于常用的采用固定地址保存运行参数的方案,该研究方案能有效延长NOR Flash存储器的使用寿命,提高系统的稳定可靠性.     

基于UML技术的空间基础数据库设计与实现

设计合理的空间基础数据库不仅能提高整个空间数据操作时的性能和效率,而且还可以减少后期的维护修复工作,使整个空间基础数据运行的更加快捷,需要对空间基础数据建立数据库;当前的空间基础数据库设计方法采用ArcSDE数据引擎对空间基础数据进行不断地更新调整,再利用多源空间数据格式转换的技术对空间基础数据库进行设计,存在空间基础数据运行时速度缓慢,计算精度低的问题;为此,提出了一种基于UML技术的空间基础数据库设计方法;该方法首先在空间基础数据库设计中建立空间基础数据索引结构,利用R-树族构建空间基础数据索引树,依据空间基础数据索引树,扫描索引空间基础数据,过滤掉不满足查询条件的空间基础数据对象,使空间数据查询结果可以在额定时间内获得,然后采用空间基础数据点、数据线、以及由数据线组成的区域、一组区域、空间基础数据网络的详细存储方式对空间基础数据进行存储,利用MongoDB驱动程序对矢量空间数据进行存储存储,最后通过对空间基础数据库索引、查询、存储等设计实现了空间基础数据库的建立;仿真实验结果证明,所提方法提高了空间基础数据的建库速度,减少了数据运行的时间,提升了空间基础数据的利用率。     

基于中间点划分无冲突哈希的高速包处理

通过在高速片上存储器上存储所有的攻击特征,实现对数据包的高速检测。针对有限的片上存储器空间,提出一种新的基于中间点划分无冲突哈希函数的trie树结构,将攻击特征串平均分配到trie树每层的多个组中,实现对片上存储器有效的控制。通过在同一个芯片中采用流水并行方式执行查询操作,获得更高的吞吐量。存储中间点的空间复杂度为O(n),哈希表的构建时间随攻击特征数量线性增长。实验结果表明：该方法降低了片上存储空间需求,在片上存储器只需执行一次即可完成特征匹配操作。     

MPI framework for parallel searching in large biological databases

In this paper, we address the problem of searching huge biological databases on the scale of at least several gigabytes by utilizing parallel processing. Biological databases storing DNA sequences, protein sequences, or mass spectra are growing exponentially. Searches through these databases consume exponentially growing computational resources as well. We demonstrate herein a general use, MPI based, C++ framework for generically splitting databases amongst several computational nodes. The combined RAM of the nodes working in tandem is often sufficient to keep the entire database in memory, and therefore to search it efficiently without paging to disk. The framework runs as a persistent service, processing all submitted queries. This allows for query reordering and better utilization of the memory. Thereby, we achieve superlinear speedups compared to single processor implementations. We demonstrate the utility and speedup of the framework using a real biological database and an actual searching algorithm for mass spectrometry.     

面向大数据流的分布式索引构建

大数据流的高效存储与索引是当今数据领域的一大难点.面向带有时间属性的数据流,根据其时间属性,将数据流划分为连续的时间窗口,提出了基于双层B+树的分布式索引结构WB-Index.下层B+树索引基于窗口内流数据构建,索引构建过程结合基于排序的批量构建技术,进一步对时间窗口分片,将数据流接收、分片数据排序以及B+树构建并行化,提高了构建性能.上层B+树索引基于各时间窗口构建,结合时间窗口时间戳的递增性和无限性,提出了避免节点分裂的构建方法,减少了B+树分裂移动开销,提高了空间利用率和更新效率.WB-Index架构中,将流数据和索引分离,同时利用内存缓存尽可能多的双层B+索引和热点数据来提高查询性能.理论和实验结果表明,该分布式索引架构能够支持高效的实时数据流写入以及流数据查询,能够很好地应用于具有时间属性的数据流场景.     

Longest-match string searching for ziv-lempel compression

Ziv-Lempel coding is currently one of the more practical data compression schemes. It operates by replacing a substring of a text with a pointer to its longest previous occurrence in the input, for each coding step. Decoding a compressed file is very fast, but encoding involves searching at each coding step to find the longest match for the next few characters. This paper presents eight data structures that can be used to accelerate the searching, including adaptations of four methods normally used for exact matching searching. The algorithms are evaluated analytically and empirically, indicating the trade-offs available between compression speed and memory consumption. Two of the algorithms are well-known methods of finding the longest match—the time-consuming linear search, and the storage-intensive trie (digital search tree). The trie is adapted along the lines of a PATRICIA tree to operate economically. Hashing, binary search trees, splay trees and the Boyer-Moore searching algorithm are traditionally used to search for exact matches, but we show how these can be adapted to find longest matches. In addition, two data structures specifically designed for the application are presented.     

ETI: an efficient index for set similarity queries

Set queries are an important topic and have attracted a lot of attention. Earlier research mainly concentrated on set containment queries. In this paper we focus on the T-Overlap query which is the foundation of the set similarity query. To address this issue, unlike traditional algorithms that are based on an inverted index, we design a new paradigm based on the prefix tree (trie) called the expanded trie index (ETI) which expands the trie node structure by adding some new properties. Based on ETI, we convert the TOverlap problem to finding query nodes with specific query depth equaling to T and propose a new algorithm called TSimilarity to solve T-Overlap efficiently. Then we carry out a three-step framework to extend T-Overlap to other similarity predicates. Extensive experiments are carried out to compare T-Similarity with other inverted index based algorithms from cardinality of query, overlap threshold, dataset size, the number of distinct elements and so on. Results show that T-Similarity outperforms the state-of-the-art algorithms in many aspects.     

实时数据库混合索引机制的设计与实现

在卫星地面设备监控中,需要将大量实时数据实时地存进数据库并提供实时查询。针对实时数据和Judy array数字树的特点,提出了一种基于内存映射文件的位图分配法,然后设计了一种哈希表、B+树和Judy array混合索引机制。通过大量记录的插入和查询,结果表明位图分配法能避免大量不可利用的内存碎片的产生,结合内存位图分配法的混合索引机制也为应用程序提供了实时的索引插入和查询。     

三维地形中多分辨率影像模型建模方法①

使用高分辨率纹理是增强地形真实性最常用的有效方法,但由于其数据量的庞大需要对纹理影像进行分块处理。为了解决常规手工纹理分块的不足,给出了影像纹理的自动分块原则和方法,提出了一种基于视点的动态多分辨纹理模型和确定纹理分辨率的算法,设计了管理纹理数据的数据结构和数据库存储方案。试验表明,该方法在不降低显示质量的同时,能有效减少纹理的渲染量和较好的可视化效果。