Partial match retrieval using recursive linear hashing

Recursive linear hashing is a hashing technique proposed for files which can grow and shrink dynamically. The scheme is an extension of linear hashing, a method originally proposed by Litwin, but unlike Litwin's scheme, it does not require conventional overflow pages. In this paper, we investigate the application of recursive linear hashing to partial match retrieval problems. Consistent with the results for primary key retrieval, recursive linear hashing performs better than the conventional scheme on these problems, especially at high load factors.     

Dynamic hashing

A new file organisation called dynamic hashing is presented. The organisation is based on normal hashing, but the allocated storage space can easily be increased and decreased without reorganising the file, according to the number of records actually stored in the file. The expected storage utilisation is analysed and is shown to be approximately 69% all the time. Algorithms for inserting and deleting a record are presented and analysed. Retrieval of a record is fast, requiring only one access to secondary storage. There are no overflow records. The proposed scheme necessitates maintenance of a relatively small index structured as a forest of binary trees or slightly modified binary tries. The expected size of the index is analysed and a compact representation of the index is suggested.     

Sequential access in splay trees takes linear time

Sleator and Tarjan have invented a form of self-adjusting binary search tree called thesplay tree. On any sufficiently long access sequence, splay trees are as efficient, to within a constant factor, as both dynamically balanced and static optimum search trees. Sleator and Tarjan have made a much stronger conjecture; namely, that on any sufficiently long access sequence and to within a constant factor, splay trees are as efficient asany form of dynamically updated search tree. Thisdynamic optimality conjecture implies as a special case that accessing the items in a splay tree in sequential order takes linear time, i.e.O(1) time per access. In this paper we prove this special case of the conjecture, generalizing an unpublished result of Wegman. Oursequential access theorem not only supports belief in the dynamic optimality conjecture but provides additional insight into the workings of splay trees. As a corollary of our result, we show that splay trees can be used to simulate output-restricted deques (double-ended queues) in linear time. We pose several open problems related to our result.     

On the power of white pebbles

We construct a family (G _p |p) of directed acyclic graphs such that any black pebble strategy forG _p requiresp ² pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.Supported by the National Science Foundation under contract no. DCR-8407256 and by the office of Naval Research under contract no. N0014-80-0517.     

A las vegas rnc algorithm for maximum matching

Recently two randomized algorithms were discovered that find a maximum matching in an arbitrary graph in polylog time, when run on a parallel random access machine. Both are Monte Carlo algorithms — they have the drawback that with non-zero probability the output is a non-maximum matching. We use the min-max formula for the size of a maximum matching to convert any Monte Carlo maximum matching algorithm into a Las Vegas (error-free) one. The resulting algorithm returns (with high probability) a maximum matching and a certificate proving that the matching is indeed maximum. Research supported by DARPA grant N00039-84-C-0098 and by a US Army Research Office fellowship.     

The average-case analysis of some on-line algorithms for bin packing

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem. A preliminary version of this paper appeared inProc. 25th IEEE Symposium on Foundations of Computer Science, 193–200. This research was done while the author was at the Massachusetts Institute of Technology Dept. of Mathematics and was supported by a NSF Graduate Fellowship and by Air Force grant OSR-82-0326.     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

The influence of large coalitions

This paper contains two results on influence in collective decision games. The first part deals with general perfect information coin-flipping games as defined in [3].Baton passing (see [8]), ann-player game from this class is shown to have the following property: IfS is a coalition of size at most \(\frac{n}{{3\log n}}\) , then the influence ofS on the game is only \(O\left( {\frac{{\left| S \right|}}{n}} \right)\) . This complements a result from [3] that for everyk there is a coalition of sizek with influence Ω(k/n). Thus the best possible bounds on influences of coalitions of size up to this threshold are known, and there need not be coalitions up to this size whose influence asymptotically exceeds their fraction of the population. This result may be expected to play a role in resolving the most outstanding problem in this area: Does everyn-player perfect information coin flipping game have a coalition ofo(n) players with influence 1?o(1)? (Recently Alon and Naor [1] gave a negative answer to this question.) In a recent paper Kahn, Kalai and Linial [7] showed that for everyn-variable boolean function of expectation bounded away from zero and one, there is a set of \(\frac{{n\omega (n)}}{{\log n}}\) variables whose influence is 1?o(1), wherew(n) is any function tending to infinity withn. They raised the analogous question where 1?o(1) is replaced by any positive constant and speculated that a constant influence may be always achievable by significantly smaller sets of variables. This problem is almost completely solved in the second part of this article where we establish the existence of boolean functions where only sets of at least \(\Omega \left( {\frac{n}{{\log ^2 n}}} \right)\) variables can have influence bounded away from zero.     

Optimal dynamic multi-attribute hashing for range queries

This paper examines a partial match retrieval scheme which supports range queries for highly dynamic databases. The scheme relies on order preserving multi-attribute hashing. In general, designing optimal indexes is NP-hard. Greedy algorithms used to determine the optimal indexes for simple partial match queries are not directly applicable because there are a larger number of queries to consider in determining the optimal indexes. In this paper we present heuristic algorithms which provide near-optimal solutions. The optimisation scheme we propose can be used to design other dynamic file structures such as the grid file, BANG file and multilevel grid file to further enhance their retrieval performance taking into consideration the query distribution.     

Recursive constructions of secure codes and hash families using difference function families

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.     

A simulation tool for the performance evaluation of parallel branch and bound algorithms

Parallel computation offers a challenging opportunity to speed up the time consuming enumerative procedures that are necessary to solve hard combinatorial problems. Theoretical analysis of such a parallel branch and bound algorithm is very hard and empirical analysis is not straightforward because the performance of a parallel algorithm cannot be evaluated simply by executing the algorithm on a few parallel systems. Among the difficulties encountered are the noise produced by other users on the system, the limited variation in parallelism (the number of processors in the system is strictly bounded) and the waste of resources involved: most of the time, the outcomes of all computations are already known and the only issue of interest is when these outcomes are produced.We will describe a way to simulate the execution of parallel branch and bound algorithms on arbitrary parallel systems in such a way that the memory and cpu requirements are very reasonable. The use of simulation has only minor consequences for the formulation of the algorithm.     

An efficient modified boosting method for solving classification problems

Based on the Adaboost algorithm, a modified boosting method is proposed in this paper for solving classification problems. This method predicts the class label of an example as the weighted majority voting of an ensemble of classifiers. Each classifier is obtained by applying a given weak learner to a subsample (with size smaller than that of the original training set) which is drawn from the original training set according to the probability distribution maintained over the training set. A parameter is introduced into the reweighted scheme proposed in Adaboost to update the probabilities assigned to training examples so that the algorithm can be more accurate than Adaboost. The experimental results on synthetic and several real-world data sets available from the UCI repository show that the proposed method improves the prediction accuracy, the execution speed as well as the robustness to classification noise of Adaboost. Furthermore, the diversity–accuracy patterns of the ensemble classifiers are investigated by kappa–error diagrams.     

An all-substrings common subsequence algorithm

Given two strings A and B of lengths n_a and n_b, n_a?n_b, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B^′ of B, the length of the longest string that is a subsequence of both A and B^′. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n_an_b) time and O(n_a+n_b) space. After this preparation, it is possible to build a matrix of size that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem.     

A refinement of a compression-oriented addressing scheme

Chang and Wu have proposed a letter-oriented perfect hashing scheme based on sparse matrix compression. We present a method which is a refinement of the Chang-Wu scheme. By experimental evaluation, we show that the hashing of our refinement has more efficient storage utilization than Chang-Wu's method. Our refinement is valuable in practical implementations of hashing for large sets of keys.     

Maximal continuants and the Fine-Wilf theorem

The following problem was posed by C.A. Nicol: given any finite sequence of positive integers, find the permutation for which the continuant (i.e. the continued fraction denominator) having these entries is maximal, resp. minimal. The extremal arrangements are known for the regular continued fraction expansion. For the singular expansion induced by the backward shift ⌈1/x⌉-1/x the problem is still open in the case of maximal continuants. We present the explicit solutions for sequences with pairwise different entries and for sequences made up of any pair of digits occurring with any given (fixed) multiplicities. Here the arrangements are uniquely described by a certain generalized continued fraction. We derive this from a purely combinatorial result concerning the partial order structure of the set of permutations of a linearly ordered vector. This set has unique extremal elements which provide the desired extremal arrangements. We also prove that the palindromic maximal continuants are in a simple one-to-one correspondence with the Fine and Wilf words with two coprime periods which gives a new analytic and combinatorial characterization of this class of words.     

Davenport–Schinzel Trees*

In this paper we study labeled–tree analogues of (generalized) Davenport–Schinzel sequences.We say that two sequences a ₁ ... a _k , b ₁ ... b _k of equal length k are isomorphic, if a _i = a _j i b _i = b _j (for all i, j). For example, the sequences 11232, 33141 are isomorphic. We investigate the maximum size of a labeled (rooted) tree with each vertex labeled by one of n labels in such a way that, besides some technical conditions, the sequence of labels along any path (starting from the root) contains no subsequence isomorphic to a fixed forbidden sequence u.We study two models of such labeled trees. Each of the models is known to be essentially equivalent also to other models. The labeled paths in a special case of one of our models correspond to classical Davenport–Schinzel sequences.We investigate, in particular, for which sequences u the labeled tree has at most O(n) vertices. In both models, we answer this question for any forbidden sequence u over a two-element alphabet and also for a large class of other sequences u.* This research was partially supported by Charles University grants No. 99/158 and 99/159 and by Czech Republic Grant GAR 201/99/0242. Supported by project LN00A056 of The Ministry of Education of the Czech Republic.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Recurrence relations for polynomial sequences via Riordan matrices

We give recurrence relations for any family of generalized Appell polynomials unifying so some known recurrences for many classical sequences of polynomials. Our main tool to get our goal is the Riordan group. We use the product of Riordan matrices to interpret some relationships between different polynomial families. Moreover using the Hadamard product of series we get a general recurrence relation for the polynomial sequences associated to the so called generalized umbral calculus.     

The Linear-Array Conjecture in Communication Complexity Is False

linear array network consists of k+1 processors with links only between and (0≤i<k). It is required to compute some boolean function f(x,y) in this network, where initially x is stored at and y is stored at . Let be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, , where D(f) is the standard two-party communication complexity of f. Tiwari proved that for almost all functions and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite family of functions for which is essentially at most . Our construction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, given the least number of monochromatic rectangles in any partition of the input space. How tight are such bounds? We exhibit certain functions, for which the (two-party) communication complexity is twice as large as the best lower bound obtainable this way. Received: March 1, 1996     

More analysis of double hashing

In [8], a deep and elegant analysis shows that double hashing is asymptotically equivalent to the ideal uniform hashing up to a load factor of about 0.319. In this paper we show how a randomization technique can be used to develop a surprisingly simple proof of the result that this equivalence holds for load factors arbitrarily close to 1.An earlier version of the paper was presented at the20th Annual ACM Symposium on Theory of Computing, Chicago, IL, May 1988.Supported by National Science Foundation Grants DCR 85-09667 and CCR 89-12063 at the University of California at IrvinePartially supported by National Science Foundation Grant DCR 85-09667 at the University of California at Irvine