Let R = {R1, R2, …, RN} be a set of data elements. The elements of R are accessed by the users of the system according to a fixed but unknown distribution S = {s1, s2, …, sN}, referred to as the users' query distribution. In this paper we consider the problem of organizing data so as to optimize its retrieval. However, rather than organize the data according to Q, the stream of queries presented by the user, we suggest a scheme by which the data is organised based on a synthesized query stream Q′. This synthesized stream possesses an underlying distribution, S′. Thus, in effect, the data organization is achieved according to the distribution S′ and so, in one sense, the user's query distribution is modified without his knowing it. Furthermore, we show how this transformation can be done in such a way that the data storage achieved according to S′ will be superior to that achieved if the data was stored according to the distribution S. The module which achieves this transformation is called a Distribution Changing Technique (DCT) Filter. In this paper we shall present the theory of DCT filters in its mathematical generality. We shall show that a DCT filter can be represented as Stochastic Mealy Automation. Various DCT filters will be catalogued and, in particular, a filter F* will be presented. It has been shown that this filter transforms the original distribution expediently, and thus accentuates the information contained in the user's distribution. The problem of cascading DCT filtes has also been studied, and extensive computational and simulation results have been included which justify the theoretical results which have been presented.

Consider a set A=(A/sub 1/,A/sub 2/,. . ., A/sub n/) of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities S=(s/sub 1/,s/sub 2/,. . ., s/sub N/) and are to be arranged lexicographically using a binary search tree (BST). If S is known a priori, it is well known that an optimal BST may be constructed using A and S. The case when S is not known a priori is considered. A new restructuring heuristic is introduced that requires three extra integer memory locations per record. In this scheme, the restructuring is performed only if it decreases the weighted path length (WPL) of the overall resultant tree. An optimized version of the latter method, which requires only one extra integer field per record has, is presented. Initial simulation results comparing this algorithm with various other static and dynamic schemes indicates that this scheme asymptotically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes reported in the literature.>

Consider a learning machine (LM) interacting with an environment epsilon . The environment offers the machine M actions. Traditionally, learning systems endeavor to compute the best action that the environment offers, and this is done without any estimation procedure. In this paper, we consider the problem of the LM computing not only the optimal action offered but also the ordering of the actions in terms of their optimality. The problem is posed in its generality and various norms of learning in this setting are formalized. Also various learning strategies are presented that use a new mathematical model called the random race. In this model the learning is modeled using M racers that are running toward a goal. At each instant, racer R/sub i/ moves toward the goal with a probability of s/sub i/ and stays where he is with a probability of (1-s/sub i/). In the simplest learning model, the learning multiple race track (LMRT) model, the racers run on multiple tracks, and in this scenario, each racer has his own track, thus disallowing interference between the racers. However, in a more general setting, the learning single race track (LSRT) model, the racers run on a single track, and in this case, interferences between racers are specified in terms of overtaking rules. In this paper, we first examine the learning multiple race track (LMRT) model, and we have shown that in the absence of a priori information the LMRT is permutationally epsilon -optimal in all suggestive random environments. Other results are proven or conjectured.>

The class of memoryless heuristics for maintaining a Doubly-Linked List in an approximately optimal order is studied. Two mappings that relate Singly-Linked List and Doubly-Linked List heuristics are defined, and theorems involving these mappings are presented. A new heuristic referred to as the Swap heuristic for the Doubly-Linked List is introduced, and its asymptotic distribution has been derived.

Let R = {R1, R2, …, RM} be an ordered set of M elements where Ri < Rj whenever i < j. Let π be the set of permutations of R. We consider the problem of randomly generating the elements of π according to a distribution G(π). Various algorithms including those due to Durstenfeld3,5 and Moses et al7 are available for the case when the distribution G(π) is a uniform distribution (i.e., where all the elements of π are generated with equal probability). In this paper we consider the case when the distribution G(π) is not necessarily uniform. We present a strategy for specifying the distribution G(π) and propose a technique for generating the elements of π according to the distribution G(π). Applications of the technique to generate ‘almost sorted lists’ and in the Travelling Salesman Problem have been presented. Finally, simulation results have been included which demonstrate the power of the Random Permutation Generation (RPG) technique.