列存储数据仓库中基于概率的保序字符串压缩方法

数据仓库中采用按列存储的方式更有利于数据的压缩,保留顺序的轻量级压缩方法对列存储的字符串属性压缩显示其优越性,然而现有做法很难兼顾字符串出现的概率对压缩效率的影响,影响了压缩性能.因此,提出一种基于概率的保序字符串压缩方法.首先,提出一种扩展的共用叶子结构,使得编码索引和解码索引共享同一个码表,大大减少了编码和解码索引的维护时间.同时在该结构中,记录字符串出现的概率,并根据概率的高低建立解码索引,有效降低了高频字符串的解压时间.进一步,根据列存储的特点,将用于列连接的行号信息保存在扩展的叶子结构中,从而有效减少了列值索引的存储空间和创建时间.实验结果验证了该方法的有效性.     

一种改进的XML压缩树索引技术

压缩树索引技术是XML数据压缩的热点问题之一,本文提出一种压缩树索引改进方法.针对压缩树在查询过程中不能很好的解决向上匹配与向下匹配的问题,改进方法引入正排索引和倒排索引.当查询到组一级时,利用正排索引可以快速的查找出以该组为父节点的子组.而选出符合值谓词的元素后,在进行向上匹配时利用倒排索引可找出该元素的父节点.新的索引方法在保留原压缩树索引优点的基础上,解决了压缩树索引在查询过程中匹配问题.     

用改进的游程编码方法压缩值索引

为了进一步提高采用游程编码方法压缩值索引的效率,针对原有方法的不足之处,采取了两个改进措施,一是在索引前排序被索引的数据表使得值索引中的0串和1串更长,二是改进现有编码算法使之可以同时压缩0串和1串。实验结果表明,采用改进后方法压缩值索引形成的压缩文件体积仅为采用原有方法时的11.83%。     

支持块编辑距离的索引结构

在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.     

一种基于编码压缩的数据广播关键字索引方法

无线环境的特殊性导致传统的关键字检索方法不能很好地用于周期数据广播之中.倒排表是全文检索中广泛使用的一种索引技术,但倒排表索引和基于哈希的数据索引无法解决索引结构过大的问题.为此,在周期数据广播环境下,提出一种新型的关键字索引结构,对倒排表进行编码压缩,缩减索引结构来减少访问时间和调谐时间.同时,与编码压缩索引相结合,设计一种周期数据广播下的文档调度方法.在真实数据集上进行的实验结果表明,该方法可缩减索引结构的规模,降低访问延迟和能耗.     

全文检索字索引技术的研究与实现

针对中文全文检索字表法检索索引的创建，提出了快速的建立方法，并根据中文文体的特点，提出了有效的索引压缩方法。实验表明，使用虚拟内存技术可以大大节省索引的建立时间；采用字节对齐的索相压缩技术，不但可以有效地减少索引占用的磁盘空间，而且可以加快检索时间，索引的空间和时间效率都得以提高。     

编码单位可变的倒排索引压缩算法研究

倒排索引是大多数大型文本搜索系统的核心数据结构，索引压缩可以有效地减少倒排索引的空间占用，提升检索效率。针对倒排索引压缩算法中的字节对齐编码进行研究，对于其压缩率不够优秀的问题，提出了分区可变单位编码（PVU编码）。算法以可变单位方式代替固定字节存储，使实际存储空间更加贴合原码长度，从而提高压缩效果。针对序列均匀分区并非最优分区的问题，提出将最优分区问题转化为图论中最短路径问题的方法，使用Dijkstra算法求解序列的最优编码分区。通过对比实验验证了改进优化的PVU编码相较于传统的字节对齐编码能够更好地压缩倒排索引序列。     

二进制翻译后端指令分级索引策略

随着硬件平台的多元化,软件兼容性问题日益突出,二进制翻译技术是解决软件兼容性问题的重要手段.鉴于二进制翻译系统大部分执行时间消耗在后端指令的查找和执行过程中,高效的指令索引策略可以减少系统的指令查找开销,提高系统的整体效率.在对二进制翻译系统后端指令局部性特征进行统计分析的基础上,设计了一种能充分挖掘现代计算机系统硬件性能的二进制翻译指令分级索引策略.该策略结合二进制翻译系统后端指令特殊的局部性特征,使用针对性的替换算法对后端指令进行缓存,降低了系统的指令查找开销.在引入了LIIS索引策略后,开源二进制翻译系统QEMU的后端指令查找时间减少了70％,整个系统执行效率提高了15％.     

基于划分的增量式字符串相似性连接方法

字符串相似性连接是数据质量管理的基本操作,也是数据价值发现的关键步骤。针对目前已有的方法不能满足面向大数据的增量式处理需求的问题,提出一种面向流式数据的增量式字符串相似性连接方法——Inc-Join,并对方法的索引技术进行了优化。该方法以Pass-Join字符串连接算法为基础,首先,采用字符串划分技术将字符串划分成多个互不相交的子串;然后,建立字符串的反向索引列表并将其作为状态;最后,新增数据只需根据状态进行相似性计算,每次连接操作结束后都对状态进行更新。实验结果表明,Inc-Join方法在不影响连接准确率的同时,有效将长、 短字符串重复匹配次数减少为√n(n是批处理方式的匹配次数)。 实验对3种数据集进行处理,发现使用批处理方式进行相似性连接的响应时间是Inc-Join的1至4.7倍,并呈现急剧递增的趋势;而且优化后Inc-Join方法的响应时间最小只占优化前的3/4,并随处理数据的增多所占比例越来越小。同时优化后的Inc-Join不需要保存状态,再一次减小了算法执行的时间和空间开销。     

基于B*树聚簇索引的加密字符串查询方法

为了提高在数据库中查询加密字符串数据的性能, 提出一种在索引特征值上创建B^*树聚簇索引的查询方法. 每一个待加密字符串数据对应一个索引特征值, 索引特征值以数值的形式保存在索引字段中. 查询时使用两阶段查询策略, 首先利用索引字段对加密数据进行一次粗糙查询过滤掉不相干的记录, 然后在返回的粗糙集合解密的基础上进行明文查询, 得到最终结果. 实验表明该方法较现有查询方法在查询性能有较大的提升.     

ALERT:基于Radix Tree的工作负载自适应学习型索引

学习型索引通过学习数据分布可以准确地预测数据存取的位置,在保持高效稳定的查询下,显著降低索引的内存占用.现有的学习型索引主要针对只读查询进行优化,而对插入和更新支持不足.针对上述挑战,设计了一种基于Radix Tree的工作负载自适应学习型索引ALERT.ALERT使用Radix Tree来管理不定长的分段,段内采用具有最大误差界的线性插值模型进行预测.同时,ALERT使用一种高效的插入缓冲来降低数据插入更新的代价.针对点查询和范围查询提出两种自适应重组优化方法,通过对工作负载进行感知,动态地调整插入缓冲的组织结构.经实验验证,ALERT与业界流行的学习型索引相比,构建时间平均降低了81%,内存占用平均降低了75%,在保持了优秀读性能的同时,使插入延迟平均降低了50%;此外,ALERT使用自适应重组优化能有效感知查询工作负载特征,与不使用自适应重组优化相比,查询延迟平均降低了15%.     

An index management using CHC-cluster for flash memory databases

Flash memories are one of the best media to support portable and desktop computers’ storage areas. Their features include non-volatility, low power consumption, and fast access time for read operations, features which are sufficient to present flash memories as major database storage components for portable computers. However, we need to improve traditional index management schemes based on B-Tree due to the relatively slow characteristics of flash memory operations compared to RAM memory. In order to achieve this goal, we propose a new index management scheme based on a compressed hot-cold clustering called CHC-Tree. The CHC-Tree-based index management scheme improves index operation performance by compressing the flash index nodes and clustering the hot-cold segments. The cold cluster compression techniques using unused free area in index node reduces the number of slow write operations in index node insert/delete processes. Our performance evaluation shows that our scheme significantly reduces the write operation overheads, improving the index update performance of B-Tree by 21.9%.     

结合近似最优比特分配的改进SPIHT算法

SPIHT算法是一种实用、高效的小波零树图像编码算法。针对SPIHT算法存储空间需求大、运算复杂度较高等缺点，提出了一种改进的快速、低存储SPIHT算法，该算法将小波变换所形成的水平、垂直、对角和低频4个子带分成4个处理单元，对每个处理单元分别进行量化编码，并在各单元之间采取近似最优比特分配以提高量化性能。实验结果表明，改进算法在提高峰值信噪比等性能指标的同时，有效地减少了算法的存储需求及运算时间。     

Fast Hardware Construction and Refitting of Quantized Bounding Volume Hierarchies

There is recent interest in GPU architectures designed to accelerate ray tracing, especially on mobile systems with limited memory bandwidth. A promising recent approach is to store and traverse Bounding Volume Hierarchies (BVHs), used to accelerate ray tracing, in low arithmetic precision. However, so far there is no research on refitting or construction of such compressed BVHs, which is necessary for any scenes with dynamic content. We find that in a hardware‐accelerated tree update, significant memory traffic and runtime savings are available from streaming, bottom‐up compression. Novel algorithmic techniques of modulo encoding and treelet‐based compression are proposed to reduce backtracking inherent in bottom‐up compression. Together, these techniques reduce backtracking to a small fraction. Compared to a separate top‐down compression pass, streaming bottom‐up compression with the proposed optimizations saves on average 42% of memory accesses for LBVH construction and 56% for refitting of compressed BVHs, over 16 test scenes. In architectural simulation, the proposed streaming compression reduces LBVH runtime by 20% compared to a single‐precision build, and 41% compared to a single‐precision build followed by top‐down compression. Since memory traffic dominates the energy cost of refitting and LBVH construction, energy consumption is expected to fall by a similar fraction.     

Improving energy efficiency for flash memory based embedded applications

The JFFS2 file system for flash memory compresses files before actually writing them into flash memory. Because of this, multimedia files, for instance, which are already compressed in the application level go through an unnecessary and time-consuming compression stage and cause energy waste. Also, when reading such multimedia files, the default use of disk cache results in unnecessary main memory access, hence an energy waste, due to the low cache hit ratio. This paper presents two techniques to reduce the energy consumption of the JFFS2 flash file system for power-aware applications. One is to avoid data compression selectively when writing files, and the other is to bypass the page caching when reading sequential files. The modified file system is implemented on a PDA running Linux and the experiment results show that the proposed mechanism effectively reduces the overall energy consumption when accessing continuous and large files.     

Low-complexity and energy efficient image compression scheme for wireless sensor networks

Currently most energy-constrained wireless sensor networks are designed with the object of minimizing the communication power at the cost of more computation. To achieve high compression efficiency, the main image compression algorithms used in wireless sensor networks are the high-complexity, state-of-the-art image compression standards, such as JPEG2000. These algorithms require complex hardware and make the energy consumption for computation comparable to communication energy dissipation. To reduce the hardware cost and the energy consumption of the sensor network, a low-complexity and energy efficient image compression scheme is proposed. The compression algorithm in the proposed scheme greatly lowers the computational complexity and reduces the required memory, while it still achieves required PSNR. The proposed implementation scheme of the image compression algorithm overcomes the computation and energy limitation of individual nodes by sharing the processing of tasks. And, it applies transmission range adjustment to save communication energy dissipation. Performance of the proposed scheme is investigated with respect to image quality and energy consumption. Simulation results show that it greatly prolongs the lifetime of the network under a specific image quality requirement.     

基于前缀扩展的快速路由查找算法

该文对路由器中的快速路由查找算法进行了研究。针对路由查找算法在查找速度、算法空间复杂度以及插入和删除表项的难度算方法存在的问题,提出了一种快速路由查找算法。该算法通过构造两级索引表结构来减小路由查找的访存次数以提高查找速度;利用前缀扩展的特性并采用特殊的数据结构来构建索引表,能支持动态插入、删除和更新路由;采用压缩技术对二级索引表进行压缩,从而大大减小了路由所需的存储空间。该算法最多四次访存,最少两次访存就完成一次路由查找。由于采用了压缩方法,所需存储空间很小,该算法不仅适合于软件实现,也适合于硬件实现。查找速度快、存储空间小并支持动态插入和删除是该算法的主要特点。     

Reducing the memory of compression Feedforward driving for a new LCD controller

Abstract— The authors have studied a method of reducing the frame memory for signal processing used to improve the response time of liquid crystals. Compared with cases in which quantization is used, the compression Feedforward driving method, which reduces frame memory by applying an image‐compression technique, can effectively reduce the frame‐memory size. The study revealed that errors decrease by 6–10 dB or so if the image data was reduced to 1/3 by means of image compression. Based on the results of the study, the authors have developed a second‐generation LCD controller. With just one SDRAM unit, this LCD controller can produce almost ideal processing effects.     

结合半波高斯量化与交替更新的神经网络压缩方法

为使神经网络模型能在实时性要求较高且内存容量受限的边缘设备上部署使用,提出一种基于半波高斯量化与交替更新的混合压缩方法。对神经网络模型输入部分进行2 bit均匀半波高斯量化,将量化值输入带有缩放因子的二值网络通过训练得到初始二值模型,利用交替更新方法对已训练的二值模型进行逐层微调以提高模型测试精度。在CIFAR-10和ImageNet数据集上的实验结果表明,该方法能有效降低参数和结构冗余所导致的内存和时间开销,在神经网络模型压缩比接近30的前提下,测试精度相比HWGQ-Net方法提高0.8和2.0个百分点且实现了10倍的训练加速。