On Designing Adaptive Data Structures with Adaptive Data "Sub"-Structures

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Bisong, Ekaba Ononse




This thesis proposes the use of "Adaptive" Data-Structures (ADSs) that invoke reinforcement learning schemes from the theory of Learning Automata (LA). The ADSs work in conjunction with select re-organization rules to update themselves as they receive queries from the Environment. The result of such a process is to minimize the cost of 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 SLLs, which contains outer and sub-list contexts. The Object Migration Automaton (OMA) family of reinforcement schemes are employed to capture the probabilistic dependence of the elements query accesses from the Environment within sub-lists. The Enhanced-OMA (EOMA), the Pursuit-EOMA (PEOMA), and the Transitivity-PEOMA (TPEOMA) are incorporated into the hierarchical SLLs. The results are currently the state-of-the-art methods for SLLs operating in NSEs.


Computer Science
Artificial Intelligence




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).