US3603937A — Multilevel compressed index generation method and…

Claim 1

Independent Claim 136 words

A method of generating index entries for a high level of multilevel compressed index, including the steps of machine assembling a plurality of boundary pairs of uncompressed keys, each boundary pair being a last and a first uncompressed key in two sequenced groups of uncompressed keys used in the generation of two sequential index blocks at the lowest level of said compressed index, said machine assembling step providing a sequenced high-level group of uncompressed keys, machine assigning pointers to each of said uncompressed key pairs, said pointers representing addresses of compresses index blocks in said lowest level, machine compressing said uncompressed keys in sequence into compressed keys, and machine generating index entries for said high level by a relational positioning of said pointers with respective pairs of said compressed keys provided by saId machine compressing step.

Claim 2

Independent Claim 136 words

A method of generating index entries for a high level of multilevel compressed index, including the steps of machine assembling a plurality of boundary pairs of uncompressed keys, each boundary pair being a last and a first uncompressed key in two sequenced groups of uncompressed keys used in the generation of two sequential index blocks at the lowest level of said compressed index, said machine assembling step providing a sequenced high-level group of uncompressed keys, machine assigning pointers to each of said uncompressed key pairs, said pointers representing addresses of compresses index blocks in said lowest level, machine compressing said uncompressed keys in sequence into compressed keys, and machine generating index entries for said high level by a relational positioning of said pointers with respective pairs of said compressed keys provided by saId machine compressing step.

Claim 3

Dependent Claim 62 words

A method as defined in claim 1 for generating the high-level index, including the steps of machine grouping said boundary pairs of said uncompressed keys and pointers into a sequence of groups, and activating said machine compressing and machine generating steps to convert said groups into respective high-level compressed index blocks, whereby said high-level compressed index blocks provide a high index level.

Claim 4

Dependent Claim 68 words

A method of generating a high-level compressed index as defined in claim 1, further including the steps of said machine compressing step simulating a null uncompressed key as the first uncompressed key in said sequenced high-level group of uncompressed keys, and machine blocking said high-level index entries into high-level blocks as provided by said machine generating step, whereby an independent search characteristic is generated for each high-level block.

Claim 5

Dependent Claim 52 words

A method as defined in claim 3 further including the step of machine transferring each of said high-level blocks to a recording medium in their generated order at preassigned locations, whereby each address representation of said preassigned locations is a pointer for an entry in a next higher level of said index.

Claim 6

Dependent Claim 34 words

A method as defined in claim 3, in which said machine blocking step includes, machine counting not more than a predetermined number of said high-level index entries to comprise any single compressed index block.

Claim 7

Dependent Claim 52 words

A method as defined in claim 3, in which said machine blocking step includes machine completing each compressed index block whenever a next index entry can exceed a predetermined number of bytes for generating each compressed index block, or when no more index entries are being provided by said machine generating step.

Claim 8

Dependent Claim 49 words

A method as defined in claim 2, in which said machine compressing step further includes machine formating a last compressed key for a last index entry in each high-level compressed index block with a special format different from a format used for other compressed keys in the same block.

Claim 9

Dependent Claim 35 words

A method as defined in claim 7, in which said machine formating step further includes machine inserting a predetermined byte as the last compressed key in the last index entry for ending each index block.

Claim 10

Dependent Claim 32 words

A method as defined in claim 6, further including the step of machine ending the generation of each high level in the multilevel compressed index before generating a next higher index level.

Claim 11

Dependent Claim 105 words

A method as defined in claim 3, for generating a next higher level in said compressed index, including the following steps machine collecting each last pair of uncompressed keys used in the generation of each said high-level block in sorted sequence to provide a machine collection of uncompressed keys, also machine assigning pointers to each said last pair of uncompressed keys, each of said pointers representing the address of a high-level index block for which said last pair was used by said machine generating step, and reiterating said machine compressing step and said machine generating step to generate index entries for the next higher level.

Claim 12

Dependent Claim 44 words

A method as defined in claim 8, further including the step of machine blocking the index entries to generate index blocks for the next higher index level, after said reiterating step has generated index entries in a number to fill a predetermined block size.

Claim 13

Independent Claim 402 words

A method of generating a multilevel compressed index from a sorted input sequence of uncompressed keys with respective pointers to related data blocks for providing an uncompressed index for a set of data blocks, having the steps of machine grouping said uncompressed keys and related pointers into a plurality of sequenced groups, machine comparing each adjacent pair of uncompressed keys in each sequenced group, machine compressing said adjacent uncompressed keys into compressed keys for a low-index level, and machine Positioning with each compressed key a pointer to a data block related to a first uncompressed key of each adjacent pair of uncompressed keys acted upon by said machine compressing step, each compressed key and its pointer comprising a low-level entry, machine collecting each low-level entry generated from each group of uncompressed keys to build each compressed index block for a lowest level of said compressed index, machine reiterating said machine comparing, machine compressing, and machine collecting steps for each sequential group to build a sequence of compressed index blocks comprising the lowest index level, machine storing each compressed index block in said lowest index level at an assigned address in a machine-addressable storage entity, and providing a boundary pair pointer to represent each assigned address, machine assembling the last uncompressed key in each group and the first uncompressed key in the next sequential group, each said last and first uncompressed keys comprising a boundary pair of uncompressed keys, machine assigning a boundary pair pointer to each said boundary pair, of uncompressed keys, each boundary pair pointer representing the assigned address of a related lowest-level compressed index block for which said last uncompressed key of said boundary pair is a last uncompressed key in the group used by said machine-collecting step to generate the related lowest level compressed index block, machine storing each boundary pair of uncompressed keys and their boundary pair pointers in sequence to form one or more sets of boundary pairs and pointers, machine compressing each set of uncompressed keys in sequence into compressed keys for said high level, and machine recording pairs of said compressed keys for said high level with related boundary pair pointers in the sequence in which they are made available by said machine compressing step in generating compressed keys for said high level, whereby a second compressed key in each pair is generated from a comparison of the uncompressed keys within a single boundary pair.

Claim 14

Independent Claim 402 words

A method of generating a multilevel compressed index from a sorted input sequence of uncompressed keys with respective pointers to related data blocks for providing an uncompressed index for a set of data blocks, having the steps of machine grouping said uncompressed keys and related pointers into a plurality of sequenced groups, machine comparing each adjacent pair of uncompressed keys in each sequenced group, machine compressing said adjacent uncompressed keys into compressed keys for a low-index level, and machine Positioning with each compressed key a pointer to a data block related to a first uncompressed key of each adjacent pair of uncompressed keys acted upon by said machine compressing step, each compressed key and its pointer comprising a low-level entry, machine collecting each low-level entry generated from each group of uncompressed keys to build each compressed index block for a lowest level of said compressed index, machine reiterating said machine comparing, machine compressing, and machine collecting steps for each sequential group to build a sequence of compressed index blocks comprising the lowest index level, machine storing each compressed index block in said lowest index level at an assigned address in a machine-addressable storage entity, and providing a boundary pair pointer to represent each assigned address, machine assembling the last uncompressed key in each group and the first uncompressed key in the next sequential group, each said last and first uncompressed keys comprising a boundary pair of uncompressed keys, machine assigning a boundary pair pointer to each said boundary pair, of uncompressed keys, each boundary pair pointer representing the assigned address of a related lowest-level compressed index block for which said last uncompressed key of said boundary pair is a last uncompressed key in the group used by said machine-collecting step to generate the related lowest level compressed index block, machine storing each boundary pair of uncompressed keys and their boundary pair pointers in sequence to form one or more sets of boundary pairs and pointers, machine compressing each set of uncompressed keys in sequence into compressed keys for said high level, and machine recording pairs of said compressed keys for said high level with related boundary pair pointers in the sequence in which they are made available by said machine compressing step in generating compressed keys for said high level, whereby a second compressed key in each pair is generated from a comparison of the uncompressed keys within a single boundary pair.

Claim 15

Dependent Claim 89 words

A method of generating a high level for a compressed index as defined in claim 12, further including the steps of machine sensing the last pair of uncompressed keys in each set used in the generation of each compressed index block at said high level, next machine assembling each last pair of uncompressed keys in the sequence provided by said machine sensing step, and machine repeating said machine assigning, last-mentioned machine compressing, and machine recording steps to generate each entry for a still higher level in said compressed index.

Claim 16

Dependent Claim 88 words

A method of generating each still higher level for a compressed index using the method defined in claim 13, further including the steps of machine indicating the end of generation for each index level and providing an end-of-index signal for each high level being generated, machine repeating the prior-named steps used in generating any high level for generating a next high level, and machine terminating each current level generated for said compressed index in response to said end-of-index signal, and continuing the generation of the next higher level.

Claim 17

Dependent Claim 80 words

A method of generating a multilevel compressed index using the method defined in claim 14, comprising machine counting the number of levels in the compressed index currently generated, machine signalling when said machine counting step indicates a predetermined number of levels upon an occurrence of said end-of-index signal, and, machine terminating the generation of said multilevel index in response to an indication by said machine signalling step whereby a last generated level is an apex level for the multilevel index.

Claim 18

Dependent Claim 117 words

A method of generating a multilevel compressed index as defined in claim 14, including the steps of machine signalling a continuing signal that generation should start for a next higher level when plural Index blocks are generated at any current level upon activation of said machine terminating step for said current level, machine generating a next higher level in said compressed multilevel index in response to said continuing signal, and machine ending the compressed index generating upon said machine signalling step signalling the existence of only one block at the next higher level, whereby a last index block completed at the execution of said machine ending step is an apex compressed block of the multilevel compressed index.

Claim 19

Dependent Claim 37 words

A method of generating a multilevel index as defined in claim 16, including the step of machine storing a pointer to said last index block in a predetermined location for future accessing of the multilevel compressed index.

Claim 20

Independent Claim 136 words

A method of generating each high level of a compressed index comprising the steps of machine assembling a sequence of boundary pairs of uncompressed keys used in the generation of a plurality of blocks in a next lower level of the compressed index, machine assigning a respective pointer to each of said boundary pairs, said pointer being related to the address of a related one of the blocks in the next lower level, machine grouping said boundary pairs and said respective pointers in sequence for the generation of index blocks in said high level, machine recognizing a null condition as the first uncompressed key in the sequence of boundary pairs, and machine storing a plurality of groupings of said boundary pairs of uncompressed keys in preparation for the generation of a high level of said index.

Claim 21

Independent Claim 136 words

A method of generating each high level of a compressed index comprising the steps of machine assembling a sequence of boundary pairs of uncompressed keys used in the generation of a plurality of blocks in a next lower level of the compressed index, machine assigning a respective pointer to each of said boundary pairs, said pointer being related to the address of a related one of the blocks in the next lower level, machine grouping said boundary pairs and said respective pointers in sequence for the generation of index blocks in said high level, machine recognizing a null condition as the first uncompressed key in the sequence of boundary pairs, and machine storing a plurality of groupings of said boundary pairs of uncompressed keys in preparation for the generation of a high level of said index.

Claim 22

Dependent Claim 154 words

A method of generating a high level of a compressed index including the steps in claim 18, and including the following steps: machine reading the groupings of uncompressed keys in the sequence stored by said machine storing step, machine compressing the uncompressed keys in each grouping to provide compressed keys, machine recording said compressed keys in sequential pairs with a related one of said pointers to provide each compressed index entry for said high level, machine blocking said entries in their generated sequence for each group of uncompressed keys to generate each high-level block, and machine repeating the preceding steps for each group for said high level until an end is reached for the groups of compressed keys provided by said machine reading step, whereby the end of the index at said high level is reached upon said machine compressing step reaching the end of the uncompressed keys provided by said machine reading step.

Claim 23

Dependent Claim 70 words

A method for generating a next higher level in a multilevel index, including the steps defined in claim 19, and further including machine reiterating the steps of machine assembling boundary pairs, machine-assigning pointers, machine grouping of boundary pairs, machine storing a plurality of groupings, machine reading the groupings, machine compressing the groupings, machine recording the compressed index entries, and machine blocking the entries until the next higher level is completed.

Claim 24

Dependent Claim 38 words

A method for generating a multilevel index including the steps in claim 20, and the additional step of ending the construction of said index as soon as any high-level compressed index is completed with a single index block.

Claim 25

Independent Claim 142 words

A system of generating index entries for a high level of a multilevel compressed index, including means for machine assembling a plurality of boundary pairs of uncompressed keys, each boundary pair being a last and a first uncompressed key in two sequenced groups of uncompressed keys used in the generation of two sequential index blocks at the lowest level of said compressed index, said machine assembling means providing a sequenced high-level group of uncompressed keys, means for machine assigning pointers to each of said uncompressed key pairs, said pointers representing addresses of compressed index blocks in said lowest level, means for machine compressing said uncomPressed keys in sequence into compressed keys, and means for machine generating index entries for said high level by a relational positioning of said pointers with respective pairs of said compressed keys provided by said machine compressing means.

Claim 26

Independent Claim 142 words

A system of generating index entries for a high level of a multilevel compressed index, including means for machine assembling a plurality of boundary pairs of uncompressed keys, each boundary pair being a last and a first uncompressed key in two sequenced groups of uncompressed keys used in the generation of two sequential index blocks at the lowest level of said compressed index, said machine assembling means providing a sequenced high-level group of uncompressed keys, means for machine assigning pointers to each of said uncompressed key pairs, said pointers representing addresses of compressed index blocks in said lowest level, means for machine compressing said uncomPressed keys in sequence into compressed keys, and means for machine generating index entries for said high level by a relational positioning of said pointers with respective pairs of said compressed keys provided by said machine compressing means.

Claim 27

Dependent Claim 59 words

A system as defined in claim 22 for generating the high-level index, including means for machine grouping said boundary pairs of said uncompressed keys and pointers into a sequence of groups, and said machine compressing means and said machine generating means receiving said groups and generating respective high-level compressed blocks, whereby said high-level blocks provide a high index level.

Claim 28

Dependent Claim 69 words

A system of generating a high-level compressed index as defined in claim 22, further including said machine compressing means simulating a null uncompressed key as the first uncompressed key in said sequenced high-level group of uncompressed keys, and machine blocking means positioning said high-level index entries into high-level blocks as said entries are provided by said machine-generating means, whereby an independent search characteristic is generated for each high-level block.

Claim 29

Dependent Claim 48 words

A system as defined in claim 24, further including means for machine transferring each of said high-level blocks to a recording medium in their generated order at preassigned locations, whereby address representations of said preassigned locations provide pointers for entries in a next higher level of said index.

Claim 30

Dependent Claim 36 words

A system as defined in claim 24, in which said machine blocking means includes, means for machine counting not more than a predetermined number of said high-level index entries to comprise any single compressed index block.

Claim 31

Dependent Claim 54 words

A system as defined in claim 24, in which said machine blocking means includes means for machine completing each compressed index block whenever a next index entry can exceed a predetermined number of bytes for generating each compressed index block, or when no more index entries are being provided by said machine generating means.

Claim 32

Dependent Claim 50 words

A system as defined in claim 23, in which said machine compressing means includes means for machine formating a last compressed key for a last index entry in each high-level compressed index block with a special format different from a format used for other compressed keys in the same block.

Claim 33

Dependent Claim 37 words

A system as defined in claim 28, in which said machine formating means further includes means for machine inserting a predetermined byte as the last compressed key in the last index entry for ending each index block.

Claim 34

Dependent Claim 31 words

A system as defined in claim 27, further including means for machine ending the generation of each high level in the multilevel compressed index before generating a next higher index level.

Claim 35

Dependent Claim 108 words

A system as defined in claim 24, for generating a next higher level in said compressed index, including means for machine collecting each last pair of uncompressed keys used in the generation of each said high-level block in sorted sequence to provide a machine collection of uncompressed keys, means for machine assigning other pointers to each said last pair of uncompressed keys, each of said other pointers representing the address of a high-level index block for which said last pair was used by said machine generating means, and said machine compressing means and said machine generating means being actuated to generate index entries for the next higher level.

Claim 36

Dependent Claim 35 words

A system as defined in claim 30, in which said machine blocking means generates index blocks for the next higher index level by sequentially controlling the index entries by means of a predetermined block size.

Claim 37

Independent Claim 430 words

A system of generating a multilevel compressed index from a sorted input sequence of uncompressed keys with respective pointers to related data blocks for providing an uncompressed index for a set of data blocks, comprising means for machine grouping said uncompressed keys and relaTed pointers into a plurality of sequenced groups, means for machine comparing each adjacent pair of uncompressed keys in each sequenced group, means for machine compressing said adjacent uncompressed keys into compressed keys for a low index level, and means for machine positioning with each compressed key a pointer to a data block related to a first uncompressed key of each adjacent pair of uncompressed keys acted upon by said machine compressing means, each compressed key and its pointer comprising a low-level entry, means for machine collecting each low-level entry generated from each group of uncompressed keys to build each compressed index block for a lowest level of said compressed index; and means for activating said machine comparing means, said machine compressing means, and said machine collecting means for each sequential group to build a sequence of compressed index blocks comprising the lowest index level, means for machine storing each compressed index block in said lowest index level at an assigned address in a machine-addressable storage entity, and providing a boundary pair pointer to represent each assigned address, means for machine assembling the last uncompressed key in each group and the first uncompressed key in the next sequential group, each said last and first uncompressed keys comprising a boundary pair of uncompressed keys, means for machine assigning a boundary pair pointer to each said boundary pair of uncompressed keys, each boundary pair pointer representing the assigned address of a related lowest level compressed index block for which said last uncompressed key of said boundary pair is a last uncompressed key in the group used by said machine collecting means to generate the related lowest level compressed index block, means for machine storing each boundary pair of uncompressed keys and their boundary pair pointers in sequence to form one or more sets of boundary pairs and pointers, means for machine compressing each set of uncompressed keys in sequence into compressed keys for said high level, and means for machine recording pairs of said compressed keys for said high level with related boundary pair pointers in the sequence in which they are made available by said machine compressing means in generating compressed keys for said high level, whereby a second compressed key in each pair is generated from a comparison of the uncompressed keys within a single boundary pair.

Claim 38

Independent Claim 430 words

A system of generating a multilevel compressed index from a sorted input sequence of uncompressed keys with respective pointers to related data blocks for providing an uncompressed index for a set of data blocks, comprising means for machine grouping said uncompressed keys and relaTed pointers into a plurality of sequenced groups, means for machine comparing each adjacent pair of uncompressed keys in each sequenced group, means for machine compressing said adjacent uncompressed keys into compressed keys for a low index level, and means for machine positioning with each compressed key a pointer to a data block related to a first uncompressed key of each adjacent pair of uncompressed keys acted upon by said machine compressing means, each compressed key and its pointer comprising a low-level entry, means for machine collecting each low-level entry generated from each group of uncompressed keys to build each compressed index block for a lowest level of said compressed index; and means for activating said machine comparing means, said machine compressing means, and said machine collecting means for each sequential group to build a sequence of compressed index blocks comprising the lowest index level, means for machine storing each compressed index block in said lowest index level at an assigned address in a machine-addressable storage entity, and providing a boundary pair pointer to represent each assigned address, means for machine assembling the last uncompressed key in each group and the first uncompressed key in the next sequential group, each said last and first uncompressed keys comprising a boundary pair of uncompressed keys, means for machine assigning a boundary pair pointer to each said boundary pair of uncompressed keys, each boundary pair pointer representing the assigned address of a related lowest level compressed index block for which said last uncompressed key of said boundary pair is a last uncompressed key in the group used by said machine collecting means to generate the related lowest level compressed index block, means for machine storing each boundary pair of uncompressed keys and their boundary pair pointers in sequence to form one or more sets of boundary pairs and pointers, means for machine compressing each set of uncompressed keys in sequence into compressed keys for said high level, and means for machine recording pairs of said compressed keys for said high level with related boundary pair pointers in the sequence in which they are made available by said machine compressing means in generating compressed keys for said high level, whereby a second compressed key in each pair is generated from a comparison of the uncompressed keys within a single boundary pair.

Claim 39

Dependent Claim 92 words

A system of generating a high level for a compressed index as defined in claim 33, including means for machine sensing the last pair of uncompressed keys in each set used in the generation of each compressed index block at said high level, means for machine assembling each last pair of uncompressed keys in the sequence provided by said machine sensing means, and means for actuating said assigning means, said last-mentioned machine compressing means, and said machine recording means to generate each entry for a still higher level in said compressed index.

Claim 40

Dependent Claim 80 words

A system of generating each still higher level for a compressed index, including the means defined in claim 34, further including means for machine indicating the end of generation for each index level and providing an end-of-index signal for each high level being generated, means for terminating each current level of said compressed index in response to said end-of-index signal, and means for actuating the prior-named means used in generating each prior high level for generating a next high level.

Claim 41

Dependent Claim 87 words

A system of generating a multilevel compressed index using the means defined in claim 35, further comprising means for machine counting the number of levels in the compressed index currently generated, means for machine signalling when said machine counting step indicates a predetermined number of levels upon an occurrence of said end-of-index signal, and means for machine terminating the generation of said multilevel Index in response to an indication by said machine signalling means, whereby a last generated level is an apex level for the multilevel index.

Claim 42

Dependent Claim 111 words

A system of generating a multilevel compressed index as defined in claim 35, including means for machine signalling a continuing signal that generating should start for a next higher level when plural index blocks are generated at any current level upon activation of said machine terminating means for the current level, means for machine generating a next higher level in said compressed multilevel index in response to said continuing signal, and means for machine ending the compressed index generation upon said machine signalling means ending the continuing signal when only one block comprises the next higher level, whereby said one block is an apex compressed block for the multilevel compressed index.

Claim 43

Dependent Claim 36 words

A system of generating a multilevel index as defined in claim 37, including means for machine storing a pointer to said last index block in a predetermined location for future accessing of the multilevel compressed index.

Claim 44

Independent Claim 144 words

A system of generating each high level of a compressed index, comprising means for machine assembling a sequence of boundary pairs of uncompressed keys used in the generation of a plurality of blocks in a next lower level of the compressed index, means for machine assigning a respective pointer to each of said boundary pairs, said pointer being related to the address of a related one of the blocks in the next lower level, means for machine grouping said boundary pairs and said respective pointers in sequence for the generating of index blocks in said high level, and means for machine recognizing a null condition as a first uncompressed key in the sequence of boundary pairs, and means for machine storing a plurality of groupings of said boundary pairs of uncompressed keys in preparation for the generation of a high level of said index.

Claim 45

Independent Claim 144 words

A system of generating each high level of a compressed index, comprising means for machine assembling a sequence of boundary pairs of uncompressed keys used in the generation of a plurality of blocks in a next lower level of the compressed index, means for machine assigning a respective pointer to each of said boundary pairs, said pointer being related to the address of a related one of the blocks in the next lower level, means for machine grouping said boundary pairs and said respective pointers in sequence for the generating of index blocks in said high level, and means for machine recognizing a null condition as a first uncompressed key in the sequence of boundary pairs, and means for machine storing a plurality of groupings of said boundary pairs of uncompressed keys in preparation for the generation of a high level of said index.

Claim 46

Dependent Claim 159 words

A system of generating a high level of a compressed index as defined in claim 39, comprising means for machine reading the groupings of uncompressed keys in the sequence stored by said machine storing means, means for machine compressing the uncompressed keys in each grouping to provide compressed keys, means for machine recording said compressed keys in sequential pairs with a related one of said pointers to provide each compressed index entry for said high level, means for machine blocking said entries in their generated sequence for each group of uncompressed keys to generate each high level block, and means for reactivating the preceding steps for each group for said high level until an end is reached for the groups of compressed keys provided by said machine reading means, whereby the end of the index at said high level is reached upon said machine compressing means reaching the end of the compressed keys provided by said machine reading means.

Claim 47

Dependent Claim 61 words

A system as defined in claim 40 for generating a next higher level in a multilevel index, including means for reactuating said machine assembling means, said machine assigning means, said machine grouping means, said machine storing means, said machine reading means, said machine compressing means, said machine recording means, and said machine blocking means until the next higher level is completed.

Claim 48

Dependent Claim 36 words

A system as defined in claim 41 for generating a multilevel index, including means for ending the construction of said index as soon as any high level compressed index is completed with a single index block.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1974-09-06	1975-03-08	1975-09-07	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1978-09-06	1979-03-08	1979-09-07	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1982-09-06	1983-03-08	1983-09-07	$7700.00	Window Closed / Lapsed

Multilevel compressed index generation method and means

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag