Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n ²) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Ω(n ²) entries of this matrix, no better bounds are possible for this class of algorithms. This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented at the 41st Annual Symp. on Foundations of Computer Science, 2000.     

Dynamic Matrix Rank with Partial Lookahead

We consider the problem of maintaining information about the rank of a matrix M under changes to its entries. For an n×n matrix M, we show an amortized upper bound of O(n ^ω?1) arithmetic operations per change for this problem, where ω<2.373 is the exponent for matrix multiplication, under the assumption that there is a lookahead of up to Θ(n) locations. That is, we know up to the next Θ(n) locations (i ₁,j ₁),(i ₂,j ₂),…?, whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner. The dynamic matrix rank problem was first studied by Frandsen and Frandsen who showed an upper bound of O(n ^1.575) and a lower bound of Ω(n) for this problem and later Sankowski showed an upper bound of O(n ^1.495) for this problem when allowing randomization and a small probability of error. These algorithms do not assume any lookahead. For the dynamic matrix rank problem with lookahead, Sankowski and Mucha showed a randomized algorithm (with a small probability of error) that is more efficient than these algorithms.     

传递闭包聚类中的模糊性分析

传递闭包聚类是根据其相似矩阵的传递闭包生成一个聚类图(模式空间的若干个精确划分),聚类过程的模糊性主要体现在相似矩阵上,并可以通过模糊信息熵函数度量。聚类过程中模糊性的大小是衡量聚类效果好坏的一个重要指标。降低聚类的模糊性,有利于最终的决策(指定一个精确的划分)。论文引入了交叉熵的概念,通过学习权重,极小化交叉熵,可以有效地降低聚类的模糊性。     

On Certificates and Lookahead in Dynamic Graph Problems

Recent work in dynamic graph algorithms has led to efficient algorithms for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versions of fundamental directed graph problems like strong connectivity and transitive closure, as well as some undirected graph problems such as maximum matchings and cuts. We provide some explanation for this lack of success by presenting quadratic lower bounds on the certificate complexity of the seemingly difficult problems, in contrast to the known linear certificate complexity for the problems which have efficient dynamic algorithms. In many applications of dynamic (di)graph problems, a certain form of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases. These give rise to dynamic strong connectivity and dynamic transitive closure problems, respectively. We explain why it is reasonable, and indeed natural and desirable, to assume that lookahead is available in these two applications. Exploiting lookahead to circumvent their inherent complexity, we obtain efficient dynamic algorithms for strong connectivity and transitive closure. Received August 11, 1995; revised August 23, 1996.     

基于求传递闭包的Warshall算法的改进

围绕传递闭包分析比较了著名的Warshall算法,给出了一个三角形算法。当关系矩阵是稀疏矩阵时,该算法比Warshall快。     

二元关系的传递闭包求法浅谈

本文介绍了三种求二元关系的传递闭包的方法,其均有效地减少了传递闭包的运算量。     

基于多重依赖关系的传递闭包研究及应用

文中通过改进Warshall-Folyd的算法,提出了一种依赖传递闭包算法和相应的动态闭包算法,其核心思想是依据依赖关系的分类和性质,定义关系矩阵和运算算子,使算法能解决选择依赖关系,并能表达直接、间接和选择三种依赖关系;同时,所提出动态算法能够运行时根据问题规模动态添加关系元素和依赖关系,解决在基本关系原则和部分关系集上求取闭包的问题。结合安全通用标准CC中关于组件间依赖关系的规定,给出了本文所提出算法的一个实际应用,表明算法取得了很好的效果。     

模糊聚类分析传递闭包法实用程序

简单介绍模糊聚类分析传递闭包法的一般步骤,给出了一个ＦｏｘＰｒｏ实用程序及其使用方法。     

HLA仿真系统中Lookahead的分析与动态调整策略

在HLA仿真系统中，Lookahead是影响系统性能的重要参量，对Lookahead的管理也是实现邦元程序的重要内容。采用时间分段的方式重新定义HLA仿真系统中的Lookahead，很好地解决了仿真运行中时戳增量改变较大的问题。在此基础上提出的Lookahead动态调整算法考虑了邦元程序对要接收事件的经验值，可以有效提高系统运行性能，协助邦元程序设计。     

Ranking of System Elements Based on Fuzzy Relation of Influence and Transitive Closure

The author proposes a method of elements ranking in multi-functional system using the fuzzy relations theory. The problem is formulated as an automatic classification based on the transitive closure of the fuzzy similarity relation. The original information about the system is given as a fuzzy relation of influence of elements’ failures on the performance of system’s functions. To calculate the degrees of element’s influence on the functions performance, we use the comparison of all influences with the least influence by 9-point Saaty scale. The proposed method relaxes the assumption about the independence and the binary-state (up-down) of elements. The possible fields of application are multi-functional systems with ill-defined structures such as organizational, ergatic, military, etc.     

Fast Jackson Networks with Dynamic Routing

A new class of models of queueing networks with load-balanced dynamic routing is considered. We propose a sufficient condition for positive recurrence of the arising Markov process and a limiting mean-field approximation where the process becomes deterministic and is described by a system of nonlinear ordinary differential equations.     

Efficient Transitive Closure Reasoning in a Combined Class/Part/Containment Hierarchy

Class hierarchies form the backbone of many implemented knowledge representation and reasoning systems. They are used for inheritance, classification and transitive closure reasoning. Part hierarchies are also important in artificial intelligence. Other hierarchies, e.g. containment hierarchies, have received less attention in artificial intelligence. This paper presents an architecture and an implementation of a hierarchy reasoner that integrates a class hierarchy, a part hierarchy, and a containment hierarchy into one structure. In order to make an implemented reasoner useful, it needs to operate at least at speeds comparable to human reasoning. As real-world hierarchies are always large, special techniques need to be used to achieve this. We have developed a set of parallel algorithms and a data representation called maximally reduced tree cover for that purpose. The maximally reduced tree cover is an improvement of a materialized transitive closure representation which has appeared in the literature. Our experiments with a medical vocabulary show that transitive closure reasoning for combined class/part/containment hierarchies in near constant time is possible for a fixed hardware configuration. Received 10 January 2000 / Revised 25 November 2000 / Accepted in revised form 9 February 2001     

An Experimental Study of Three Dataflow Paradigms in Multithreaded Database Transitive Closure Algorithms on Shared Memory Multiprocessors

This paper describes an experimental study of three dataflow paradigms, namely, no dataflow, pipelined dataflow, and network dataflow, in multithreaded database transitive closure algorithms on shared memory multiprocessors. This study shows that dataflow paradigm directly influences performance parameters such as the amount of interthread communication, how data are partitioned among the threads, whether access to each page of data is exclusive or shared, whether locks are needed for concurrency control, and how calculation termination is detected. The algorithm designed with no dataflow outperforms the algorithms with dataflow. Approximately linear speedup is achieved by the no dataflow algorithm with sufficient workload and primary memory. An exclusive access working set model and a shared access working set model describe the interactions between two or more threads′ working sets when access to each page of data is exclusive or shared among the threads, respectively. These models are experimentally verified.     

Lookahead actions in dispatching to parallel queues

Applying the first policy iteration (FPI) to any static dispatching (task assignment) policy yields a new improved dynamic policy that takes into account the particular cost structure and the expected future arrivals. However, it is generally hard to go beyond that due to the complex state space and the resulting difficulty in computing the value function for a dynamic policy. For example, applying FPI to identical FCFS servers with Bernoulli split gives the Least-Work-Left (LWL) policy, for which no closed-form value function is known. In fact, LWL with identical servers is equivalent to an M/G/k queue, the performance measures of which have remained as open problems. The situation gets even more complicated with heterogeneous servers. In this paper, we take an intermediate approach and consider lookahead actions that concern not only the current job but also the job arriving next, after which a basic (static) policy is assumed to take over. This is important as the benefits from some decisions can only be reaped with appropriate subsequent actions. The lookahead enables sound estimates also for marginal admission costs, e.g., with respect to LWL. The superior performance of the new near-optimal dispatching policies is demonstrated numerically.     

填补存储器间距的一种方法——前瞻性Cache

近年来CPU速度的提高远远超过了主存,CPU与主存之间的速度差距（称存储器间距－MeoryGap）越来越大,先进的高性能Cache结构的研究对于提高系统性能显得更加重要;在传统的Cache中,仅仅依靠程序扫行时访存指令流地下的局域性保证较高的Cache命令中率,使得Cache命中率的提高受到限制,本文提出了一种新型的“前瞻性Cache”,对即将执行的指公进行提前分析,并尽可能地在Load类指令尚未实际执行这前将所需的数据预先装和Cache,这样可以提高Cache的命中率,本文阐述了前瞻性Cache结构的方案,提出了定量的评价参数,并开发了软件工具对该结构进行模拟分析,模拟检验证明,这种方法能在不扩大处理机芯片上Cache容量的基础上,进一步提高动态执行中Cache的性能,对于填补存储器间距和提高系统性能可以起到较大作用。     

结合一种面-面碰撞检测算法的服装动态模拟

实时的服装动态模拟一直是计算机动画的研究热点。在回顾弹性模型及其碰撞问题的相关研究工作的基础上,采用基于质点－弹簧模型的动态模拟方法,产生了虚拟3D模特表面的服装动态效果。其中考虑了织物的非理想弹性属性和变化的空气流作用力,并针对系统实现的瓶颈－服装和人体的碰撞问题,提出一种碰撞检测算法。     

On the Influence of Lookahead in Competitive Paging Algorithms

We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is n-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal. Received April 8, 1994; revised May 15, 1995.