一种基因数据的聚类并行算法研究

提出了一种基于密度的聚类并行算法,在APRAM模型的分布式存储系统中,通过欧几里德距离矩阵和密度函数两次时间复杂度为O(n2)的计算,可使聚类过程的时间复杂度变为O(n),以增加一次计算的代价来降低聚类过程的时间复杂度。基于8结点的机群计算实验表明本算法能够达到较同类算法更高的并行加速比,能提高高维生物数据的聚类速度。     

基于分层聚类的并行数据预处理算法

分层聚类技术在图像处理、入侵检测和生物信息学等方面有着极为重要的应用,是数据挖掘领域的研究热点之一。针对目前并行分层聚类算法处理大数据集时速度较慢的特点,提出一种并行数据预处理算法,该算法可使原始输入数据的规模最多减少为原来的1/10,从而可减少总的并行分层聚类时间。在测试数据集上的实验结果表明使用本算法进行预处理后,能显著减少分层聚类的运行时间。     

子集和问题的量子中间相遇搜索算法

子集和问题是NP完全问题,该问题是背包公钥的基础.现有最优的经典算法求解规模为n的子集和问题需要O(n2n/2)步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法,该算法可以在O(n2n/3)步求解规模为n的子集和问题,其存储复杂性为O(2n/3).由于NP完全问题可以在多项式时间内可相互归约,所以,在存储复杂性...     

基于并查集的低复杂度模糊聚类信号分选算法

随着雷达技术与电子技术的不断发展,电子对抗环境日趋复杂.为能够在复杂电子对抗环境中进行实时有效的信号分选,提出了一种基于并查集的低复杂度模糊聚类信号分选算法.通过计算两脉冲间相似度,以相似度高于阈值作为集合归并条件,依次完成集合归并后查询并查集完成聚类结果输出.通过结合并查集与模糊聚类分选算法,大大降低了模糊聚类分选算法的复杂度,本文所提算法时间复杂度为O(n2),空间复杂度为O(n).由于该算法具有低复杂度的特点,可应用于工程项目.     

基于邻域的迭代最优化聚类算法的设计与分析

迭代最优化算法是模式识别中一种重要方法.算法随机确定k个分类中心进行初始类划分,再通过逐步求精的方法进行合理分类.通过对迭代最优化算法的分析和研究,指出该算法存在样本选择的盲目性、易陷入局部极值、没有考虑样本的聚类趋势等缺点.文中根据样本的聚类趋势,结合邻域思想,设计了基于样本邻域概念的迭代最优化算法,并对算法的时间代价进行了定量分析.该算法总的时间代价为O(n),已应用于网络管理中的知识分类中,并取得了满意结果.     

一种改进的层次聚类算法

为了更好地实现聚类,在分析层次聚类(agglomerative)算法和神经网络的ART2算法的基础上,提出了一种改进的层次聚类算法.改进算法将首先采用一种基于ART2的改进神经网络聚类算法得到一个初始的聚类结果,然后在此基础上利用agglomerative算法实现分层聚类.实验结果表明,改进算法较原先传统的聚类算法,不但算法执行速度快、效率高,而且聚类效果也比较好.     

机群系统上基于映射和抽样划分的并行聚类算法

采用映射和抽样划分方法,基于MPI消息传递编程模式,在机群系统上设计与实现一种并行聚类算法.该算法将生物基因序列映射成整数值,采用整数值取代字符串进行聚类,使得聚类过程快速,通过多次抽样一次聚类寻找初值在一定程度上避免了聚类结果陷入局部解的问题,优化了聚类质量.在PC机群系统上对基因序列进行并行聚类的实验结果表明该算法获得了较好的加速和可扩展性.     

基于K-均值与AGNES聚类算法的校园网行为分析系统研究

校园网中的服务器存有海量的用户访问日志文件,记录了校园网用户的访问信息。鉴于此,提出了一种基于聚类算法的校园网用户行为分析技术,设计和实现了数据预处理系统,对日志数据进行一系列的清理、合并,标准化等预处理,使其更好地适应后续的聚类操作。将预处理后的数据作为输入数据,分别实现了三种常用的聚类算法对日志数据进行聚类,然后从聚类准确率和聚类速度两个角度对现有算法进行优化。为了提高聚类准确率,提出了用K-均值算法结合AGNES算法的方法;为了提高聚类速度,在MPICH2平台上设计和实现了并行K-均值算法,实现多机并行分析,最后简单介绍了校园网行为分析系统的应用。     

基于余弦相似性的自适应权重的改进FCM算法

模糊C-均值聚类算法(FCM)是一种经典的聚类算法,主要通过迭代更新隶属度和聚类中心来提高聚类的有效性.FCM算法的性能主要通过类内紧性和类间分离性来评价,但其既依赖于初始聚类中心,也对噪声非常敏感.考虑到每个数据点和每个聚类中心对目标函数的不同重要性,本文提出了一种具有自适应权重的改进FCM聚类算法(Hybrid FCM).主要贡献:将2个具有自适应指数p和q的自适应权向量ψ和φ引入FCM的目标函数,以体现不同数据点和聚类中心的重要性;为提高聚类性能,自适应指数p、q和模糊因子m采用粒子群优化算法(PSO)优化,新提出的聚类评价指标AWCVI作为PSO算法的适应度函数;迭代过程中利用余弦相似性对隶属度函数进行修正,提高算法的鲁棒性.实验表明,本文提出的算法能够有效地提高聚类效果.     

基于Spark框架和ASPSO的并行划分聚类算法

针对划分聚类算法处理海量的数据存在的数据离散系数较大与抗干扰性差、局部簇簇数难以确定、局部簇质心随机性及局部簇并行化合并效率低等问题,提出了一种基于Spark框架和粒子群优化自适应策略(ASPSO)的并行划分聚类(PDC-SFASPSO)算法.首先,提出了基于皮尔逊相关系数和方差的网格划分策略获取数据离散系数较小的网格...     

Memory Conflict Analysis and Implementation of a Re-configurable Interleaver Architecture Supporting Unified Parallel Turbo Decoding

This paper presents a novel hardware interleaver architecture for unified parallel turbo decoding. The architecture is fully re-configurable among multiple standards like HSPA Evolution, DVB-SH, 3GPP-LTE and WiMAX. Turbo codes being widely used for error correction in today’s consumer electronics are prone to introduce higher latency due to bigger block sizes and multiple iterations. Many parallel turbo decoding architectures have recently been proposed to enhance the channel throughput but the interleaving algorithms used in different standards do not freely allow using them due to higher percentage of memory conflicts. The architecture presented in this paper provides a re-configurable platform for implementing the parallel interleavers for different standards by managing the conflicts involved in each. The memory conflicts are managed by applying different approaches like stream misalignment, memory division and use of small FIFO buffer. The proposed flexible architecture is low cost and consumes 0.085 mm² area in 65 nm CMOS process. It can implement up to 8 parallel interleavers and can operate at a frequency of 200 MHz, thus providing significant support to higher throughput systems based on parallel SISO processors.     

A parallel algorithm for time-slot assignment problems in TDMhierarchical switching systems

The paper presents a parallel algorithm for time-slot assignment problems in TDM hierarchical switching systems, based on the neural network model. The TDM systems are operated in repetitive frames composed of several time-slots. A time-slot represents a switching configuration where one packet is transmitted through an I/O line. The goal of the algorithm is to find conflict-free time-slot assignments for given switching demands. The algorithm runs on a maximum of n²×m processors for m-time-slot problems in n×n TDM systems. In small problems up to a 24×24 TDM system, the algorithm can find the optimum solution in a nearly constant time, when it is performed on n²×m processors     

A Hardware Architecture for the LZW Compression and Decompression Algorithms Based on Parallel Dictionaries

In this paper, a parallel dictionary based LZW algorithm called PDLZW algorithm and its hardware architecture for compression and decompression processors are proposed. In this architecture, instead of using a unique fixed-word-width dictionary a hierarchical variable-word-width dictionary set containing several dictionaries of small address space and increasing word widths is used for both compression and decompression algorithms. The results show that the new architecture not only can be easily implemented in VLSI technology because of its high regularity but also has faster compression and decompression rate since it no longer needs to search the dictionary recursively as the conventional implementations do.     

Parallel Algorithms Based on the Temporal-Window Method for Non-Alternating 3D-WT over Angiographies Using a Multicomputer

In this paper, we introduce and evaluate the parallel implementations of two video sequences decorrelation algorithms having been developed based on the non-alternating three-dimensional wavelet transform (3D-WT) and the temporal-window method. The proposed algorithms have been proven to outperform the classic 3D-WT algorithm in terms of a better coding efficiency and lower computational requirements while enabling a lossless coding and a top-quality reconstruction: the two most highly relevant features to medical imaging applications. The parallel implementations of the algorithms are developed and tested on a shared memory system, a SGI Origin 3800 supercomputer, making use of a message-passing paradigm. We evaluate and analyze the performance of the implementations in terms of the response time and speed-up factor by varying the number of processors and various video coding parameters. The key point enabling the development of highly efficient implementations rely on a workload distribution strategy supplemented by the use of parallel I/O primitives, for better exploiting the inherent features of the application and computing platform. Two sets of I/O primitives are tested and evaluated: the ones provided by the C compiler and the ones belonging to the MPI/IO library.     

A sorter-based architecture for a parallel implementation of communication intensive algorithms

This paper deals with the parallel execution of algorithms with global and/or irregular data dependencies on a regularly and locally connected processor array. The associated communication problems are solved by the use of a two-dimensional sorting algorithm. The proposed architecture, which is based on a two-dimensional sorting network, offers a high degree of flexibility and allows an efficient mapping of many irregularly structured algorithms. In this architecture a one-dimensional processor array performs all required control and arithmetic operations, whereas the sorter solves complex data transfer problems. The storage capability of the sorting network is also used as memory for data elements. The algorithms for sparse matrix computations, fast Fourier transformation and for the convex hull problem, which are mapped onto this architecture, as well as the simulation of a shared-memory computer show that the utilization of the most complex components, the processors, is O(1).     

Multimedia Signal Processors: An Architectural Platform with Algorithmic Compilation

Novel algorithmic features of multimedia applications and advances in VLSI technologies are driving forces behind the new multimedia signal processors. We propose an architecture platform which could provide high performance and flexibility, and would require less external I/O and memory access. It is comprised of array processors to be used as the hardware accelerator and RISC cores to be used as the basis of the programmable processor. It is a hierarchical and scalable architecture style which facilitates the hardware-software codesign of multimedia signal processing circuits and systems. While some control-intensive functions can be implemented using programmable CPUs, other computation-intensive functions can rely on hardware accelerators.To compile multimedia algorithms, we also present an operation placement and scheduling scheme suitable for the proposed architectural platform. Our scheme addresses data reusability and exploits local communication in order to avoid the memory/communication bandwidth bottleneck, which leads to faster program execution. Our method shows a promising performance: a linear speed-up of 16 times can be achieved for the block-matching motion estimation algorithm and the true motion tracking algorithm, which have formed many multimedia applications (e.g., MPEG-2 and MPEG-4).     

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models

For pt. I see ibid., vol.46, p.755-88 (2000). The concept of context-free grammar (CFG)-based coding is extended to the case of countable-context models, yielding context-dependent grammar (CDG)-based coding. Given a countable-context model, a greedy CDG transform is proposed. Based on this greedy CDG transform, two universal lossless data compression algorithms, an improved sequential context-dependent algorithm and a hierarchical context-dependent algorithm, are then developed. It is shown that these algorithms are all universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet. Moreover, it is proved that these algorithms' worst case redundancies among all individual sequences of length n from a finite alphabet are upper-bounded by d log log n/log n, as long as the number of distinct contexts grows with the sequence length n in the order of O(n/sup a/), where 0 < /spl alpha/ < 1 and d are positive constants. It is further shown that for some nonstationary sources, the proposed context-dependent algorithms can achieve better expected redundancies than any existing CFG-based codes, including the Lempel-Ziv (1978) algorithm, the multilevel pattern matching algorithm, and the context-free algorithms in Part I of this series of papers.     

Efficient algorithms for k-out-of-n andconsecutive-weighted-k-out-of-n:F system

A new reliability model, consecutive-weighted-k-out-of-n:F system, is proposed and an O(n) algorithm is provided to evaluate its reliability. An O(n·min(n,k)) algorithm is also presented for the circular case of this model. The authors design an O(n) parallel algorithm using k processors to compute the reliability of k-out-of-n systems, that achieves linear speedup     

Seismic migration algorithms on parallel computers

The authors study seismic migration algorithms with the aim of presenting a general framework for analyzing such algorithms, and propose some medium-grained paradigms for computation on parallel computers. They introduce parallel models for computation and discuss techniques to optimize the performance of the models on distributed concurrently executing processors. The computational and communication requirements of the algorithms are discussed and diverse optimization techniques are proposed. The memory limitation, I/O (input/output) bottleneck, and computational tradeoffs on hypercube multiprocessors are analyzed