Algorithmic approach to the consecutive retrieval property

Ghosh's consecutive retrieval property (CR property) not only represents an elegant file organization, but also raises the problem of how to construct such a file with this property. Ghosh used ann ×m 0–1 incidence matrix, wheren is the number of records andm is the number of queries, as a tool for constructing a file with the CR property. In this paper the rows and columns of the incidence matrix are restricted to unique 0–1 patterns. It is found that such a unique incidence matrix cannot have the CR property if the number of rows is greater than 2m–1. This upper bound can be used to generatem(2m–1) columns, which form all the matrices with the CR property that may correspond to the given matrix. Two algorithms are presented which map the columns of the given incidence matrix to these columns with consecutive l's. A proposed implementation in terms of data base design is also presented.     

On Unbounded Tolerable Solution Sets

We prove that the nonempty tolerable solution set of the interval linear system Ax = b is unbounded if and only if the interval matrix of the system has linearly dependent degenerate columns. Also, we prove that the tolerable solution set may be represented as a sum of the linear subspace {c ε ℝⁿ ∨ Ac = 0} and a bounded convex polyhedron and propose a way for suitable estimation of unbounded tolerable solution sets.     

Optimal multiway search trees for variable size keys

Summary This paper considers the construction of optimal search trees for a sequence of n keys of varying sizes, under various cost measures. Constructing optimal search cost multiway trees is NP-hard, although it can be done in pseudo-polynomial time O ³ and space O ², where L is the page size limit. An optimal space multiway search tree is obtained in O ³ time and O ² space, while an optimal height tree in O(n ² log² n) time and O(n) space both having additionally minimal root sizes. The monotonicity principle does not hold for the above cases. Finding optimal search cost weak B-trees is NP-hard, but a weak B-tree of height 2 and minimal root size can be constructed in O(n log n) time. In addition, if its root is restricted to contain M keys then a different algorithm is applied, having time complexity O(nM log n). The latter solves a problem posed by McCreight.     

On frequent sets of Boolean matrices

Given a Boolean matrix and a threshold t, a subset of the columns is frequent if there are at least t rows having a 1 entry in each corresponding position. This concept is used in the algorithmic, combinatorial approach to knowledge discovery and data mining. We consider the complexity aspects of frequent sets. An explicit family of subsets is given that requires exponentially many rows to be represented as the family of frequent sets of a matrix, with any threshold. Examples are given of families that can be represented by a small matrix with threshold t, but that require a significantly larger matrix if the threshold is less than t. We also discuss the connections of these problems to circuit complexity and the existence of efficient listing algorithms. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bipartite isoperimetric graph partitioning for data co-clustering

Data co-clustering refers to the problem of simultaneous clustering of two data types. Typically, the data is stored in a contingency or co-occurrence matrix C where rows and columns of the matrix represent the data types to be co-clustered. An entry C _ij of the matrix signifies the relation between the data type represented by row i and column j. Co-clustering is the problem of deriving sub-matrices from the larger data matrix by simultaneously clustering rows and columns of the data matrix. In this paper, we present a novel graph theoretic approach to data co-clustering. The two data types are modeled as the two sets of vertices of a weighted bipartite graph. We then propose Isoperimetric Co-clustering Algorithm (ICA)—a new method for partitioning the bipartite graph. ICA requires a simple solution to a sparse system of linear equations instead of the eigenvalue or SVD problem in the popular spectral co-clustering approach. Our theoretical analysis and extensive experiments performed on publicly available datasets demonstrate the advantages of ICA over other approaches in terms of the quality, efficiency and stability in partitioning the bipartite graph.     

Parallel solution of dense linear systems using diagonalization methods

We study the parallel implementation of two diagonalization methods for solving dense linear systems: the well known Gauss-Jordan method and a new one introduced by Huard. The number of arithmetic operations performed by the Huard method is the same as for Gaussian elimination, namely 2n ³/3, less than for the Jordan method, namely n ³. We introduce parallel versions of these methods, compare their performances and study their complexity. We assume a shared memory computer with a number of processors p of the order of n, the size of the problem to be solved, We show that the best parallel version for Jordan's method is by rows whereas the best one for Huard's method is by columns. Our main result states that for a small number of processors the parallel Huard method is faster than the parallel Jordan method and slower otherwise. The separation is obtained for p = 0.44n.     

A note on the Consecutive Ones Submatrix problem

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer K is given and we want to know if there exists a submatrix B of A consisting of K columns of A with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979].     

K-center and K-median problems in graded distances

Graded distances are generalizations of the Euclidean distance on points in R¹. They have been used in the study of special cases of NP-hard problems. In this paper, we study the k-center and K-median problems with graded distance matrices. We first prove that the K-center problem is polynomial time solvable when the distance matrix is graded up the rows or graded down the rows. We then prove that the K-median problem is NP-complete when the distance matrix is graded up the rows or graded down the rows. An easy special case of the K-median problem with graded distance matrices is also discussed.     

Clustering rows and/or columns of a two-way contingency table and a related distribution theory

The row-wise multiple comparison procedure proposed in Hirotsu [Hirotsu, C., 1977. Multiple comparisons and clustering rows in a contingency table. Quality 7, 27–33 (in Japanese); Hirotsu, C., 1983. Defining the pattern of association in two-way contingency tables. Biometrika 70, 579–589] has been verified to be useful for clustering rows and/or columns of a contingency table in several applications. Although the method improved the preceding work there was still a gap between the squared distance between the two clusters of rows and the largest root of a Wishart matrix as a reference statistic for evaluating the significance of the clustering. In this paper we extend the squared distance to a generalized squared distance among any number of rows or clusters of rows and dissolves the loss of power in the process of the clustering procedure. If there is a natural ordering in columns we define an order sensitive squared distance and then the reference distribution becomes that of the largest root of a non-orthogonal Wishart matrix, which is very difficult to handle. We therefore propose a very nice χ²-approximation which improves the usual normal approximation in Anderson [Anderson, T.W., 2003. An Introduction to Multivariate Statistical Analysis. 3rd ed. Wiley Intersciences, New York] and also the first χ²-approximation introduced in Hirotsu [Hirotsu, C., 1991. An approach to comparing treatments based on repeated measures. Biometrika 75, 583–594]. A two-way table reported by Guttman [Guttman, L., 1971. Measurement as structural theory. Psychometrika 36, 329–347] and analyzed by Greenacre [Greenacre, M.J., 1988. Clustering the rows and columns of a contingency table. Journal of Classification 5, 39–51] is reanalyzed and a very nice interpretation of the data has been obtained.     

A factorization principle for stabilization of linear control systems

By introducing a fictitious signal y⁰ if necessary we define a transform which generalizes the passage from the scattering to the chain formalism in circuit theory. Given a factorization ??? = ?R of ??? where R is a block matrix function with a certain key block equal to a minimal phase (or outer) matrix function, we show that a given compensator u = Ky is internally stabilizing for the system ?? if and only if a related compensator K′ is stabilizing for ?. Factorizations ??? = ?R with ? having a certain block upper triangular form lead to an alternative derivation of the Youla parametrization of stabilizing compensators. Factorizations with ? equal to a J-inner matrix function (in a precise weak sense) lead to a parametrization of all solutions K of the H^∞ problem associated with ??. This gives a new solution of the H^∞ problem completely in the transfer function domain. Computation of the needed factorization ??? = ?R in terms of a state-space realization of ?? leads to the state-space formulas for the solution of the H^∞ problem recently obtained in the literature.     

Fast Parallel Algorithms for Solving Triangular Systems of Linear Equations on the Hypercube

This paper presents efficient hypercube algorithms for solving triangular systems of linear equations by using various matrix partitioning and mapping schemes. Recently, several parallel algorithms have been developed for this problem. In these algorithms, the triangular solver is treated as the second stage of Gauss elimination. Thus, the triangular matrix is distributed by columns (or rows) in a wrap fashion since it is likely that the matrix is distributed this way after an LU decomposition has been done on the matrix. However, the efficiency of the algorithms is low. Our motivation is to develop various data partitioning and mapping schemes for hypercube algorithms by treating the triangular solver as an independent problem. Theoretically, the computation time of our best algorithm is ((12p + 1)n² + 36p³ − 28p²)/(24p²), and an upper bound on the communication time is 2αp log p (log n − log p) + 2α(log n − log p − 1) log p + (cn/p − 2c)(2 log p − 1) + log p(cn − c − α), where α is the (communication startup time)/(one entry scanning time), c is a constant, n is the order of the triangular system and p is the number of nodes in the hypercube. Experimental results show that the algorithm is efficient. The efficiency of the algorithm is 0.945 when p = 2, n = 513, and 0.93 when p = 8, n = 1025.     

Efficient reliable communication over partially authenticated networks

Reliable communication between processors in a network is a basic requirement for executing any protocol. Dolev [7] and Dolev et al. [8] showed that reliable communication is possible if and only if the communication network is sufficiently connected. Beimel and Franklin [1] showed that the connectivity requirement can be relaxed if some pairs of processors share authentication keys. That is, costly communication channels can be replaced by authentication keys. In this work, we continue this line of research. We consider the scenario where there is a specific sender and a specific receiver in a synchronous network. In this case, the protocol of [1] has n^O(n) rounds even if there is a single Byzantine processor. We present a more efficient protocol with round complexity of (n/t)^O(t), where n is the number of processors in the network and t is an upper bound on the number of Byzantine processors in the network. Specifically, our protocol is polynomial when the number of Byzantine processors is O(1), and for every t its round complexity is bounded by 2^O(n). The same improvements hold for reliable and private communication. The improved protocol is obtained by analyzing the properties of a "communication and authentication graph" that characterizes reliable communication. Received: 13 January 2004, Accepted: 22 September 2004, Published online: 13 January 2005 A preliminary version of this paper appeared in [2].     

VISOR: Vast Independence System Optimization Routine

An algorithm is sketched that generates all K maximal independent sets and all M minimal dependent sets of an arbitrary independence system, based on a set of cardinality n having at most 2 ⁿ subsets, with access to an oracle that decides if a set is independent or not. Because the algorithm generates all those sets, it solves the problems of finding all maximum independent and minimum dependent sets. Those problems are known to be impossible to solve in general in time polynomial in n , K , and M , and they are \cal N \cal P hard. The algorithm proposed and used is efficient in the sense that it requires only O(nK+M) or O(K+nM) visits to the oracle, the nonpolynomial part is only related to bitstring comparisons and the like, which can be performed rather quickly and, to some degree, in parallel on a sequential machine. This complexity compares favorably with another algorithm that is O(n ² K ² ) . The design of a computer routine that implements the algorithm in a highly optimized way is discussed. The routine behaves as expected, as is shown by numerical experiments on a range of randomly generated independence systems with n up to n=34 . Application on an engineering design problem with n=28 shows the routine requires almost 10 ⁶ times less visits to the oracle than an exhaustive search, while the time spent in visiting the oracle is still significantly larger than that spent for all other computations together. Received March 30, 1998; revised February 10, 1999 and April 27, 1999.     

HOW TO MAKE THE HILL CIPHER SECURE

ABSTRACT

This paper presents a symmetric cipher that is actually a variation of the Hill cipher. The new scheme makes use of “random” permutations of columns and rows of a matrix to form a “different” key for each data encryption. The cipher has matrix products and permutations as the only operations which may be performed “efficiently” by primitive operators, when the system parameters are carefully chosen.     

AN EXTENSION OF HILL CIPHER USING GENERALISED INVERSES AND mth RESIDUE MODULO n

Hill Cipher is a symmetric polyalphabetic block cipher that enciphers a string of letters into another string of the same length using the linear transformation y=xK. In deciphering, the determinant value must be less than 26 and relatively prime to 26 so that the matrix K of the linear transformation is invertible in modulo 26. The Affine Hill cipher extends the concept of Hill cipher by using the non-linear transformation y=xK+b. In this paper, we extend this concept to encrypt a plaintext of blocksize m to a ciphertext of blocksize n≥m using (a) affine transformation and (b) polynomial transformation to make this cipher more secure. Here the matrix K of the transformation need not be a square matrix. To enable decryption, we state the conditions to be satisfied by K which are as follows. Case (a): (i) For affine transformation, the generalised inverse K ⁺ of the matrix K corresponding to the transformation should satisfy the equation KK ⁺=I in modulo p where p is a chosen prime p>26. For m=n, K ⁺ is the usual inverse of the matrix K. Case(b): (i) For polynomial transformation, the generalised inverse K ⁺ should satisfy the above condition, (ii) If r is the degree of the polynomial, then choose those values of s≤r such that the sth root of modulo p exists for all elements in Z _p . In other words, choose those values of s that are relatively prime to Φ(p).     

Functional dependencies among Boolean dependencies

In this paper, we consider functional dependencies among Boolean dependencies (BDs, for short). Armstrong relations are defined for BDs (called BD-Armstrong relations). For BDs, two necessary and sufficient conditions for the existence of BD-Armstrong relations are given. A necessary and sufficient condition for the existence of Armstrong relations for functional dependencies (FDs, for short) is given, which in some sense is more convenient than the condition given in [3]. We give an algorithm that solves the problem of deciding if two BDs imply the same set of functional dependencies. If the BDs are given in perfect disjunctive normal form, then the algorithm requires only polynomial time. Although Mannila and Räihä have shown that for some relations exponential time is needed for computing any cover of the set of FDs defined in this relation, as a consequence, we show that the problem of deciding if two relations satisfy the same set of FDs can be solved in polynomial time. Another consequence is a new correspondence of the families of functional dependencies to the families of Sperner systems. By this correspondence, the estimate of the number of databases given previously in [6] is improved. It is shown that there is a one-to-one correspondence between the closure of the FDs that hold in a BD and its so-calledbasic cover. As applications of basic covers, we obtain a representation of a key, the family of minimal keys and a representation of canonical covers.This research was supported by the Hungarian Foundation for Scientific Research, Grant Nos. OTKA 2575, 2149.     

Algorithms for projecting points to give the most uniform distribution with applications to hashing

This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angle ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn² logn) time and On²+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On²+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n²+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb < n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b^0.610n^1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.This work was supported in part by a Grant in Aid for Scientific Research of the Ministry of Education, Science, and Cultures of Japan.     

Selection in X + Y and matrices with sorted rows and columns

Let A be an n×n matrix of reals with sorted rows and columns and k an integer, 1 ? k ? n². We present an O(n) time algorithm for selecting the kth smallest element of A. If X and Y are sorted n-vectors of reals, then Cartesian sum X + Y is such a matrix as A. One application of selection in X + Y can be found in statistics. The algorithm presented here is based on a new divide-and-conquer technique, which can be applied to similar order related problems as well. Due to the fact that the algorithm has a relatively small constant time factor, this result is of practical as well as theoretical interest.     

Stabilizability of Discrete Systems over Rings

Linear nonautonomous discrete single-input systems in K ⁿ , where K is a ring with unit, are studied. Total controllability is defined and every totally controllable system is shown to be representable in canonical form (i.e., as an nth-order scalar equation with coefficients in K). Therefore, every totally controllable system is stabilizable in the sense that all solutions vanish for some linear feedback, beginning from a finite instant.     

A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs

We give an approximation algorithm for fractional packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+ε of opt (the optimal cost) in time O((r+c)log(n)/ε ²+n).