Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-07-14
2003-03-11
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06532457
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The preset invention relates to radix-search methods, and, in particular, to a method and system for achieving improved performance of radix-search methods by using a look-ahead tree structure in conjunction with a high band-width memory access.
The Binary Search Tree (BST) is a well-known and commonly-used data structure which, when coupled with an appropriate algorithm, can provide fast average-case performance for numerous symbol-table operations, including search, insert, select, and sort. BSTs are often appropriate for systems having wild cards, varying-length entries, and systems in which a longest-prefix match approach is necessary. BSTs are often particularly appropriate for text entries or text-containing entries.
The running time of algorithms on BSTs is dependent on the shape of the tree. Sedgewick (“Algorithms in C++”, Addison Wesley, 1998) in surveying the performance characteristics of BSTs, summarizes:
“Specifically, the path-length and height measures of binary trees . . . relate directly to the cost of searching in BSTs. The height is the worst-case cost of a search, the internal path length is directly related to the cost of search hits, and external path length is directly related to the cost of search misses.”
BSTs are known, however to have bad worst-case performance, and various approaches have been developed over the years to improve the structure (balance) of BSTs, including randomized BSTs, skip lists, splay BSTs, and optimization.
In another approach, termed radix-search methods, the search proceeds by examining the search keys one small piece at a time, rather than using full comparisons between keys at each step. Radix-search methods are particularly suited to handling variable-length keys. They also provide reasonable worst-case performance without the need to balance trees using one of the above-mentioned techniques.
Two important disadvantages, noted by Sedgewick, are that such search methods can make inefficient use of space, and that performance can suffer if efficient access to he bytes of the keys is not available.
In recent years, the market has made increasingly-dramatic demands on performance, a trend that, according to all indications, will continue in the foreseeable future. This is particularly true of networking applications. One approach to meeting these performance demands is to increase the band-width in order to access or transfer more data, in parallel, per clock cycle. While current bus widths of 16 bits and 32 bits are typical for memory access, it is possible to design memory access systems having bus widths of 256 bits, 512 bits, and more, particularly when working with embedded memory.
Unfortunately, current search methods (and devices) are not designed towards accessing so much data in an individual clock cycle. Thus, the amount of useful data that can be accessed does not increase in proportion to the increase in bus width. Conventional tree search techniques examine one node per memory access. In many common applications, the node contains only 20-60 bits of useful information, a far cry from the 256 bits or 512 bits that can be transferred in a single memory access.
There is therefore a recognized need for, and it would be highly advantageous to have, a look-ahead tree structure and a search method therefor, that would allow efficient utilization of the memory access potential of high band-width architectures, such that the information transfer would be significantly improved over what has been known heretofore.
SUMMARY OF THE INVENTION
The present invention is a method and system for achieving improved performance of radix-search methods by using a look-ahead tree structure in conjunction with a high band-width memory access.
According to the teachings of the present invention there is provided a method for storing and retrieving data using a radix-search tree having nodes and leaves comprising: (a) storing a plurality of nodes, each of the nodes having node-attributes, in a radix-search tree, and (b) retrieving the node-attributes of the plurality of nodes in a single memory access.
According to further features in the described preferred embodiments, the radix-search tree is stored in a contiguous memory block.
According to still further features in the described preferred embodiments, the plurality of node-attributes includes node-attributes of two nodes in series.
According to still further features in the described preferred embodiments, the plurality of node-attributes includes node-attributes of at least three nodes in series.
According to still further features in the described preferred embodiments, the plurality of node-attributes includes node-attributes of an entire sub-tree.
According to further features in the described preferred embodiments, the plurality of no e-attributes is arranged in at least one table.
According to still further features in the described preferred embodiments, the plurality of node-attributes includes at least one pointer pointing to at least one address located within the contiguous memory block.
According to still further features in the described preferred embodiments, the plurality of node-attributes includes at least one pointer pointing to at least one address selected from the group consisting of node address and leaf address, the at least one address being located outside of the contiguous memory block.
According to yet another aspect of the present invention there is provided a system for storing and retrieving data using a radix-search tree having nodes and leaves, wherein at least one node has a right child and a left child, the system comprising: (a) a data storage module for storing a plurality of sub-trees containing a plurality of nodes having node attributes, wherein the node attributes of at least one of the sub-trees are stored in a contiguous memory block, and (b) a processor that is operative to perform operations including: (i) transferring the node attributes of at least one of the sub-trees to the data storage module, and (ii) retrieving the node attributes of at least one of the sub-trees from the data storage module.
According to further features in the described preferred embodiments, the processor is operative to retrieve the node attributes of each of at least one of the sub-trees is a single memory access.
According to still further features in the described preferred embodiments, the node-attributes include a first pointer pointing to a node address within the contiguous memory block, and a second pointer pointing to a node address located outside of the contiguous memory block.
According to still further features in the described preferred embodiments, the node-attributes are arranged in at least one table.
According to still further features in the described preferred embodiments, the node-attributes include at least one pointer pointing to at least one address selected from the group consisting of node address and leaf address, the at least one address being located outside of the contiguous memory block.
According to still further features in the described preferred embodiments, the at least one pointer pointing to at least one address selected from the group consisting of node addresses and leaf address is stored in a separate table.
According to still further features in the described preferred embodiments, the plurality of node-attributes includes a single pointer that is used to identify t e memory addresses of both the right child and the left child of the node.
According to still further features in the described preferred embodiments, the memory addresses are stored in adjacent rows of the at least one table. The memory addresses can also be stored in adjacent columns of the at least one table.
According to still further features in the described preferred embodiments, the node-attributes include the node-attributes of two nodes in series.
According to still further features in the described preferred embodiments, the node-attributes include node-attributes of at least three nodes in series.
Acc
Gabbay Itzchak
Tal Alex
Ezchip Technologies Ltd.
Friedman Mark M.
Mizrahi Diane D.
Wu Yicun
LandOfFree
Look-ahead tree structure does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Look-ahead tree structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Look-ahead tree structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044729