一种基于信息分散算法的分布式数据存储方案

针对分布式数据存储方案中,基于复制的方法和基于秘密共享的方法存在存储开销过大的问题,提出了分布式系统中一种基于IDA码的客户-服务器工作模式的数据存储方案。该方案在数据写入过程中通过构造编码后数据分块的Hash值级连,即所谓的数字指纹,可实现Byzantine环境数据的完整性保护。     

A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

改进的线性局部切空间排列算法

线性局部切空间排列算法（LLTSA）是一种能很好的适用于识别问题的非线性降维方法,但LLTSA仅仅关注了数据的局部几何结构,而没有体现数据的整体信息。本文提出了一种基于主成分分析（PCA）改进的线性局部切空间排列算法（P-LLTSA）,该算法在Linear-LTSA的基础上,考虑了样本的全局结构,进而得到更好的降维效果。在经典的三维流形和在MNIST图像库手写体识别的实验中,识别率较PCA、LPP,LLTSA有明显提高,证实了该算法在识别问题中的有效性。     

一种◢k◣-ary搜索树的快速求交算法

k-ary搜索树因其对高速缓存和SIMD并行指令集天然的适配性,正在受到越来越多的关注和研究.近年来,它被成功地应用于搜索引擎倒排索引结构中,用于实现高效的查询处理和索引压缩.但基于k-ary搜索树的查询处理算法目前仍处在一种相对简单基础的应用程度,效率提升有限;而且查询算法仅限于元素搜索,大大限制了其适用范围.基于上述观察,研究了基于k-ary搜索树的求交算法,并提出了两种优化技术用于压缩搜索范围以提升查询效率.实验证明,结合不同的遍历方式,优化后的求交算法可以极大地提高查询速度,尤其是针对存储海量数据的长倒排链,配合更大的SIMD寄存器,k-ary搜索树相比于传统求交算法的优势更为明显.     

基于P2P的结构化数据存储索引算法设计

通过把数据标识和数据索引分别进行组划分后映射到节点组上,然后把树节点的索引重新分布和同步构造PB—link树。应用lazy update和active update两种节点合并、分裂策略,对连续有序数据进行索引,结果比DB—link树具有显著优势,更适应于P2P结构化数据存储环境。     

A systolic algorithm for solving dense linear systems

For an arbitrary n × n matrix A and an n × 1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax = b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 ≤ i ≤ n, the i^th linear array is responsible to eliminate the i^th unknown variable x_i of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover, this algorithm can detect whether A is singular or not.     

基于K 2树的大图存储优化研究*

针对大图数据的一种表达方法——K2树,提出了相应的压缩优化算法。该算法利用带有启发式规则的DFS编码对图中所有节点进行重新编码,并通过自适应调整参数K,使得K2树能够充分利用网络中的社团结构特性,从而降低空间代价。给出了K2树的优化算法描述,并针对一系列真实网络和模拟网络进行了实验,验证了优化算法具有较好的压缩效果。     

基于图的机械系统拓扑结构的数据存储

应用图论的概念和建模理论,分析了机械系统机构图和拓扑结构图的关系,提出了一种新的基于图的机械系统拓扑结构的数据存储模型.该存储模型不仅解决了复杂多体系统的存储结构问题,避免了非树形多体向树形多体的切除转换,而且使树形多体系统和非树形多体系统从数学建模到数据存储达到高度一致.     

分段线性系统最优控制设计的一种混合算法

将分段线性系统的最优控制设计问题转化成以反馈增益为寻优参数，以最优控制性能上界为目标的一组双线性矩阵不等式(BMI)问题．将遗传算法与内点法相结合设计出一种混合算法，对BMI问题进行求解．算例仿真表明该算法是简便而有效的．     

A parallel algorithm solving a tridiagonal Toeplitz linear system

A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).     

A note on a linear time algorithm for constructing adjacency graphs of 3D FEA data

In this paper, we present an algorithm for constructing adjacency graphs of 3D finite element analysis (FEA) data. Adjacency graphs are created to represent the connectivities of FEA data cells. They are used in most visualization methods for FEA data. We stress that in many engineering applications FEA data sets do not contain the adjacency information. This is opposite to computer-aided geometric design where, e.g., the winged edge geometrical representation is usually generated and utilized. By establishing intermediate data structures and using bin-sorting, we developed an efficient algorithm for constructing such graphs. The total time complexity of the algorithm is linear in the number of data cells.     

High TPO/TCO for data storage:policy,algorithm and early practice

Today, the data storage industry faces a rapidly growing volume of data. Adding more primary disk capacity to manage data growth is a costly and non-sustainable strategy. Before investing in new capacity, data managers should rationalize their existing storage infrastructure to maximize the use of existing capacity. There is a growing need for achieving a high ratio of Total Performance of Ownership (TPO) to Total Cost of Ownership (TCO), or TPO/TCO. The storage infrastructure can be made more efficient by assessing data usages, eliminating unnecessary data copies, moving less critical data to less expensive disk devices and repurposing allocated but unused capacity. Optimizing existing storage assets can reduce storage costs by delaying or eliminating the need for new primary capacity to manage information growth. In this paper, we apply the notion of information lifecycle management (ILM) to achieve the above improved efficiencies and optimizations. By balancing data value and storage requirements, we aim to reduce the storage system’s dependence on expensive high-performance disk devices and lower its cost per online gigabyte, thus resulting in a higher TPO/TCO.     

图压缩存储格式的核排序重边匹配算法

将图核概念引入到多水平方法粗化阶段,针对图的压缩存储格式提出了核排序重边匹配（CSHEM）算法。该算法借助图核的全局信息,改进了以往仅仅利用结点的度等局部信息进行匹配的粗化算法,在对原始图粗化过程中发挥结点核值导向性作用,克服以往只能选择随机匹配（RM）算法作为导向匹配算法的缺陷;提出了基于CSHEM和重边匹配（HEM）算法的组合粗化策略,在发挥结点核值的导向性作用的同时,又不至于被过分强调而使粗化图违背结点核值大小均匀分布的原则。基于ISPD98电路测试基准的实验和分析表明,相比无向图剖分软件MeTiS采用的RM和HEM算法的组合粗化策略,提出的策略取得了一定性能的改进。     

蚁群算法求解连续空间优化问题

借鉴蚁群算法的进化思想，提出一种求解连续空问优化问题的蚁群算法。该算法主要包括全局搜索、局部搜索和信息素强度更新规则。在全舄搜索过程中，利用信息素强度和启发式函数确定蚂蚁移动方向。在局部搜索过程中，嵌入了确定性搜索，以改善寻优性能，加快收敛速率。通过一个实例问题的求解表明了该算法的有效性。     

高效的带状线性方程组分布式并行算法

提出了一种新的带状线性方程组的分布式并行算法(New Distributed Parallel Algorithm for Banded Linear Equations,简称为NDPAB算法)。当带状线性方程组的系数矩阵满足对角占优时,算法在运行过程中不会中断,算法的加速比接近于处理器数目。给出了基于局域网的MPI异构环境下数值实验结果,数值实验结果表明算法是高效的。     

传感器输出特征线性化的稳健算法

利用最小一乘估计的稳健性 ,给出了传感器输出特征线性化的特征直线的稳健估计。该方法在稳健性方面明显优于最小二乘估计 ,更有效地刻划了传感性输出特征的本质     

分布式存储系统的哈希算法研究

针对分布式存储系统中如何实现数据在物理存储上的均匀分布和高效定位的问题,对多种哈希算法展开研究,提出了衡量分布式存储系统哈希算法优劣的标准;从散列分布性、哈希冲突和计算效率等多个维度对这些哈希算法进行分析比较,指出各种哈希算法的应用场景;结合分布式存储系统的应用,给出最优的哈希算法选择。实验结果证明,Davies-Meyer算法具有很好的均匀分布性和很高的计算效率,很适合分布式存储系统的应用。     

多维数据的Z-Ordering存储映射算法及其缓存调度优化

多维数据以线性形式在存储系统中进行访问操作,二维及以上维度空间中的相邻节点被不同的映射算法映射到一维空间的不相邻位置。高维空间中进行相邻节点访问时,其一维存储映射位置有着不同的访问距离和访问延迟。提出了基于空间填充曲线Z-Ordering的存储映射方法及其访问距离的度量指标,并和常规优先算法进行了对比,发现能更好地将高维相邻的数据节点簇集到一维存储位置,加强了局部性。调整缓存空间中用于预取的空间大小,可以利用增强的局部性,提高了缓存命中率。实验结果表明,改善了多维数据的访问速度,优化了系统性能。