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.     

Frequency loading and linear probing

It is well-known that the minimum expected search length for hash files which employ linear probing to solve the overflow problem is achieved by frequency loading. In this paper the resulting expected search length is computed. A rather simple formula for computing the expected length of unsuccessful searches is obtained as a by-product. An infinite number of buckets is assumed.     

Analysis of grid file algorithms

Grid file algorithms were suggested in [12] to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. We provide an asymptotic analysis. The growth of the indexes appears to be non-linear for uniform distributions:O(v ^c ) orO(v ), wherec=1+b^–1, =1+(s-1)/(sb+1),s is the number of attributes being used,v the file size, andb the page capacity of the system. Finally we give corresponding results for biased distributions and compare transient phases.     

Sharp load thresholds for cuckoo hashing

The paradigm of many choices has influenced significantly the design of efficient data structures and, most notably, hash tables. Cuckoo hashing is a technique that extends this concept. There, we are given a table with n locations, and we assume that each location can hold one item. Each item to be inserted chooses randomly k ≥ 2 locations and has to be placed in any one of them. How much load can cuckoo hashing handle before collisions prevent the successful assignment of the available items to the chosen locations? Practical evaluations and theoretical analysis of this method have shown that one can allocate a number of elements that is a large proportion of the size of the table, being very close to 1 even for small values of k such as 4 or 5. In this paper we show that there is a critical value for this proportion: with high probability, when the amount of available items is below this value, then these can be allocated successfully, but when it exceeds this value, the allocation becomes impossible. We give explicitly for each k ≥ 3 this critical value. This answers an open question posed by Mitzenmacher (ESA '09) and underpins theoretically the experimental results. Our proofs are based on the translation of the question into a hypergraph setting, and the study of the related typical properties of random k ‐uniform hypergraphs.© 2012 Wiley Periodicals, Inc. Random Struct., 2012     

On the insertion time of random walk cuckoo hashing

Cuckoo Hashing is a hashing scheme invented by pervious study of Pagh and Rodler. It uses d ≥ 2 distinct hash functions to insert n items into the hash table of size m = (1 + ε)n. In their original paper they treated d = 2 and m = (2 + ε)n. It has been an open question for some time as to the expected time for Random Walk Insertion to add items when d > 2. We show that if the number of hash functions d ≥ d_ε = O(1) then the expected insertion time is O(1) per item.     

Tiny families of functions with random properties: A quality-size trade-off for hashing

We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family), and the quality (or error parameter) of the pseudorandom property it achieves. Unlike previous constructions, most notably universal hashing, the size of our families is essentially independent of the size of the domain on which the functions operate. The first construction is for the mixing property—mapping a proportional part of any subset of the domain to any other subset. The other two are for the extraction property—mapping any subset of the domain almost uniformly into a range smaller than it. The second and third constructions handle, respectively, the extreme situations when the range is very large or very small. We provide lower bounds showing that our constructions are nearly optimal, and mention some applications of the new constructions. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 315–343 (1997)     

ONE-WAY MULTIVARIATE REPEATED MEASUREMENTS ANALYSIS OF VARIANCE MODEL

The one-way multivariate repeated measurements analysis of variance (1-way MRM ANOVA) model for complete data and the sphericity test are studied.     

On the expected longest length probe sequence for hashing with separate chaining

Hashing is a widely used technique for data organization. Hash tables enable a fast search of the stored data and are used in a variety of applications ranging from software to network equipment and computer hardware. One of the main issues associated with hashing are collisions that cause an increase in the search time. A number of alternatives have been proposed to deal with collisions. One of them is separate chaining, in which for each hash value an independent list of the elements that have that value is stored. In this scenario, the worst case search time is given by the maximum length of that list across all hash values. This worst case is often referred to as Longest Length Probe Sequence (llps) in the literature. Approximations for the expected longest length probe sequence when the hash table is large have been proposed and an exact analytical solution has also been presented in terms of a set of recurring equations. In this paper, a novel analytical formulation of the expected longest length probe sequence is introduced. The new formulation does not require a recursive computation and can be easily implemented in a symbolic computation tool.     

Parking with density

We study parkings with n places, where m(n) cars are placed according to a nonuniform probability. The aim of this paper is to show a threshold function (depending on the distribution) for the emergence of a giant component. The size of the largest blocks of consecutive occupied places and the total displacement of the cars are also studied. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 364–380, 2001.     

Generalized model with repeated calls in case of extreme load

Recurrence formulas for finding any desired number of terms in the asymptotic expansion of basic stationary performance measures of a generalized full-available system with repeated calls into a power series of the intensity of primary calls as it tends to infinity are derived. The first 3–4 terms of the expansion are found in explicit form. Other coefficients can be found numerically. It is shown that a number of interesting particular cases can be obtained from the model by proper choice of the values of input parameters. Among them it is worth mentioning models with possibility of call repetitions because of unsuccessful finishing of waiting time, inner blocking or unsuccessful finishing of service time. This revised version was published online in June 2006 with corrections to the Cover Date.     

The effective minimax value of asynchronously repeated games

We study the effect of asynchronous choice structure on the possibility of cooperation in repeated strategic situations. We model the strategic situations as asynchronously repeated games, and define two notions of effective minimax value. We show that the order of players moves generally affects the effective minimax value of the asynchronously repeated game in significant ways, but the order of moves becomes irrelevant when the stage game satisfies the non-equivalent utilities (NEU) condition. We then prove the Folk Theorem that a payoff vector can be supported as a subgame perfect equilibrium outcome with correlation device if and only if it dominates the effective minimax value. These results, in particular, imply both Lagunoff and Matsuis (1997) result and Yoon (2001)s result on asynchronously repeated games.I thank three anonymous referees as well as an associate editor for many helpful comments and suggestions. This research was supported by the Suam Foundation Research Grants.Received: October 2001     

Analysis of ordered categorical data from repeated measurements assuming a quantitative latent variable

Summary The purpose of the present paper is to propose an analytical method for ordered categorical responses obtained from a repeated measurement/longitudinal experiment. The ordered categorical scale is assumed to be a manifestation of a latent quantitative variable. A linear model is assumed for location parameters of the underlying distributions. Weighted least square method is applied to parameter estimation and subsequent analysis. Two data sets are analyzed to show several aspects of analysis by the proposed model and to discuss comparative characteristics of analysis compared with earlier analysis. A mention is made for a computer software program for the proposed model.     

Some properties of repeated hits after first explosion for birth and death processes

Of repeated hits and repeated explosions after first explosion for a birth and death process with explosion some properties are investigated. The properties of repeated hits after first explosion may be expressed by the properties of the first hit after the first explosion. Project supported by the National Natural Science Foundation of China (Grant No. 19761028) and the Centre of Researching Mathematics and Forstering Higher Talent, the Ministry of Education of China.     

Probabilistic Analysis of Condition Numbers for Linear Programming

In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C _R(A) introduced by Renegar (Ref. 2).     

重复n人随机合作对策的核心

以Su ijs等人(1995)引入的随机合作对策的模型为基础,建立了重复n人随机合作对策的理论,定义了重复n人随机合作对策的支付序列以及支付序列的优超关系,并由此给出了重复n人随机合作对策的核心、超可加性和凸性的定义,并讨论了该核心的一些特征和性质.     

3-player repeated games with lack of information on one side

We study the existence of uniform equilibria for three-player repeated games with lack of information on one side and perfect observation. If there are only two states of nature, a completely revealing or a joint plan equilibrium always exists. This is not the case for larger spaces of states. Final version June 2001     

The asymptotic validity of invariant procedures for the repeated measures model and multivariate linear model

Fairly general sufficient conditions are given to guarantee that invariant tests about means in the multivariate linear model and the repeated measures model have the correct asymptotic size when the normal assumption under which the tests are derived is relaxed. These conditions are the same as Huber's condition which guarantees asymptotic validity of the size of the F-test for the univariate linear model.     

A bi-unique transformation into integers of identifiers and other variable-length items

A simple algorithm is given for transforming variable-length items (such as identifiers) bi-uniquely into fixed-length integers, which are more easily accomodated by computer programs. The technique is especially useful when programming assemblers and compilers but may also find application in other areas of data processing.     

A family of balanced incomplete‐block designs with repeated blocks on which general linear groups act

We give two constructions of a balanced incomplete‐block design discovered by van Lint: the design has parameters (13,39,15,5,5), and has repeated blocks and an automorphism group of order 240. One of these methods can be generalized to produce a large class of designs with the properties of the title. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).