一种可扩展的XPath查询最小化算法框架

XPath是XML的基本查询语言,XPath查询最小化对于提高XML数据库的查询性能具有重要意义.但是,由于XPath查询最小化是一个coNP完备问题,大部分已有的算法局限于处理简单的XPath片段.本文从一个新的角度入手,综合考虑完备性和高效性,提出了一个新的查询最小化框架,与已有算法"面向结点",即逐个删除冗余结点的解决思路不同,本文提出"面向树模式"的方式,即通过计算树模式的自同态映射,寻找目标结点集最小的自同态映射,进而求解最小等价查询树的方法.该方法具有较高的效率,而且在--Z..情况下是完备的,尤其是可以进一步扩展到更复杂的XPath片段.本文以此框架为基础,给出一个可以计算复杂查询模式的算法.     

集合多覆盖问题的乘性权重更新分析

集合多覆盖问题的简单贪心算法的近似比是lnn＋1。本文提出简单贪心算法的一个变形，宽度优先贪心算法，并且证明其有近似比（lnn）／r＋lnlnn＋O（1），其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O（（lnn）/r＋√（lnn）＋1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。关键词集合多覆盖，宽度优先贪心算法，乘性权重更新方法     

K-median问题贪心近似算法的分析与实验

讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法,证明该算法的近似度为O(ln(n/k)),通过实验证明该贪心算法在实际应用当中可以取得较好的效果,大约有90%的客户能被距离其最近、次近和第三近的设备服务。     

无线网络干扰最小化问题的一种缩边贪心算法

无线传感器网络的最大干扰最小化问题可以被描述为已知平面上◢n◣个点的位置及发射半径的阈值,要求设置发射半径使得任意点被其他点发射范围覆盖的最大数量达到最小。为了有效求解该问题,提出了一种新的贪心算法——缩边算法。不同于已有算法的构图方式,该算法是通过采取缩边的方式构造网络通信拓扑图,并结合了操作系统中批量处理的思想对贪心算法进行了加速,缩短了算法的运行时间。通过实验验证,该算法相比于已有算法在随机产生的算例上能产生更优的解。     

基于贪心策略的多信道数据广播调度算法

为减少多信道数据广播环境中的多信道平均延迟时间,提出一种基于贪心策略的多信道数据广播调度算法,将数据项合理地分配到各信道,最小化多信道数据项平均访问时间,在每个信道内采用近似最优的Log-time算法。实验结果表明,在不同的系统环境下,该算法都能够达到近似最优的性能。     

面向内部威胁的最优安全策略算法研究

内部攻击行为具有很强的伪装性,这使得检测结果具有不确定性.攻击图模型经常用于描述攻击行为的多个攻击步骤之间的因果关系,但在计算最优安全策略时,很少考虑到当前观测事件所具有的不确定性,也没有从概率的角度刻画安全防护策略实施后对攻击成功概率带来的影响.在前人的概率攻击图模型研究基础上,首次提出了一种面向内部威胁的安全防护策略概率攻击图(measures probablitity attack graph,MPAG)模型,在该模型中较为完备地讨论了内部攻击的3类不确定性,并引入安全防护措施节点及其对攻击成功的概率影响.在该模型基础上,最优安全防护策略计算被证明是一个NP难问题,一种贪心算法被提出解决该问题,该算法能在多项式时间内动态计算近似最优安全防护策略集合.最后给出一个真实的内部威胁网络环境的概率攻击图实例,说明该模型及相应的贪心算法能根据当前观测事件及其置信概率,计算满足一定代价限制条件的近似最优安全防护策略集合.     

Multi-Radio无线传感器网络中基于缓存和信道切换的数据查询算法的研究

针对Multi-Radio Multi-Channel传感器网络中链路服务质量和信道冲突等问题,提出并证明了基于缓存和信道切换的数据查询问题是一个NP完全问题.根据数据流守恒和链路-信道等约束条件,建立线性规划方程,得到该问题的最优解模型,并提出了一个多项式时间的近似算法——贪心新覆盖数据算法.该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延,再贪心选择其具有最小路径时延的缓存节点,收集其新覆盖数据.理论分析和实验结果表明,提出的方案能有效地减少数据收集时延,提高数据查询效率.     

MANET中基于缓存的移动数据查询处理算法的研究

针对MANET环境中带宽有限、能量有限、存储有限和链路频繁的断接性等特点,提出了基于缓存的移动数据查询问题,证明该问题是NP完全问题,并给出一个多项式时间的近似算法,即最大节点新覆盖数据算法MD.该算法采用贪心策略,查询新覆盖数据量最大的节点,减少了查询次数,并最大限度地减少了网络中的传输时延.然后在MD算法的基础上,同时考虑了节点新覆盖数据量和链路服务质量问题,提出了一种改进的高效的启发式算法,即基于最大节点DD值的算法MDD,有效地减少了能量消耗,最小化数据传输时延,提高了网络的吞吐量.理论分析及实验结果表明提出的数据查询算法能够充分利用缓存节点的数据信息,较好地完成数据查询工作,有效地减少数据收集时延,提高查询效率.     

NFV 中的 vDPI 功能放置问题研究

网络功能虚拟化 (NFV) 是视频流应用的重要技术。在视频流使用场景下,已有的工作研究 NFV 网络中的虚拟深度包检测 (vDPI) 放置问题时,仅考虑减少 vDPI 放置的数量,但没有考虑放置 vDPI 功能带来的 NFV 网络性能稳定性问题。针对上述不足,本文在减小 vDPI 放置数量的基础上,考虑提高网络稳定性,提出了一个多目标线性整数规划模型,并设计了一种贪心近似放置算法。该算法在 NFV 中放置 vDPI 功能时,可以降低 vDPI 放置数量、减少流量经过的平均网络跳数、降低传输时延、保证网络性能的稳定性。本文采用 Lingo 求出数学模型的最优解,并用贪心近似放置算法进行实验,对比算法实验结果与模型所求最优解可知：所提算法正确性较高,有较好的时间复杂度,适用于不同规模的 NFV 网络。     

基于网格网络的十字仲裁集互斥算法

分布式互斥是网格分布式系统的重要问题.根据网格系统的特点,提出了新型的分布式互斥算法.该算法基于网格网络的行列生成分布式互斥十字仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines

A crucial problem that needs to be solved is the allocation of memory to processors in a pipeline. Ideally, the processor memories should be totally separate (i.e., one-port memories) in order to minimize contention; however, this minimizes memory sharing. Idealized sharing occurs by using a single shared memory for all processors but this maximizes contention. Instead, in this paper we show that perfect memory sharing of shared memory can be achieved with a collection of two-port memories, as long as the number of processors is less than the number of memories. We show that the problem of allocation is NP-complete in general, but has a fast approximation algorithm that comes within a factor of asymptotically. The proof utilizes a new bin packing model, which is interesting in its own right. Further, for important special cases that arise in practice a more sophisticated modification of this approximation algorithm is in fact optimal. We also discuss the online memory allocation problem and present fast online algorithms that provide good memory utilization while allowing fast updates.     

ISD2500系列语音芯片在报警系统中的应用

介绍了ISD2500系列语音芯片工作原理及其在报警系统中的应用,同时给出了语音段落组合播放方法和语音复制电路的设计;由于ISD系列语音芯片是采用模拟方式来存储语音信息,因而语音信息的复制较为困难;针对此问题,给出了在语音段落起始地址已知和未知的情况下,运用连续寻址模式来实现语音信息复制的方法;经实践证明该方法简便可靠,达到了较为理想的复制效果.     

Approximating Latin Square Extensions

In this paper we investigate the problem of computing the maximum number of entries which can be added to a partially filled latin square. The decision version of this question is known to be NP-complete. We present two approximation algorithms for the optimization version of this question. We first prove that the greedy algorithm achieves a factor of 1/3. We then use insights derived from the linear relaxation of an integer program to obtain an algorithm based on matchings that achieves a better performance guarantee of 1/2. These are the first known polynomial-time approximation algorithms for the latin square completion problem that achieve nontrivial worst-case performance guarantees. Our study is motivated by applications to lightpath assignment and switch configuration in wavelength routed multihop optical networks. Received September 25, 1997; revised February 16, 1998.     

Multi-objective Reinforcement Learning for Responsive Grids

Grids organize resource sharing, a fundamental requirement of large scientific collaborations. Seamless integration of Grids into everyday use requires responsiveness, which can be provided by elastic Clouds, in the Infrastructure as a Service (IaaS) paradigm. This paper proposes a model-free resource provisioning strategy supporting both requirements. Provisioning is modeled as a continuous action-state space, multi-objective reinforcement learning (RL) problem, under realistic hypotheses; simple utility functions capture the high level goals of users, administrators, and shareholders. The model-free approach falls under the general program of autonomic computing, where the incremental learning of the value function associated with the RL model provides the so-called feedback loop. The RL model includes an approximation of the value function through an Echo State Network. Experimental validation on a real data-set from the EGEE Grid shows that introducing a moderate level of elasticity is critical to ensure a high level of user satisfaction.     

Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem

The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l · r_e, where r_e is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively.     

Broadcasting in Heterogeneous Networks

In this paper we study a well-known broadcasting heuristic for heterogeneous networks of workstations, called fastest node first. We show that this heuristic produces an optimal solution for minimizing the sum of all completion times and, in addition, produces a 1.5 approximation for the problem of minimizing the maximum completion time. We also develop a polynomial-time approximation scheme for this problem. We extend these results to show that the same bounds can be obtained for the multicast operation on such heterogeneous networks. In addition we show that the problem of minimizing the maximum completion time is NP-hard, which settles the complexity of this open problem.     

Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations

This paper considers machine scheduling that integrates machine deterioration caused by jobs and, consequently, maintenance activities. The maintenance state of the machine is represented by a maintenance level which drops by a certain, possibly job-dependent amount while jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Hence, maintenance activities that raise the maintenance level may become necessary and have to be scheduled additionally. We consider the objective to minimize the makespan throughout the paper. For the single machine case, we provide a linear-time approximation algorithm with worst-case a bound of 5/4, and comment on how an FPTAS from previous literature can be employed to apply to our problem. Due to problem similarity, these results also apply to the minimum subset sum problem, and the 5/4 linear-time approximation algorithm is an improvement over the 5/4 quadratic-time approximation algorithm of Güntzer and Jungnickel. For the general problem with multiple machines, we provide approximability results, two fast heuristics, an approximation algorithm with an instance-dependent approximation factor and a computational study evaluating the heuristics.     

Preemptive stochastic online scheduling on two uniform machines

This paper addresses a stochastic online scheduling problem in which a set of independent jobs are to be processed by two uniform machines whose speeds are 1 and s(s?1). Each job has a processing time, which is a random variable with an arbitrary distribution, and all the jobs are arriving overtime, which means that no information of the job is known in advance before its arrival. During the processing, jobs are allowed to be preempted and resumed later. The objective is to minimize the sum of expected weighted completion times. In this paper, the optimal policy, named SMPR, is designed for the single-machine preemptive stochastic scheduling problem where jobs have a common arriving time. Based on SMPR, the online approximative policy-UMPR, is devised for the preemptive stochastic online scheduling on two uniform machines. Then, UMPR is proved to have an approximation factor of 2. Furthermore, it is concluded that UMPR could not have a smaller approximation factor than 2, which means 2 is the approximation ratio of UMPR for the two-uniform-machine scheduling problem.     

基于任务复制的网格任务调度算法

网格中资源之间存在着通信延迟，通过任务复制的冗余，可以减少任务之间的通信开销，缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的；而基于任务复制调度算法往往会产生过多的复制任务，增大系统开销，甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题，因此本文提出了一种基于任务复制的网格资源调度算法，以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。     

基于Blakley方案的音频水印分存算法

提出了一种基于Blakley密钥共享方案的音频水印分存算法。算法将密钥分存的思想引入到音频水印算法中,将水印分存到音频数据的不同段中,检测时只需提取出部分水印信息就可以恢复出原始水印。算法同时采用了Bark码来解决剪切攻击带来的同步问题,并利用逼近信号统计特征和纠错码技术来提高算法的鲁棒性。实验证明,算法具有较强的抗剪切攻击能力。