key: cord-0044138-oi17m6gu
authors: Ekaba Bisong, O.; John Oommen, B.
title: Optimizing Self-organizing Lists-on-Lists Using Transitivity and Pursuit-Enhanced Object Partitioning
date: 2020-05-06
journal: Artificial Intelligence Applications and Innovations
DOI: 10.1007/978-3-030-49161-1_20
sha: f0777f3ea7efe3fb0771e91598633df19a35a28f
doc_id: 44138
cord_uid: oi17m6gu

The study of Self-organizing lists deals with the problem of lowering the average-case asymptotic cost of a list data structure receiving query accesses in Non-stationary Environments (NSEs) with the so-called “locality of reference” property. The de facto schemes for Adaptive lists in such Environments are the Move To Front (MTF) and Transposition (TR) rules. However, significant drawbacks exist in the asymptotic accuracy and speed of list re-organization for the MTF and TR rules. This paper improves on these schemes using the design of an Adaptive list data structure as a hierarchical data “sub”-structure. In this framework, we employ a hierarchical Singly-Linked-Lists on Singly-Linked-Lists (SLLs-on-SLLs) design, which divides the list data structure into an outer and inner list context. The inner-list context is itself a SLLs containing sub-elements of the list, while the outer-list context contains these sublist partitions as its primitive elements. The elements belonging to a particular sublist partition are determined using reinforcement learning schemes from the theory of Learning Automata. In this paper, we show that the Transitivity Pursuit-Enhanced Object Migration Automata (TPEOMA) can be used in conjunction with the hierarchical SLLs-on-SLLs as the dependence capturing mechanism to learn the probabilistic distribution of the elements in the Environment. The idea of Transitivity builds on the Pursuit concept that injects a noise filter into the EOMA to filter divergent queries from the Environment, thereby increasing the likelihood of training the Automaton to approximate the “true” distribution of the Environment. By taking advantage of the Transitivity phenomenon based on the statistical distribution of the queried elements, we can infer “dependent” query pairs from non-accessed elements in the transitivity relation. The TPEOMA-enhanced hierarchical SLLs-on-SLLs schemes results in superior performances to the MTF and TR schemes as well as to the EOMA-enhanced hierarchical SLLs-on-SLLs schemes in NSEs. However, the results are observed to have superior performances to the PEOMA-enhanced hierarchical schemes in Environments with a Periodic non-stationary distribution but were inferior in Markovian Switching Environments.

Research in self-organizing lists is aimed at mitigating the worst-case linear cost of list retrieval by adaptively rearranging the list nodes in response to query accesses from a Non-Stationary Environment (NSE). This paper optimizes the singly linked-list data structure. The models of NSEs are covered in Sect. 3.1. The goal of the rearrangement is to move towards the head of the list, elements that are more frequently accessed. This has the result of improving the asymptotic average cost of retrievals. However, this action requires information of the "unknown" probability distribution of the Environment. The Environment has a dependency property where element O i is not conditionally independent of O j ,

This property is called "locality of reference". Queries are requests coming from the Environment to retrieve elements from the data structure.

The asymptotic cost is an empirical measure for assessing the algorithmic performance of the list re-organization strategies [1] . This is performed by implementing the corresponding strategy, and taking an ensemble average of the averages of the cost as the algorithm converges. Since the schemes are ergodic (meaning that they have a final solution that is independent of the starting states of a Markov chain), they can be seen to provide an accurate estimation of the asymptotic cost.

The formal expression for the asymptotic cost of an adaptive strategy, A, is given as:

In Eq. (1) and Eq. (2), the expression P {π j } A represents the steady-state (or stationary) probability of choosing the list permutation π j in the Markov chain that involves the adaptive strategy, A. Further, C(π j ) is the ordering cost or the average-access cost of the list permutation π j . For more mathematical details on the asymptotic cost and Markov chains, the reader is directed to [1, 5] .

The de facto schemes for list self-organization in NSEs are the Move To Front (MTF) and Transposition (TR) rules. In the MTF update scheme, the queried element is moved to the list head, except when it is the first element, because, in that case, it is already at the head (Fig. 1) . As opposed to this, in the TR adaptive scheme, if the queried element is not already at the list head, it is moved one position towards the front of the list (Fig. 2 ). Another deterministic scheme for self-organization in NSEs is the Frequency Count (FC) scheme. The FC rule maintains an accumulator for recording the access frequencies of the list elements. The resulting list is re-arranged according to the descending order of the counters. This relatively simple scheme yields rather impressive results with regard to its asymptotic cost being close to optimal, and its amortized cost being about two times the optimal cost [4] . Notwithstanding, the FC scheme has some obvious drawbacks, the first being that the memory cost scales poorly for large lists [12] . Secondly, in environments exhibiting "locality of reference", the FC scheme yields an unacceptable performance [11, 15] .

The MTF and TR rules are of greater interest to this work for two reasons. The first being that they have been shown to empirically out-perform the other schemes [2] , and the second, that the time and space complexities involved in implementing other surveyed schemes render most of them impractical for realworld settings. It is for these sort of Environments with dependent query accesses that this present work seeks to provide novel solutions.

Indeed, while these schemes (MTF, TR, FC) show superior performances in minimizing the asymptotic average-cost of Singly-Linked-Lists (SLLs) in NSEs [13] , they, however, suffer peculiar drawbacks in NSEs exhibiting "locality of reference". An empirical analysis of TR responding to query accesses from different probability distributions shows that TR outperforms MTF for the Zipf's distribution [17] , and the results of [9] showed that the asymptotic cost of TR outperforms MTF for the Lotka, exponential, linear, and 80-20 probability distributions. However, the MTF has a faster adaptive rate and quickly converges early-on in the algorithm's execution [8] .

This work combines the MTF and TR rules to take advantage of the quick updates of the MTF rule and the asymptotically stable convergence of the TR rule in designing our improved hierarchical adaptive strategies. This design led to the hierarchical Singly-Linked-Lists on Singly-Linked-Lists (SLLs-on-SLLs) variations of the MTF-MTF, MTF-TR, TR-MTF and TR-TR schemes, where the first component is the rule governing the list outer-context and the second component is the rule for the list inner-context [1] .

However, the hierarchical SLLs-on-SLLs configuration as-is results in a certain static ordering of the elements within the inner sublist context. This presupposed static ordering carries the "false" assumption that there exists a probabilistic dependence between the elements in the sublist. In reality, the initial elements within a sublist are due to an arbitrary permutation. Hence, it turns out that the performance of the vanilla hierarchical SLLs-on-SLLs is worse of than the MTF and TR in NSEs [1, 6] .

This static pre-supposed ordering is relaxed by the introduction of a reinforcement learning update scheme from the theory of Learning Automata (LA) called the Object Migration Automaton (OMA). The OMA algorithm is designed to learn the probabilistic dependence of elements in the Environment. This information is used to update the elements contained in the hierarchical sublist context represents their dependence ordering in the Environment. This formulation led to the OMA-hierarchical SLLs-on-SLLs consisting of the MTF-MTF-OMA, MTF-TR-OMA, TR-MTF-OMA and TR-TR-OMA schemes [1] .

However, the OMA suffers from the "deadlock" problem 1 which occurs when an accessed element is swapped from one action to another and then back to the original action and thus prevented from converging to their optimal ordering (this concept is further explained in Sect. 2.2). To mitigate this, the Enhanced Object Migration Automaton (EOMA) was introduced by [10] that imposes conditions to restrict unnecessary swaps on action-state boundaries as well as to redefine the convergence criteria to when the automaton is in the two-innermost states as the "final" states instead of when the automaton is in the innermost state.

Bisong and Oommen [6] employed the EOMA reinforcement scheme in designing the EOMA-augmented hierarchical SLLs-on-SLLs which resulted in superior performances to the de facto MTF and TR schemes and the OMAaugmented hierarchical schemes in NSEs. Further, the work by [7] further improved the performance of the hierarchical SLLs-on-SLLs by incorporating the PEOMA reinforcement scheme. The PEOMA algorithm by [18] employed the Pursuit concept to filter divergent query pairs from the Environment. To the best of our knowledge, the work by [7] is currently the state-of-the-art for self-organizing lists in NSEs.

This paper further explores the state of the art by incorporating the concept of Transitivity in the PEOMA algorithm, that is the Transitivity Pursuit-Enhanced Object Migration Automaton (TPEOMA) to design a TPEOMAaugmented hierarchical SLLs-on-SLLs. This proposed hierarchical formulation consists of the MTF-MTF-TPEOMA, MTF-TR-TPEOMA, TR-MTF-TPEOMA and TR-TR-TPEOMA schemes. The Transitivity concept is used to infer "dependent" queries from the Environment to further train the automaton to approximate its "unknown" distribution. The Transitivity concept is discussed in more detail in Sect. 2.3.

The novel contributions of this paper include:

-The design and implementation of the TPEOMA-enhanced SLLs-on-SLLs; -Demonstrating the superiority of the TPEOMA-augmented hierarchical schemes to the MTF and TR rules and to the original OMA-augmented schemes that pioneered the idea of a hierarchical LOL approach; -Demonstrating the superiority of the TPEOMA-augmented hierarchical schemes to the EOMA-augmented hierarchical schemes; -Highlighting the performances of the TPEOMA-augmented hierarchical schemes to the PEOMA variants; -Showing that the "Periodic" and "UnPeriodic" versions of the TPEOMAaugmented hierarchical schemes yielded superior and comparable performances respectively in PSEs to those without such additions.

Section 1 introduces the idea of a hierarchical SLLs-on-SLLs for minimizing the asymptotic average case for list retrieval in NSEs. It also lays out the case for incorporating the OMA-family of reinforcement schemes for learning the probability dependence distribution of elements in the Environment. Section 2 reviews the theory of LA 2 as the foundational theory for the TPEOMA reinforcement scheme. In addition, this section accesses the idea of the Transitivity concept that builds on the Pursuit concept in the PEOMA algorithm. Section 3 explains the design of the TPEOMA-augmented hierarchical SLLs-on-SLLs for NSEs. Section 4 presents the Results and Discussions, and Sect. 5 concludes the paper.

Learning automata (LA) arose in the Soviet Union in the 1960s by Tsetlin as a computational adaptive scheme for learning. [20] The LA task can be modeled by means of a feedback loop between the Environment and the automaton. The automaton interacts with the Environment by choosing from a set of actions based on the feedback it receives from the Environment. The LA model is set up as an adaptive process [3] in which little or no information is known a priori about the Environment. The goal of the learner (the LA) is then to learn the optimal action that maximizes a utility function or improves a performance index [1, 5, 18 ].

The OMA improves on the Tsetlin/ Krinsky strategies for partitioning objects into groups in the Equal-Partitioning Problem (EPP) [16] . In the OMA, the number of actions represents the number of groups, or partitions, R, where each action contains a set number of states, N . The OMA partitions the object group W into R partitions by moving the abstract objects O around the action-states of the automaton. To learn more about the OMA algorithm the reader is referred to [5] [6] [7] 18] .

The EOMA algorithm improves on the OMA to mitigate the inability of the OMA algorithm to converge due to a "deadlock" scenario. The deadlock scenario occurs when there is a query pair O i , O j in a stream of query pairs belonging to different actions, α h and α g . If one object is in the boundary state of its action, and the other is not, the query pairs are prevented from converging to their optimal ordering, and this can lead to an "infinite" loop scenario. The boundary state of the OMA is the outermost memory state of an action α (see Fig. 3 ). To learn more about the EOMA algorithm the reader is referred to [5] [6] [7] 18] .

To resolve the deadlock scenario for the query pair O i , O j , let us say that there exists an object in the boundary state of the action-group, α g containing O j , given that the other element O i is not in the boundary state of its action-group α h . The EOMA moves moves O j from action-group α g to be in the boundary state of action-group, α h . By taking this step, the partitions become unequal. To regain the equi-partitioning, the object that is closest to O i in α h , which we will call O l , is moved to the boundary state of α g .

Hence, given a set of query elements, the transitions of the EOMA for the abstract objects O i , O j on reward and on penalty are illustrated in Fig. 3 . In addition, the EOMA also modifies the convergence criteria to reduce its vulnerability to divergent queries by setting the two-innermost states as the "final" states, as opposed to just the innermost state in the vanilla OMA.

To learn more about how the EOMA algorithm mitigates the "deadlock" scenario in the OMA, the reader is referred to [5] [6] [7] 18 ].

The Pursuit concept is incorporated into the EOMA design to filter divergent queries from the Environment using Maximum Likelihood Estimates (MLEs). It works by updating the joint query probabilities using ranked estimates of the reward probabilities to asymptotically choose or "pursue" better actions. For a detailed discussion of the pursuit concept, the reader is referred to [18] . The Pursuit-EOMA scheme was the best-known object-partitioning algorithm until the authors of [19] introduced the TPEOMA.

The TPEOMA algorithm is based on the observation that the Pursuit matrix can also be used to infer underlying relations in the Environment [18] . It then invokes a policy that spins off reward/penalty operations by incorporating the statistics obtained between objects that have been previously accessed. The Pursuit matrix M is defined as a W R × W R matrix whose element The reader is referred to [19] for a details analysis of the Pursuit matrix.

When an estimate of the Pursuit matrix is obtained, the transitivity property can be used to infer queries to further train the automaton to learn the model of dependence of the Environment. In other words, if the current query received from the Environment is O i , O j and O j is in relation with O k , k ∈ {1, · · · , W j }, k = i, we can infer that O i is also in a relation with O k , where i, j, and k are the indices of the entries in the Pursuit matrix. Thus, given the transitivity threshold, τ T , which is a suitable user-defined threshold which is set to a value 1 W 2 −W , where W is the number of elements in the list. We can assert that P ij > τ T ∧ P jk > τ T ⇒ P ik > τ T . This means that if i and j, and i and k are also accessed together often, it is also likely that i and k are also accessed together often. The transitivity relation is illustrated in Fig. 4 . The reader is referred to [19] for a thorough analysis of the Transitivity property in the TPEOMA algorithm. 

The concept of a hierarchical data "sub"-structure involves dividing a list of size W into k sub-lists. The re-organization strategy is then hierarchically applied to the list by first considering the elements within the sub-list (also called the sub-context) and then operating over the sublists (or sub-contexts) themselves.

The re-organization strategies involved are the MTF and TR rules. When used in a hierarchical scheme, this yields MTF-preceding-MTF, (MTF-MTF), MTF-preceding-TR, (MTF-TR), TR-preceding-MTF, (TR-MTF), and TR-preceding-TR, (TR-TR) schemes. For example, in the case of MTF-TR, the element within a sub-context is first moved to the front of the list, and then the subcontext is moved to the front of the list context. Again, the fundamental idea of combining the MTF and TR schemes in this hierarchical formulation is principally to take advantage of the fast convergence properties of the MTF rule and the more accurate asymptotic convergence of the TR rule.

In NSEs with "locality of reference", let us assume that query accesses m are made to a sub-context (or local context) Q a . For a given query access m i from Q a , the probability that the next query access, m j will come from the same local context, Q a is high. Hence, it is useful to take advantage of this dependency relationship by moving the entire sublist of elements of the sub-context en masse towards the head of the list to cut-down the access-time cost when an element within the sub-context Q a is requested. The hierarchical schemes mentioned above are preferred in Environments characterized by such a "locality of reference". Observe that the stand-alone MTF will require at least J k distinct requests to promote the entire sub-context to the head of the list.

Further, if a record m u is accessed that is not in the re-organized sub-context, the hierarchical schemes will promote en masse all records that are part of m u 's sub-context towards the head of the list thereby reducing the subsequent access costs. As opposed to this in the MTF and TR schemes, for example, the entire context is promoted towards the list head one record at a time.

In the TPEOMA-Augmented Hierarchical SLLs-on-SLLs, the Transitivity phenomenon, included in the TPEOMA, takes advantage of the statistical distribution of the queried elements to infer good query pairs from non-accessed elements in the transitivity relation. Both of these are used to improve the dependence-capturing aspect to be included in the sub-lists when it concerns the Lists-on-Lists hierarchy. The augmentation of hierarchical SLLs with the TPEOMA reinforcement scheme gives rise to the MTF-MTF-TPEOMA, MTF-TR-TPEOMA, TR-MTF-TPEOMA and the TR-TR-TPEOMA.

In NSEs, the penalty probabilities for each action vary with time. In the context of adaptive data structures, this variation affects the expected query cost because the Environment exhibits the so-called "locality of reference", or is characterized by dependent accesses. The "locality of reference" occurs when there exists a probabilistic dependence between the consecutive queries [2] . In other words, there is a considerably small number of distinct or unrelated queries within a segment of the access sequence.

To initiate the design of adaptive data structures in NSEs, we introduce and examine two dependent query generators for simulating an Environment producing queries with dependent accesses. They are the Markovian and Periodic query generators. Given a set of n distinct elements, if we split it into k disjoint and equal partitions with m elements where n = k.m, the k subsets can be considered to be local or "sub"-contexts. The elements within a sub-context k i exhibit "locality of reference". This implies that if an element from set k i is queried at time t, there exists a high likelihood that the next queried element at time t + 1 will also arrive from the same set k i . In other words, the Environment itself can be seen to have a finite set of states {Q i |1 ≤ i ≤ k}, and the dependent model defines the transition from one Environmental state to another.

The Environment generates queries according to a probability distribution. In recording the behaviour of the hierarchical list schemes proposed in this work, we considered five different types of query distributions, namely, the Zipf, Eighty-Twenty, Lokta, Exponential and Linear distributions. For a given list of size W , divided into k sub-lists, with each sub-list containing W k elements, the probability distribution {s i } where 1 ≤ i ≤ m describes the query accesses for the elements in the subset k. Notice that in this way, the total probability mass for the query accesses in each group is the same, and the distribution within each group has the respective distribution.

A rationale for conducting the simulations with these query distributions is that, for the most part, they result in "L-shaped" graphs. This is true in particular, for the Exponential and Lotka distribution, and to an extent for the Zipf distributions. Such "L-shaped" distributions assign high probabilities to a small number of the sub-list elements. By working in this manner, we can compare our hierarchical variants against the MTF and TR schemes, which were the de facto schemes for adaptive lists in NSEs.

The experimental setup for the simulations involving the TPEOMA-augmented hierarchical schemes in MSEs involved splitting a list of size 128 into k sublists with k ∈ 2, 4, 8, 16, 32, 64. The degree of dependence of the MSE, α, was set to 0.9 and the period for the PSE, T = 30. For all the results discussed in this section, the simulation involved an ensemble of 10 experiments, each evaluating 300, 000 query accesses, and for the various aforementioned query generators. For conciseness sake, we present results for k = 8.

From Table 1 , when k = 8, we observed that the TPEOMA-augmented hierarchical schemes were superior to the MTF and TR standalone schemes for all query distributions in the MSE. As an example in the Lotka distribution, the asymptotic and amortized costs for the MTF-MTF-TPEOMA, MTF-TR-TPEOMA, TR-MTF-TPEOMA and TR-TR-TPEOMA were (6.60, 6.11, 4.39, 4.37) and (8.09, 7.84, 6.57, 6.54) respectively. As opposed to this, the corresponding asymptotic and amortized costs for the MTF and TR were significantly higher at (39.30, 48.25) and (39.17, 48.66) respectively. Further, in the Exponential distribution for the MSE, the MTF-MTF-TPEOMA, MTF-TR-TPEOMA, TR-MTF-TPEOMA and TR-TR-TPEOMA had asymptotic and amortized costs of (7.01, 6.99, 7.50, 7.64) and (8.98, 8.83, 9.66, 9.87 ), while the MTF and TR rule had asymptotic and amortized costs of (8.72, 10.52) and (8.71, 10 .93) respectively. Hence, showing the superiority of the TPEOMA-augmented schemes to the MTF and TR rules respectively in the MSE. Also, from Table 1 , observe that while the TPEOMA-augmented hierarchical schemes are superior to the EOMA-augmented hierarchical schemes, the PEOMA-augmen-ted hierarchical still boasts superior performances in MSEs. the MTF-MTF-TPEOMA, MTF-TR-TPEOMA, TR-MTF-TPEOMA and TR-TR-TPEOMA Also, when the knowledge of the Periodic state change is passed to the TPEOMA-augmented hierarchical schemes, we observed that the "periodic" variations yielded superior performances to their vanilla versions, whereas the unperiodic variations had comparable performances to the vanilla versions.

From Fig. 6 , we see that the TPEOMA-augmented hierarchical schemes were superior to the MTF and TR schemes in noisy Environments when the dependence degree α > 0.2. Actually, when α = 0.2, the TPEOMA enhanced schemes already displayed comparable (and in some cases better) performances to the MTF and TR schemes for the Zipf distribution.

In this paper, we designed a TPEOMA-augmented hierarchical Singly-Linked-Lists on Singly-Linked-Lists (SLLs-on-SLLs) using reinforcement learning schemes from the theory of Learning Automata, which led to the MTF-MTF-TPE-OMA, MTF-TR-TPEOMA, TR-MTF-TPEOMA and TR-TR-TPEOMA schemes. The TPEOMA-augmented hierarchical schemes showed superior performances to the standalone MTF and TR schemes in MSEs. Also, they are superior to the EOMA-augmented hierarchical schemes. However, the PEOMAaugmented hierarchical schemes are still superior to the TPEOMA-augmented hierarchical schemes in the MSE. In the PSE, the TPEOMA-augmented hierarchical were for the most part superior to the MTF and TR schemes for the query distributions under consideration. Further, the TPEOMA-augmented schemes were also superior to the EOMA-augmented and PEOMA-augmented hierarchical schemes in the PSE. However, when the knowledge of the periodic state change were incorporated to the hierarchical schemes, the "periodic" case had superior performances to their vanilla versions while the "unperiodic" case had comparable performances.

Adaptive list organizing strategies for non-stationary distributions

On the competitive theory and practice of online list accessing algorithms

Adaptive Control Processes: A Guided Tour

Amortized analyses of self-organizing sequential search heuristics

On designing adaptive data structures with adaptive data "sub"-structures. Master's thesis

Optimizing self-organizing lists-on-lists using enhanced object partitioning

Optimizing self-organizing lists-on-lists using pursuitoriented enhanced object partitioning

Optimality of move-to-front for self-organizing data structures with locality of references

Time reversible self-organizing sequential search algorithms

Improvements to an algorithm for equipartitioning

Self-organizing linear search

The Art of Computer Programming

On serial files with relocatable records

Learning Automata: An Introduction

Generalized swap-with-parent schemes for self-organizing sequential linear lists

Deterministic learning automata solutions to the equipartitioning problem

On self-organizing sequential search heuristics

Novel solutions and applications of the object partitioning problem

The advantages of invoking transitivity in enhancing pursuit-oriented object migration automata

Finite automata and models of simple forms of behaviour

Zipf In Table 2 , the performance of the TPEOMA-augmented hierarchical schemes in the PSEs were superior to the standalone MTF and TR rules for all distributions under consideration except for the Exponential scheme which boasted slightly comparable results. As an example, consider the 80-20 distribution where