Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Structure to Optimize Depth-First And Breadth-First Record Sorting

IP.com Disclosure Number: IPCOM000119950D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 72K

Publishing Venue

IBM

Related People

Austin, JH: AUTHOR [+3]

Abstract

Disclosed is an encoding technique for hierarchically structured sequential records which uses a record prefix that allows the records to be easily sorted into a depth-first or breadth-first order.

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

Structure to Optimize Depth-First And Breadth-First Record Sorting

      Disclosed is an encoding technique for hierarchically
structured sequential records which uses a record prefix that allows
the records to be easily sorted into a depth-first or breadth-first
order.

      Assume a collection of records.  The records are stored
sequentially in random order, but they fit into some type of
hierarchical relationship, as shown in Fig. 1.

      Depth token is a fixed-length data structure associated with
each record that specifies at what level the record appears in the
hierarchy.  If one level A is situated above level B in the
hierarchy, then the depth token for level A will be less than the
depth token for level B.

      For this example, the highest level will have a depth token
value of 0, the next level 1, etc.  In Fig. 1, record REC_Z would
have an associated depth token of 0; REC_B, REC_Q and REC_C would all
have depth tokens of 1; REC_D, REC_E, REC_V and REC_I would all have
depth tokens of 2; REC_S, REC_L and REC_A would all have depth tokens
of 3.

      Correlator string is a variable length data structure
associated with each record that specifies that record's place in the
hierarchy.  The correlator string for any record is the correlator
string of its parent, appended with a token indicating this record's
position within a left-to-right ordering of its siblings.  A record's
token will be greater than any sibling to its left, but less than any
sibling to its right.

      For this example, the highest level record will have a
correlator string of 'a' and all sibling records will be enumerated
'a', 'b', 'c', etc.  Fig. 2 shows the depth tokens and correlator
strings for the hierarchy presented in Fig. 1.

      As each record is generated, it should have the concatenation
of the depth token with the correlation string added to each record.
The records can easily be sorted into either a depth-first or
breadth-first sequential ordering by only changing the definition of
the sort comparison field and function.  No record data needs to be
modified or re-arranged to create t...