Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-02331323
Contributor : Hal Ifip <>
Submitted on : Thursday, October 24, 2019 - 12:51:10 PM
Last modification on : Thursday, October 24, 2019 - 12:54:39 PM
Long-term archiving on: : Saturday, January 25, 2020 - 4:17:04 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

O. Bisong, B. Oommen. Optimizing Self-organizing Lists-on-Lists Using Enhanced Object Partitioning. 15th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), May 2019, Hersonissos, Greece. pp.451-463, ⟨10.1007/978-3-030-19823-7_38⟩. ⟨hal-02331323⟩

Share

Metrics

Record views

62