Adaptive Data Structures SLLs-on-SLLs

This research proposes the use of "Adaptive" Data-Structures (ADSs) that invoke reinforcement learning schemes from the theory of Learning Automata (LA). These operate in conjunction with select re-organization rules to update themselves as they receive queries from the Environment of interaction. The result of such a process is the subsequent minimization of the cost associated with query accesses. The Environments under consideration are those that exhibit a so-called "locality of reference", and are referred to as Non-stationary Environments (NSEs).

A hierarchy of data "sub"-structures is used to design Singly-Linked Lists (SLLs) on Singly-Linked Lists, which contain outer and sub-list contexts. The elements that are more likely to be accessed together are grouped within the same sub-context, while the sub-lists themselves are moved “en masse” towards the head of the list-context by following a re-organization strategy.

The Object Migration Automaton (OMA) family of reinforcement schemes are employed to capture the probabilistic dependence of the elements in the data structure as it receives query accesses from the Environment. The Enhanced Object Migration Automaton (EOMA), the Pursuit Enhanced Object Migration Automaton (PEOMA), and the Transitivity Pursuit Enhanced Object Migration Automaton (TPEOMA) have each been individually incorporated into the hierarchical SLLs. The consequent results are currently the state-of-the-art methods for adaptive SLLs operating in NSEs.