Optimizing Self-organizing Lists-on-Lists Using Enhanced Object Partitioning

摘要

The question of how to store, manage and access data has been central to the field of Computer Science, and is even more pertinent in these days when megabytes of data are being generated every second. This paper considers the problem of minimizing the cost of data retrieval from the most fundamental data structure, i.e., a Singly-Linked List (SLL). We consider a SLL in which the elements are accessed by a Non-stationary Environment (NSE) exhibiting so-called 'Locality of Reference'. We propose a solution to the problem by designing an 'Adaptive' Data Structure (ADS) which is created by means of a composite of hierarchical data 'sub'-structures to constitute the overall data structure. In this paper, we design an hierarchical Lists-on-Lists (LOLs) by assembling a SLL into an hierarchical scheme that results in a Singly-Linked List on Singly-Linked Lists (SLLs-on-SLLs) comprising of an outer-list and sublist context. The goal is that elements that are more likely to be accessed together are grouped within the same sub-context, while the sublists themselves are moved 'en masse' towards the head of the list-context so as to minimize the overall access cost. This move is carried-out by employing the 'de-facto' list re-organization schemes, i.e., the Move-To-Front (MTF) and Transposition (TR) rules. To achieve the clustering of elements within the sublists, we invoke the Object Migration Automaton (OMA) family of reinforcement schemes from the theory of Learning Automata (LA). They are introduced so as to capture the probabilistic dependence of the elements in the data structure as it receives query accesses from the Environment. In this paper, we show that SLLs-on-SLLs augmented with the Enhanced Object Migration Automaton (EOMA) minimizes the retrieval cost for elements in NSEs and are superior to the stand-alone MTF and TR schemes, and also superior to the OMA-augmented SLLs-on-SLLs operating in such Environments.