Abstract Random minimaxing studies the consequences of using a random number for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. Experiments in Chess showed that the strength of play increases as the depth of the lookahead is increased. Previous research by the authors provided a partial explanation of why random minimaxing can strengthen play by showing that, when one move dominates another move, then the dominating move is more likely to be chosen by minimax. This paper examines a special case of determining the move probability when domination does not occur. Specifically, we show that, under a uniform branching game tree model, whether the probability that one move is chosen rather than another depends not only on the branching factors of the moves involved, but also on whether the number of ply searched is odd or even. This is a new type of game tree pathology, where the minimax procedure will change its mind as to which move is best, independently of the true value of the game, and oscillate between moves as the depth of lookahead alternates between odd and even.

Encrypted deduplicated storage systems face multiple challenges: long-term backup workloads with metadata storage approaching the size of the deduplicated data itself and the disk bottleneck problem caused by fingerprint indexes that will not fit in memory. Resource contention issues may arise when backup loads at peak-time force deduplication of many concurrent backup streams. We propose a system that performs both client and server deduplication. The client forms segments from groups of chunks, enabling coarse-grained client-side deduplication. Deduplicating segment-sized chunks reduces server memory requirements, metadata upload and storage volume but can cause the upload of some previously uploaded data chunks. For longer-term workloads, this redundant upload volume can be offset by the reduced metadata upload volume. On the server, chunk-level deduplication is performed by merge-sorting the fingerprints of multiple clients in a single pass. The server-side deduplication produces high levels of duplicate elimination, and we use index locality to reduce resource contention between concurrent backup streams and significantly reduce disk I/O for indexing. Experiments with two real-world backup datasets using an 8KiB chunk size and 512KiB-4MiB segment sizes reduced server memory requirements by up to 81.6% and metadata storage volume by up to 97.2%. Client to server upload volume ranged from a reduction of 23.9% to an increase of 13.3%. The use of index locality deduplication reduced index I/Os for 2MiB segments to less than 350 per backup generation.

This paper presents an algorithm, ParGenFS, for generalizing, or “lifting”, a fuzzy set of topics to higher ranks of a hierarchical taxonomy of a research domain. The algorithm ParGenFS finds a globally optimal generalization of the topic set to minimize a penalty function, by balancing the number of introduced “head subjects” and related errors, the “gaps” and “offshoots”, differently weighted. This leads to a generalization of the topic set in the taxonomy. The usefulness of the method is illustrated on a set of 17685 abstracts of research papers on Data Science published in Springer journals for the past 20 years. We extracted a taxonomy of Data Science from the international Association for Computing Machinery Computing Classification System 2012 (ACM-CCS). We find fuzzy clusters of leaf topics over the text collection, lift them in the taxonomy, and interpret found head subjects to comment on the tendencies of current research.

The Elo system for rating chess players, also used in other games and sports, was adopted by the World Chess Federation over four decades ago. Although not without controversy, it is accepted as generally reliable and provides a method for assessing players' strengths and ranking them in official tournaments. It is generally accepted that the distribution of players' rating data is approximately normal but, to date, no stochastic model of how the distribution might have arisen has been proposed. We propose such an evolutionary stochastic model, which models the arrival of players into the rating pool, the games they play against each other, and how the results of these games affect their ratings, in a similar manner to the Elo system. Using a continuous approximation to the discrete model, we derive the distribution for players' ratings at timetas a normal distribution, where the variance increases in time as a logarithmic function oft. We validate the model using published rating data from 2007-2010, showing that the parameters obtained from the data can be recovered through simulations of the stochastic model. The distribution of players' ratings is only approximately normal and has been shown to have a small negative skew. We show how to modify our evolutionary stochastic model to take this skewness into account, and we validate the modified model using the published official rating data.

Protein families can be used to reconstruct evolutionary histories of organisms. The accuracy of protein assignment to such families is critical for the success of such studies. Here we investigate the automatic aggregation of motif-defined homologous protein families for further reconstruction of their evolutionary histories. We propose a method that utilises only parameters that can be adjusted by using the data. The building blocks of the method include: (a) a majority rule for combining protein homologous neighbourhood lists into that for a family, and (b) a robust clustering procedure whose only parameter, the similarity shift, can be estimated from information on proteins with known function. The method is applied to a herpesvirus protein dataset leading to insights into the composition of ancestors of herpesvirus superfamilies. Comparison of the computational reconstructions with more comprehensive analyses also show how alignment-based between-protein similarity scoring can be improved by using data on gene arrangements.

Recently several authors have proposed stochastic evolutionary models for the growth of the Web graph and other networks that give rise to power-law distributions. These models are based on the notion of preferential attachment, leading to the “rich get richer” phenomenon. We present a generalization of the basic model by allowing deletion of individual links and show that it also gives rise to a power-law distribution. We derive the mean-field equations for this stochastic model and show that, by examining a snapshot of the distribution at the steady state of the model, we are able to determine the extent to which link deletion has taken place and estimate the probability of deleting a link. Applying our model to actual Web graph data provides evidence of the extent to which link deletion has occurred. We also discuss a problem that frequently arises in estimating the power-law exponent from empirical data and a few possible methods for dealing with this, indicating our preferred approach. Using this approach our analysis of the data suggests a power-law exponent of approximately 2.15 for the distribution of inlinks in the Web graph, rather than the widely published value of 2.1.

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs with n vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. Finally, it is used in an algorithm for solving the symmetric bottleneck travelling salesman problem with probability tending to 1, as n tends to ∞.

We define and characterize orderings of the set of partitions of a positive integer n obtained by traversing the binary tree of the set of partitions of n in each of the three principal orders. Loop-free algorithms for generating the set of partitions in each of these three orders and also in the three corresponding reverse orders are derived. The asymptotic behaviour of each of these six algorithms is examined and compared.

A representation of the partitions of an integer as a binary tree is presented, and the structure of this tree is related to the lexicographic ordering of the set of partitions. The appropriate recursive traversal algorithm for this binary tree immediately yields a recursive algorithm for generating the set of partitions in lexicographic order. Further consideration of the structure of the tree enables us to transform this version of the algorithm into a non-recursive loop-free version. Similar consideration of another recursive traversal algorithm yields corresponding algorithms for generating the set of partitions in a different order.

New lower bounds on the minimal condition numbers of a matrix with respect to both one-sided and two-sided scaling by diagonal matrices are obtained. These bounds improve certain results obtained by F. L. Bauer.