Permutation anonymization

In data publishing, anonymization techniques have been designed to provide privacy protection. Anatomy is an important techniques for privacy preserving in data publication and attracts considerable attention in the literature. However, anatomy is fragile under background knowledge attack and the presence attack. In addition, anatomy can only be applied into limited applications. To overcome these drawbacks, we propose an improved version of anatomy: permutation anonymization, a new anonymization technique that is more effective than anatomy in privacy protection, and in the meanwhile is able to retain significantly more information in the microdata. We present the detail of the technique and build the underlying theory of the technique. Extensive experiments on real data are conducted, showing that our technique allows highly effective data analysis, while offering strong privacy guarantees.     

Permutation schedules

The optimal scheduling problem of parallel identical machines is reduced by the resource approach to optimal permutation scheduling of jobs. Permutation scheduling algorithms for this problem are given.Translated from Kibernetika, No. 1, pp. 81–83, 111, January–February, 1990.     

Fault-Tolerant Permutation Routing in Hypercubes

This paper introduces a deterministic mechanism for fault-tolerant permutation routing on an n-cube with less than n processor and/or link faults, using O(n) steps and constant queue size. The basic approach is to modify an existing route of a given permutation to avoid the faulty processors and/or faulty links, yet only incurring a constant factor slowdown in communication by ensuring that, at each step of the routing, every message either stays where it is or is sent to a nonfaulty neighbor, each link has at most one message traversing it in each direction, and the routing uses constant queue size. The existing route used in this paper is Benes routes. However, our method can be applied to any routing method where, in each step, all messages use links across the same dimension. The same approach can also be applied to online routing based on Batcher′s bitonic sorting to avoid faults.     

Computing Permutation Encodings

A permutation can be encoded in several different ways. This paper discusses some relations among some encodings and how one can be computed from others. The paper shows a short proof of an existing efficient algorithm for encoding a permutation and presents two new efficient algorithms. One of the new algorithms is constructed as the inverse of an existing algorithm for decoding, making it the first efficient permutation encoding algorithm obtained in that way. Received June 1994 / Accepted in revised form December 1998     

Permutation rewriting and algorithmic verification

We propose a natural subclass of regular languages (Alphabetic Pattern Constraints, APC) which is effectively closed under permutation rewriting, i.e., under iterative application of rules of the form ab → ba. It is well-known that regular languages do not have this closure property, in general. Our result can be applied for example to regular model checking, for verifying properties of parametrized linear networks of regular processes, and for modeling and verifying properties of asynchronous distributed systems. We also consider the complexity of testing membership in APC and show that the question is complete for PSPACE when the input is an NFA, and complete for NLOGSPACE when it is a DFA. Moreover, we show that both the inclusion problem and the question of closure under permutation rewriting are PSPACE-complete when we restrict to the class APC.     

Finding Possible Permutation Characters

We describe three different methods to compute all those characters of a finite group that have certain properties of transitive permutation characters. First, a combinatorial approach can be used to enumerate vectors of multiplicities. Secondly, these characters can be found as certain integral solutions of a system of inequalities. Thirdly, they are calculated via Gaussian elimination. The methods are used to determine these characters for some finite groups and runtimes are listed. In the final section, a permutation character of the Lyons group is constructed.     

最佳并行排列组合算法

本文给出两个新的最佳并行排列组合算法。这里所说的排列组合均指从n个元素中取m个元素的排列和组合处理。算法可运行于一种非常简单的并行计算模型上,它由k个同步运行的处理机构成,其中1≤k≤N,N为要处理的元素个数。当1≤k≤N/n,算法需O(「N/k」·h)时间。     

Permutation inversions and multidimensional cumulative distribution functions

The problem of computing the empirical cumulative distribution function (ECDF) of N points in k-dimensional space has been studied and motivated recently by Bentley [1], whose solution uses recursive multidimensional divide-and-conquer. In this paper, the problem is treated as a generalization of the problem of computing the inversion of a permutation. An algorithm of Knuth [3] is then extended to yield an O(kN(log₂N)^k?1) solution to the ECDF problem, which is comparable to Bentley's solution. Neither solution approaches the O(kN log₂N) lower bound, and they are worse than the O(kN²) ‘brute force’ algorithm for large k. The new algorithm, however, has the advantage of being highly parallel so that fast solution exists with parallel processors.     

分组密码对称置换算法设计

证明了对称置换的圈结构与计数,提出并设计了一种以特定对称结构作为分组密码算法的置换部分,以减小加密算法硬件空间,提高加/解密速度。指出了分组密码的多次迭代使对称置换结构复杂化,可以选择对称置换作为分组密码算法的扩散部分来设计。     

Permutation Routing on Reconfigurable Meshes

In this paper we present efficient algorithms for packet routing on the reconfigurable linear array and the reconfigurable two-dimensional mesh. We introduce algorithms that are efficient in the worst case and algorithms that are better on average. The time bounds presented are better than those achievable on the conventional mesh and previously known algorithms. We present two variants of the reconfigurable mesh. In the first model, M _r , the processors are attached to a reconfigurable bus, the individual edge connections being bidirectional. In the second model, M _mr , the processors are attached to two unidirectional buses. In this paper we present lower bounds and nearly matching upper bounds for packet routing on these two models. As a consequence, we solve two of the open problems mentioned in [9]. Received August 17, 1998; revised November 3, 1999.     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).     

Euclidean Distance Based Permutation Methods in Atmospheric Science

The majority of existing statistical methods inherently involve complex nonmetric analysis spaces due to their least squares regression origin; consequently, the analysis space of such statistical methods is not consistent with the simple metric Euclidean geometry of the data space in question. The statistical methods presented in this paper are consistent with the data spaces in question. These alternative methods depend on exact and approximate permutation procedures for univariate and multivariate data involving cyclic phenomena, autoregressive patterns, covariate residual analyses including most linear model based experimental designs, and linear and nonlinear prediction model evaluations. Specific atmospheric science applications include climate change, Atlantic basin seasonal tropical cyclone predictions, analyses of weather modification experiments, and numerical model evaluations for phenomena such as cumulus clouds, clear-sky surface energy budgets, and mesoscale atmospheric predictions.     

比特置换运算单元的设计与实现

比特置换操作在对称密码算法中使用频率非常高,但传统处理器对比特置换操作并不直接支持.为此,美国普林斯顿大学的Ruby B. Lee提出比特置换指令,并证明了比特置换指令对提高通用处理器上实现的密码算法的性能有明显作用[10].本文重点研究比特置换指令的实现技术,提出一种比特置换运算单元的实现算法,并在FPGA上进行验证.     

Shift Register Graphs and Permutation/Reset Automata

Abstract

This note completes the author's study of embedding of cascade products of permutation or reset automata in so-called shift register graphs.     

有限域上置换多项式的研究进展

AGW准则和分段方法是构造有限域上置换多项式的两种主要方法。介绍有限域上置换多项式在密码学和编码理论中的应用,总结利用AGW准则和分段方法构造有限域上置换多项式和逆置换的研究进展,阐述置换多项式存在的问题,并对下一步研究工作进行展望。     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.