TR-147: On Transparently Modifying Users’ Query Distributions

Abstract

In this paper we introduce a concept which is completely new to the areas of computer science and data manipulation. Let 1 = {R1 ,R2, … , RN} be a set of data elements. The elements of 1 are accessed by the users of the system according to a fixed but unknown distribution ={s1, s2, … , SN}. referred to as the users’ query distribution. The manager of the system organizes the data 1 so as to minimize the cost of retrieving them. Thus, if 1 is maintained as a linear list it is advantageous that the elements of 1 are sorted in the descending order of. the access probabilities. In this paper we consider the problem of transforming the users’ query distribution into a new distribution . The latter transformation is done in a fashion that is transparent to the user. Furthermore, rather than having the manager organize the data according to the distribution he can maintain the data according to the distribution to obtain superior data retrieval characteristics. After posing the problem in its mathematical generality we propose a particular Distribution Changing Technique (OCT) filter and show that it indeed transforms the original distribution expediently. The problem of cascading OCT filters has also been studied and some initial theoretical results have been presented. Numerous computational and simulation results which validity the theoretical results presented have also been included.