Browse Prior Art Database

Implementation and Application of the Search-Insert-Sort Matrix

IP.com Disclosure Number: IPCOM000119180D
Original Publication Date: 1997-Dec-01
Included in the Prior Art Database: 2005-Apr-01

Publishing Venue

IBM

Related People

Tran, TM: AUTHOR

Abstract

Disclosed is a Design and Implementation of Search-Insert-Sort-Matrix (SISM) Algorithm. The algorithm is implemented with a thread safe and it can be used to apply on any databases and resources.

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

Implementation and Application of the Search-Insert-Sort Matrix

      Disclosed is a Design and Implementation of
Search-Insert-Sort-Matrix (SISM) Algorithm.  The algorithm is
implemented with a thread safe and it can be used to apply on any
databases and resources.

      The SISM algorithm is implemented based on two linked
lists.  The first linked list is called the Row Linked List.  The
second linked list is called the Column Linked List.  The Row Linked
List contains the Rowdata which is the data type of the resource's
member and  a double Linked List to manage the traverse order of the
records in each  column.  The Column Linked List contains the
following members:
  o  The K, the data type of the member's property
  o  The *CS, the current pointer in each column
  o  The *Head, the pointer points to the head of each column
  o  The *Tail, the pointer points to the tail of each column
  o  The Head_Set, the flag which is set when Head pointer is
      set to *CS
  o  The Tail_Set, the flag which is set when Tail pointer is
      set to *CS

      In the Row Linked List, we introduce the double Linked List
(*Next and *Prev pointers) to allow the Application Programs to
traverse the records in each column forward and backward as desired.
In the Column Linked List, *CS pointer is used to point to the
current record  in each column and it serves as an index pointer.
The *Head and *Tail  pointers are used for traversing purposes, e.g.,
the starting points.  The Head_Set and Tail_Set flags are used to
keep track of the  *Head and *Tail pointers in each column.  Without
these flags, the algorithm would not be able to retrieve the members
when a searching is  made.  In addition, one global pointer is also
used.  It is called *CPTR  and it is used to point to the head of the
Column Linked List.

In general, the SISM algorithm consists of three parts:
  1.  The first part is to obtain the members of the resource
       and build the nxm matrix.
  2.  The second part is to search and insert the members into
       the nxm matrix.
  3.  The third part is to retrieve the members from the nxm
       matrix.

      To obtain the members of the resource and build the nxm matrix,
SISM opens the resource, reads one member at a time, then converts
the MEMBER{i} into SISM{n,m} coordinate depending on the property
value. For  example, the super set S can be built into SISM matrix,
as shown in Fig. 1.

      Once a member is obtained, it is passed to the "search and
insert" routine to search and insert it into the nxm matrix.  The
search starts at the first coordinate of the nxm SISM matrix which is
SISM{1,1}.  If the member that contains the property did not match
any property of the existing members in the Column Linked List, the
comparison is made to the next coordinates, e.g., SISM{1,2},
SISM{1,3}, etc.  Thus, the searching routine will return either a
matching SISM{1,j...