Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-30
2004-05-11
Le, Uyen (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06735600
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to search engines for searching large tables of data, and particularly to an improved protocol for insertion and deletion of items to the search table.
BACKGROUND OF THE INVENTION
Lookup procedures are a major source of bottlenecks in high-performance compilers and routers, such as compilers used to search databases of cell designs for designing integrated circuits, and compilers used to lookup internet addresses (URLs) in network applications. Recently, there has been renewed interest in binary search trees, largely because the worst-case time required for basic dynamic set operations is O(log n), where n is the number of nodes or vertices in the tree. In application Ser. No. 09/679,313, we describe a sorted binary search tree that inherits the favorable attributes of prior binary search trees, but provides simpler solutions for insertion and deletion functions. However, that search tree requires considerable memory allocation, particularly for performing insertion and deletion functions. The insertion and deletion functions are important to the search tree because they maintain equal length to all search paths through the tree.
The present invention is directed to an improvement of the search tree described in our aforementioned applications, and particularly to an improved insertion and deletion technique that reduces memory requirements for the tree.
SUMMARY OF THE INVENTION
One aspect of the present invention is a process for changing the number of entries in a search tree by inserting or deleting entries into or from a vertex of a bottom level. The search tress has a top level, a bottom level and at least one hierarchy level between the top level and the bottom level. The bottom level has a plurality of vertices each containing at least one entry, with each bottom level vertex being a child vertex to a vertex of a hierarchy level and each vertex in the top and hierarchy levels being a parent to at least one vertex in a lower level. A vertex is selected and its level in the tree identified. If the level of the selected vertex is not the bottom level, the entries in the child vertices of the selected vertex are redistributed so that the child vertex having a maximal index contains a predetermined number of entries. In the case of a deletion, the predetermined number equals the maximum number H that a vertex may contain. In the case of an insertion, the predetermined number is less than the maximum number and is preferably H−1. If the level of the child vertex is the bottom level the entry is inserted or deleted on the child vertex having the maximal index. If the level of the selected vertex is the bottom level the entry is inserted or deleted on the selected vertex.
In preferred forms of the invention, the process of deleting an entry from the search tree is performed by repeating the steps of the process using the child vertex having the maximal index found during one iteration for the selected vertex during the next iteration, until a child vertex is found in the bottom level.
In preferred forms of the invention, if the level of the child vertex is not the bottom level, the process of inserting an entry to the search tree is includes redistributing entries between grandchild vertices of the selected vertex that are children of the child vertex having the maximal index so that the grandchild vertex having a maximal index contains the predetermined number of entries. If the level of the grandchild vertex is the bottom level the entry is inserted on the grandchild vertex having the maximal index. If the level of the grandchild vertex is not the bottom vertex, the process is repeated using the child or grandchild vertex having the maximal index found during one iteration for the selected vertex during the next iteration, until a child or grandchild vertex is found in the bottom level.
The selection of the child or grandchild vertex as the selected vertex depends on whether the child vertex contains the maximum number (H) of entries. If the child vertex contains less than the maximum number of entries (H−1), the process is repeated using the child vertex during the next iteration. If the child vertex contains the maximum number of entries (H), the process is repeated using the grandchild vertex during the next iteration.
Another aspect of the present invention resides in a search tree that includes instrumentalities to carry out the process of the invention.
Another aspect of the present invention resides in the provision of computer readable program code that is embedded in a computer usable medium. The computer readable program code includes computer code that causes a computer to define the search tree and computer code that causes the computer to insert and delete entries to and from bottom vertices of the tree.
REFERENCES:
patent: 5123104 (1992-06-01), Levine et al.
patent: 5493678 (1996-02-01), Arcuri et al.
patent: 5710916 (1998-01-01), Barbara et al.
patent: 5758356 (1998-05-01), Hara et al.
patent: 6553370 (2003-04-01), Andreev et al.
patent: 6564211 (2003-05-01), Andreev et al.
Frederickson “Data structures for on-line updating of minimum spanning trees”, ACM 1983, pp. 252-257.*
Goodrich et al “Dynamic trees and dynamic point location”, ACM 1991, pp. 523-533.*
Cheetham et al “Adaptive structuring of binary search trees using conditional rotations”, IEEE 1993, pp. 695-704.*
Evans et al “Restructuring ordered binary trees”, Proceedings of the eleventh annual ACM-SIAM symposium on discrete algorithms, Feb. 2000, pp. 477-486.*
Eikerling et al “Automatic structuring and optimization of hierarchical designs”, IEEE 1996, 6 pages.*
Cohen et al “Dynamic expression trees and their applications”, Proceedings of the second annual ACM-SIAM symposium on discrete algorithms, Mar. 1991, pp. 52-61.
Andreev Alexander E.
Scepanovic Ranko
Le Uyen
LSI Logic Corporation
Westman Champlin & Kelly
LandOfFree
Editing protocol for flexible search engines does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Editing protocol for flexible search engines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Editing protocol for flexible search engines will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3251136