A fast MATLAB program to estimate the multifractal spectrum of multidimensional data: Application to fractures

A MATLAB^® program based on the Hou algorithm for estimation of fractal dimension and multifractal spectrum of fractures is presented. The program performance was tested with many synthetical fractals and field data. Interpolation and sampling effects on the fractal dimension and multifractal spectrum estimation were also studied. Some common problems related to the fractal dimension and multifractal spectrum are also discussed.     

Complexity and design of QoS routing algorithms in wireless mesh networks

Quality of service (QoS) provisioning in wireless mesh networks (WMNs) is an open issue to support emerging multimedia services. In this paper, we study the problem of QoS provisioning in terms of end-to-end bandwidth allocation in WMNs. It is challenging due to interferences in the networks. We consider widely used interference models and show that except a few special cases, the problem of finding a feasible path is NP-complete under the models. We propose a k-shortest path based algorithmic framework to solve this problem. We also consider the problem of optimizing network performance by on-line dynamic routing, and adapt commonly used conventional QoS routing metrics to be used in WMNs. We find the optimal solutions for these problems through formulating them as optimization models. A model is developed to check the existence of a feasible path and another to find the optimal path for a demand; moreover, an on-line optimal QoS routing algorithm is developed. Comparing the algorithms implemented by the proposed framework with the optimization models shows that our solution can find existing feasible paths with high probability, efficiently optimizes path lengths, and has a comparable performance to the optimal QoS routing algorithm. Furthermore, our results show that contrary to wireline networks, minimizing resource consumption should be preferred over load distribution even in lightly loaded WMNs.     

Flash memory efficient LTL model checking

As the capacity and speed of flash memories in form of solid state disks grow, they are becoming a practical alternative for standard magnetic drives. Currently, most solid-state disks are based on NAND technology and much faster than magnetic disks in random reads, while in random writes they are generally not.So far, large-scale LTL model checking algorithms have been designed to employ external memory optimized for magnetic disks. We propose algorithms optimized for flash memory access. In contrast to approaches relying on the delayed detection of duplicate states, in this work, we design and exploit appropriate hash functions to re-invent immediate duplicate detection.For flash memory efficient on-the-fly LTL model checking, which aims at finding any counter-example to the specified LTL property, we study hash functions adapted to the two-level hierarchy of RAM and flash memory. For flash memory efficient off-line LTL model checking, which aims at generating a minimal counterexample and scans the entire state space at least once, we analyze the effect of outsourcing a memory-based perfect hash function from RAM to flash memory.Since the characteristics of flash memories are different to magnetic hard disks, the existing I/O complexity model is no longer sufficient. Therefore, we provide an extended model for the computation of the I/O complexity adapted to flash memories that has a better fit to the observed behavior of our algorithms.     

Extending ?-diversity to generalize sensitive data

Generalization is an important technique for protecting privacy in data dissemination. In the framework of generalization, ?-diversity is a strong notion of privacy. However, since existing ?-diversity measures are defined in terms of the most specific (rather than general) sensitive attribute (SA) values, algorithms based on these measures can have narrow eligible ranges for data that has a heavily skewed distribution of SA values and produce anonymous data that has a low utility. In this paper, we propose a new ?-diversity measure called the functional (τ, ?)-diversity, which extends ?-diversity by using a simple function to constrain frequencies of base SA values that are induced by general SA values. As a result, algorithms based on (τ, ?)-diversity may generalize SA values, thus are much less constrained by skew SA distributions. We show that (τ, ?)-diversity is more flexible and elaborate than existing ?-diversity measures. We present an efficient heuristic algorithm that uses a novel order of quasi-identifier (QI) values to achieve (τ, ?)-diversity. We compare our algorithm with two state-of-the-art algorithms that are based on existing ?-diversity measures. Our preliminary experimental results indicate that our algorithm not only provides a stronger privacy protection but also results in better utility of anonymous data.     

An algorithmic framework for network reconstruction

Models of biological systems and phenomena are of high scientific interest and practical relevance, but not always easy to obtain due to their inherent complexity. To gain the required insight, experimental data are provided and need to be interpreted in terms of models that explain the observed phenomena. In systems biology the framework of Petri nets is often used to describe models for the regulatory mechanisms of biological systems. The aim of this paper is to provide, based on results in Marwan et al. (2008) [1] and Durzinsky et al. (2008) [2], an algorithmic framework for the challenging task of generating all possible Petri nets fitting the given experimental data.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

有线数字广播中高阶QAM信号的载波同步与均衡器设计

针对ITU-T J.83标准,结合有线数字广播的信道特征,提出一种适用于高阶QAM信号的载波同步与自适应均衡的联合设计方案。该方案在均衡部分采用常模数算法(CMA)和最小均方误差算法(LMS)的双模均衡算法。通过算法的切换达到快速收敛和降低均方误差(MSE)的目的;针对高阶QAM信号,载波同步环路首先选用极性判决算法,并采用带宽较大的环路滤波器系数,使环路能在短时间内进行大范围频偏捕获。然后调低环路滤波器系数,减小环路带宽,进而降低稳态抖动。环路最后切换到判决指示算法,使相位均方差降至最低。整个方案通过算法验证并在Altera Stratix Ⅱ系列EP2S130F1020C5型现场可编程门阵列(FPGA)上完成了布局布线。最高工作频率为90.47MHz。     

基于编织算法的复线高速磁浮列车运行图铺画方法

根据高速磁浮线路结构和运行控制系统的特点,建立了复线高速磁浮列车运行图编制模型,设计了编织算法对模型进行求解。该算法严格按照列车在各车站的发车时间顺序,对上、下行列车运行线如同“织毛衣”般交叉铺画,在遇到列车冲突时通过更改列车路由和增加发车间隔等方法予以及时化解,逐步得到整体优化的列车运行图。算例分析表明,该方法优化速度快,能够有效地进行高速磁浮列车运行图的铺画。     

面向数据挖掘的时间序列聚类方法研究

一、引言自然界以及我们社会生活中的各种事物都在运动、变化和发展着,将它们按时间顺序记录下来,我们就可以得到各种各样的“时间序列”数据。对时间序列进行分析,可以揭示事物运动、变化和发展的内在规律,对于人们正确认识事物并据此作出科学的决策具有重要的现实意义。     

一种改进的无死锁试卷生成算法

1.引言作为计算机远程教育(网上教育)中一个必不可少的组成部分,教学评价系统(即考试系统)设计成败的关键在于网络环境下的题库管理系统的设计,这一设计主要应考虑以下几方面的问题: (1)多卷并发试卷的时间冲突。一方面,由于网络用户数目的事先不确定性和题库中试题总量有限,可能产生多份试卷争夺试题资源的现象,从而形成时间