© 1994 by British Computer Society
A New Technique for Enhancing Linked-List Data Retrieval: Reorganize Data Using Artifically Synthesized Queries
School of Computer Science, Carleton University, Ottawa K1S 5B6, Canada
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.
Received August 1993. revised June, 1994.
* School of Computer Science, Carleton University, Ottawa K1S 5B6, Canada