Method for labeling data stored in sequential data structures with parameters which describe position in a hierarchy

• US 7,769,781 B1
• Filed: 05/23/2007
• Issued: 08/03/2010
• Est. Priority Date: 05/23/2007
• Status: Active Grant

• Current Assignee: Stephen Edward Huntley
• Original Assignee: Stephen Edward Huntley
• Inventors: Huntley, Stephen Edward
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Uddin; MD. I
• Application Number:
  US11/752,303
• Time in Patent Office: 1,168 Days
• Field of Search: 707/102, 707/673, 707/736, 707/752, 707/791, 707/802, 708/7, 708/503, 708/620, 708/622, 708/623, 708/624, 708/625, 708/626, 709/201, 709/205
• US Class Current: 707/791
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

Abstract

A method for calculating numerical values in a manner which can be interpreted as encoding places in a hierarchy, and are in a format convenient for storage and retrieval on computer systems. The numerical values are calculated by associating paths in a hierarchy with sub-sequences of terms of a mathematical series where an ordering of the sub-sequences according to the occurrence of the first terms of the sub-sequences in the mathematical series is the same as an ordering of the magnitude of the sums of the terms of the sub-sequences. Said numerical values can be conveniently stored as integer or floating-point data types commonly used in computer systems and as such assigned to appropriate data elements in a data structure which defines serial relationships between the items it stores. Thus this invention enables sequential data structures such as arrays, linked lists and databases to store and retrieve tree structure data efficiently.

Claims

1. A method, implemented by loading a program into the addressable memory of a general purpose computer and executing said program, for representing a hierarchy in a sequential data structure, comprising the steps of:

selecting a mathematical series with a defined sequence of summation values and a defined sequence of terms, each said term being a function of an input variable, said input variable corresponding to the summation index variable of said defined sequence of summation values, said mathematical series having the property that any set of sub-sequences of said terms of said series, sorted into an order according to occurrence in said series of each sub-sequence'"'"'s first term, can be sorted into the same order according to the magnitude of the result of adding each sub-sequence'"'"'s terms,

assigning to each node of said hierarchy one of said terms of said mathematical series, such that every parented node of said hierarchy has an assigned term which comes after said parented node'"'"'s parent'"'"'s assigned term in said mathematical series'"'"' said sequence of terms, and each said parented node of said hierarchy has an assigned term which is unique with respect to any of said parented node'"'"'s siblings'"'"' assigned terms,

calculating the respective numerical value of each respective node'"'"'s assigned term and associating with each said respective node of said hierarchy said respective numerical value,

calculating for each said respective node of said hierarchy the unique sum of said respective node'"'"'s said respective associated numerical value plus the associated numerical values of all of said respective node'"'"'s ancestors,

splitting the range of binary digits which represent the value of said unique sum into segments such that the number of binary digits in each said segment is no longer than the maximum number of binary digits that said computer can address in a single data read/write cycle operating on said sequential data structure,

defining in said sequential data structure a new data element by allocating in said computer'"'"'s available memory a discrete number of addressable ranges equal to the number of said segments of said range of binary digits such that said addressable ranges of memory are capable of storing said range of binary digits in full,

copying said segments of said range of binary digits each into one of said discrete number of addressable ranges of memory,

whereby said general purpose computer becomes a special purpose computer whose addressable memory is in a state suitable for performing search and retrieval of hierarchical information.

2. The method of claim 1 where said sequential data structure is a database residing on a tangible computer-readable storage medium.

3. A method, implemented by loading a program into the addressable memo of a general purpose computer and executing said program, for representing a hierarchy in a sequential data structure, comprising the steps of:

selecting a double mathematical series with two defined sequences of summation values and a defined sequence of terms, each said term being a function of two input variables, said input variables corresponding to the summation index variables of said two defined sequences of summation values, said double mathematical series having the property that any set of sub-sequences of said terms, in which each summation value increments in each term, of said double series, sorted into an order according to occurrence in said series of each sub-sequence'"'"'s first term, can be sorted into the same order according to the magnitude of the result of adding each sub-sequence'"'"'s terms,

assigning to each node of said hierarchy one of said terms of said double mathematical series, such that every parented node of said hierarchy has an assigned term which comes after said parented node'"'"'s parent'"'"'s assigned term in said double mathematical series'"'"' said sequence of terms, each respective said assigned term has one of its summation index variables set to a value equal to the level in said hierarchy of said parented node to which the respective said assigned term is assigned, and the numerical value of each said parented node'"'"'s said assigned term is unique with respect to the numerical value of any of said parented node'"'"'s siblings'"'"' assigned terms,

calculating the respective numerical value of each respective node'"'"'s assigned term and associating with each said respective node of said hierarchy said respective numerical value,

calculating for each said respective node of said hierarchy the unique sum of said respective node'"'"'s said respective associated numerical value plus the associated numerical values of all of said respective node'"'"'s ancestors,

splitting the range of binary digits which represent the value of said unique sum into segments such that the number of binary digits in each said segment is no longer than the maximum number of binary digits that said computer can address in a single data read/write cycle operating on said sequential data structure,

defining in said sequential data structure a new data element by allocating in said computer'"'"'s available memory a discrete number of addressable ranges equal to the number of said segments of said range of binary digits such that said addressable ranges of memory are capable of storing said range of binary digits in full,

copying said segments of said range of binary digits each into one of said discrete number of addressable ranges of memory,

whereby said general purpose computer becomes a special purpose computer whose addressable memory is in a state suitable for performing search and retrieval of hierarchical information.

4. The method of claim 3 where said sequential data structure is a database residing on a tangible computer-readable storage medium.

5. A non-transitory computer-readable storage medium with an executable program stored thereon, wherein the program instructs a computer processor to perform the following steps:

selecting a mathematical series with a defined sequence of summation values and a defined sequence of terms, each said term being a function of an input variable, said input variable corresponding to the summation index variable of said defined sequence of summation values, said mathematical series having the property that any set of sub-sequences of said terms of said series, sorted into an order according to occurrence in said series of each sub-sequence'"'"'s first term, can be sorted into the same order according to the magnitude of the result of adding each sub-sequence'"'"'s terms,

assigning to each node of said hierarchy one of said terms of said mathematical series, such that every parented node of said hierarchy has an assigned term which comes after said parented node'"'"'s parent'"'"'s assigned term in said mathematical series'"'"' said sequence of terms, and each said parented node of said hierarchy has an assigned term which is unique with respect to any of said parented node'"'"'s siblings'"'"' assigned terms,

calculating the respective numerical value of each respective node'"'"'s assigned term and associating with each said respective node of said hierarchy said respective numerical value,

calculating for each said respective node of said hierarchy the unique sum of said respective node'"'"'s said respective associated numerical value plus the associated numerical values of all of said respective node'"'"'s ancestors,

splitting the range of binary digits which represent the value of said unique sum into segments such that the number of binary digits in each said segment is no longer than the maximum number of binary digits that said computer can address in a single data read/write cycle operating on said sequential data structure,

defining in said sequential data structure a new data element by allocating in said computer'"'"'s available memory a discrete number of addressable ranges equal to the number of said segments of said range of binary digits such that said addressable ranges of memory are capable of storing said range of binary digits in full,

copying said segments of said range of binary digits each into one of said discrete number of addressable ranges of memory.

6. The non-transitory computer-readable storage medium with an executable program stored thereon of claim 5 where said sequential data structure specified in said program is a database residing on a tangible computer-readable storage medium.

7. A non-transitory computer-readable storage medium with an executable program stored thereon, wherein the program instructs a computer processor to perform the following steps:

selecting a double mathematical series with two defined sequences of summation values and a defined sequence of terms, each said term being a function of two input variables, said input variables corresponding to the summation index variables of said two defined sequences of summation values, said double mathematical series having the property that any set of sub-sequences of said terms, in which each summation value increments in each term, of said double series, sorted into an order according to occurrence in said series of each sub-sequence'"'"'s first term, can be sorted into the same order according to the magnitude of the result of adding each sub-sequence'"'"'s terms,

assigning to each node of said hierarchy one of said terms of said double mathematical series, such that every parented node of said hierarchy has an assigned term which comes after said parented node'"'"'s parent'"'"'s assigned term in said double mathematical series'"'"' said sequence of terms, each respective said assigned term has one of its summation index variables set to a value equal to the level in said hierarchy of said parented node to which the respective said assigned term is assigned, and the numerical value of each said parented node'"'"'s said assigned term is unique with respect to the numerical value of any of said parented node'"'"'s siblings'"'"' assigned terms,

calculating the respective numerical value of each respective node'"'"'s assigned term and associating with each said respective node of said hierarchy said respective numerical value,

calculating for each said respective node of said hierarchy the unique sum of said respective node'"'"'s said respective associated numerical value plus the associated numerical values of all of said respective node'"'"'s ancestors,

splitting the range of binary digits which represent the value of said unique sum into segments such that the number of binary digits in each said segment is no longer than the maximum number of binary digits that said computer can address in a single data read/write cycle operating on said sequential data structure,

defining in said sequential data structure a new data element by allocating in said computer'"'"'s available memory a discrete number of addressable ranges equal to the number of said segments of said range of binary digits such that said addressable ranges of memory are capable of storing said range of binary digits in full,

copying said segments of said range of binary digits each into one of said discrete number of addressable ranges of memory.

8. The non-transitory computer-readable storage medium with an executable program stored thereon of claim 7 where said sequential data structure specified in said program is a database residing on a tangible computer-readable storage medium.