Skip to main content

Data structures that re-organize based on queries received from a non-stationary environment

Project description

Adaptive Data Structures SLLs-on-SLLs
=====================================

[![image](https://img.shields.io/pypi/v/ads.svg)](https://pypi.org/project/adaptive-data-structures) [![image](https://travis-ci.org/dvdbisong/Adaptive-Data-Structures-SLLs-on-SLLs.svg?branch=master)](https://travis-ci.org/dvdbisong/Adaptive-Data-Structures-SLLs-on-SLLs) [![Documentation
Status](https://readthedocs.org/projects/ads-ai/badge/?version=latest)](https://ads-ai.readthedocs.io/en/latest/?badge=latest)


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.

<p align="center">
<img src="/docs/images/thesis-update.svg" align="middle" alt="Learning Automata Model." />
</p>

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for adaptive-data-structures, version 0.3.1
Filename, size File type Python version Upload date Hashes
Filename, size adaptive-data-structures-0.3.1.tar.gz (5.2 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page