Browse Prior Art Database

A Deterministic Heuristic for Self-Organizing Lists

IP.com Disclosure Number: IPCOM000122987D
Original Publication Date: 1998-Mar-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 36K

Publishing Venue

IBM

Related People

Lai, TW: AUTHOR

Abstract

Disclosed is a method for reducing the average search time of an unordered sequential search list. This method uses an auxiliary array of timestamps to rearrange the search list.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 82% of the total text.

A Deterministic Heuristic for Self-Organizing Lists

      Disclosed is a method for reducing the average search time of
an unordered sequential search list.  This method uses an auxiliary
array of timestamps to rearrange the search list.

      A sequential search list is often implemented by storing the
records in an array.  To reduce the search time, one can employ a
"self-organizing" list that moves frequently used records near the
front of the array.  This invention uses an additional array of
timestamps to guide the rearrangement process.

      Suppose our list is stored in an array A.  Let T be our array
of timestamps.  For each i, we store in the ith element of T, denoted
T(i), the time of the last search of the ith element of A, denoted
A(i).  We maintain the list as follows.

      Search: To search for a record x, compare x with A(1), A(2),
etc. until x is found.  Suppose x is found in position k.  Let K be
the ceiling of k/2; that is, let K be the smallest integer no less
than k/2.  Examine the timestamps T(1), ..., T(K) to determine which
record among the first K was searched least recently; let A(i) be
this record.  Exchange A(i) and A(k), set T(k) to the current value
of T(i), and set T(i) to the current time.

      Insert: To insert a record x in a list of n records, place x
in A(n+1).  Let K be the ceiling of (n+1)/2.  Examine the timestamps
T(1), ..., T(K) to determine which record among the first K was
searched least recen...