Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1996-12-12
2001-09-11
Choules, Jack (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06289349
ABSTRACT:
TABLE OF CONTENTS
Table of Contents
Introduction
Background of the Invention
Prior Art
Summary of the Invention
Claims
Abstract
Drawings
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a binary tree arrangement storing fixed or variable length keys, and a method and apparatus for locating the insert arc or node in such an arrangement.
2. Introduction
The invention provides a novel binary tree arrangement for a machine representation storing both fixed and variable length keys, together with their lengths, organized by the nodes and connections between nodes in said binary tree. The arrangement minimizes the storage required for the machine representation of said nodes, connections, keys and their lengths.
The invention provides method and means for controlling the locating step(s) of a binary tree insertion operation, It uses a principle based on a minimal difference or a maximal similarity relationship among the keys stored in the tree.
The embodiments of this invention include unique methods and apparatus for controlling the execution of a computer. This application describes the steps performed and the machine representation in sufficient detail that a person skilled in the art can make and use them in hardware, microprogram, or program. Thus the inventions can be utilized in either a special purpose or general purpose computer system.
The invention provides the control logic for said insertion method in a binary tree having said novel binary tree arrangement, said control logic minimizing the number of storage accesses and stores for carrying out said locating step(s) and inserting operation, and minimizing the amount of elapsed time required for a machine to execute said operations.
The invention provides both method and means for said control logic that is especially suited for direct use in a special purpose apparatus for executing the subject processes, and especially suited for incorporation in a reduced instruction set computer (RISC) in the form of instructions which can be executed in a single cycle.
The methods and apparatus of the invention provide economic advantage for sorting and indexing, which are heavily used in commercial computing environments; especially providing a competitive economic advantage for computer execution of database operations and associative classes in object oriented programming, logic programming, and constraint logic programming.
3. Description of the Prior Art
The prior art includes publications such as “Sorting and Searching”, by D. E. Knuth, published in 1973 by Addison Wesley. The prior art also includes the following U.S. patents: U.S. Pat. No. 3,916,387 “Direcory Searching Method and Means”, and U.S. Pat. No. 4,086,628 “Directory Generation System Having Efficiency Increase with Sorted Input.”
The above prior art apply to searching and inserting in binary trees, where a forward path trace is followed by a backward path trace to complete an insert. The path trace utilizing the forward and backward path trace to locate the insert arc enables the prior art to locate the insert arc by processing a number of nodes approximately equal to 1.4 times the base two logarithm of the number of keys in the tree, plus the nodes on the backward path trace.
The prior art includes “Blasting Through The Information Theoretic Barrier With FUSION TREES”, by Michael L. Frednam and Dan E. Willard, published in the Proceedings of the 22-nd ACM Symposium on Theory for Computing, (1990), pp. 1-7. In this prior art, multiplication is used to select bits of a key in order to form an index into a complete binary tree having a number for entries that is an exact power of two.
This prior art utilizes an insertion method requiring polynomial time for new nodes in a multiway tree. As a result, claims for faster sorting in this prior art apply only to ernormously large numbers of entries, as the “constant” time to use for each sub-logarithmic operation is so huge that it would require having trillions of entries before the time is competitive with other art.
More closely related prior art is “New Trie Data Structures Support Very Fast Search Operations”, by Dan E. Willard, published in the Journal of Computing and System Sciences, volume 28, in 1984, pp. 379-394. In this prior art, two keys are stored at each binary tree node. Searching and inserting follow a downward path trace, starting from a top node. Said two keys are selected from the left and right subtrees, respectively, of said binary tree node. Said downward path trace proceeds by forming two quantities by exclusive-oring a new key with said two stored keys, and then comparing the two quantities. The lower of the two quantities determines whether the new key directs the downward path trace into said left or said right subtree of said node.
Also stored at each binary tree node are pointers to the subtrees of said node. Thus the space requirements are at least four words per entry, and in practice are more, because of the encoding of terminal nodes. No means nor method for backtrace is provided.
The above prior art mentions forming a multilevel tree structure by utilizing trees for each level, wherein the keys are restricted to the word length of the machine. The first level is thus represented by a first level tree. At the end of each path in the first level tree is a pointer to a next level tree for the next word in the key, and so on. No encoding methods, no arrangements of the fields to accomplish the multilevel encoding, are disclosed.
The above prior art does not provide for variable length keys, except for U.S. Pat. No. 3,916,387 which does not elaborate the actual representation for variable length key support.
In the prior art U.S. Pat. No. 3,916,387 no part of any key is stored in the tree, but all locating is done by means of bit testing. It is somewhat similar to the Fusion Tree methods, except that the Fusion Tree methods espouse the use of multiplcation for decoding multiple bits for path tracing.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the invention to provide a faster means and method for locating the insert arc in a binary tree.
Another object of the invention is to provide a binary tree arrangement and insertion method and apparatus that is simpler and easier to use.
The subject invention locates the insertion arc by processing a number of nodes which could actually be less than the base two logarithm of the number of tree entries. It locates the insert arc on a forward path trace, stopping when it first processes the insert arc. Thus is does not necessarily trace the complete forward path; nor does it effect a backward trace.
In case the lengths of the paths in the binary tree are not evenly distributed, the above prior art locates an insertion arc in a number of steps equal to the length of the path to an already-existing entry plus the number of arcs traced along the backpath, whereas the subject invention never requires more steps to locate an insertion point than the length of the path, and on the average requires fewer steps than the length of an already existing path.
Another advantage of the invention over the prior art is that said prior art uses a flag bit as a part of each binary tree node representation to signal whether the node is a left or a right successor of its predecessor node, whereas the subject invention does not need nor use a left/right successor flag bit.
Yet another advantage of the subject invention over the above prior art is that the above prior art employs bit tests for path tracing, whereas the subject invention does not use bit testing for path tracing but rather uses a novel minimal difference or maximal similarity partitioning operation for path tracing during insertion.
The subject invention also has economic advantage over the prior art for building indexes and for sorting.
Partial order trees are also sometimes called “heap trees”, after Floyd Patterson; see the “Communications of the ACM”, 1965. The prior art employing partial order trees, or heap trees, require a number of steps proportional to the b
Choules Jack
Taphorn Jospeh B.
LandOfFree
Binary tree structure with end of path flags stored with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Binary tree structure with end of path flags stored with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary tree structure with end of path flags stored with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2507827