Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability
First Claim
1. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
- inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.
5 Assignments
0 Petitions
Accused Products
Abstract
A method of searching utilizing a longest match based Radix Search Trie with variable length keys and having the ability to handle keys being prefixes of other keys. The method is based on the well known Patricia search trie algorithm. The address prefixes representing the keys for the tree are modified before being processed by the algorithm. A single byte is added to the beginning of each address prefix which is set equal to the length of the address prefix. The combined address length byte followed by the address prefix is used by the Patricia algorithm . When one address is the prefix of another, the length byte will make both addresses unique and distinct from each other. The conventional Patricia search can now be used since the keys have been made unique. A circular prefix list is maintained in descending numerical order comprising an entry for each distinct value of address length insure that the longest matching address is found.
-
Citations
19 Claims
-
1. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
-
inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
-
inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof, said step of modifying a key comprises adding a byte of data to the beginning of a key, said byte of data having a value equal to the length of said key, said byte of data comprises a Private Network Node Interface (PNNI) level value;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.
-
-
16. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
-
inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field, said list comprising a circularly linked list;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.
-
-
17. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
-
inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
storing a plurality of identical keys in a circularly linked list, said circularly linked list stored in said tree in similar fashion to that of other keys;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.
-
-
18. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
-
inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list, said determining comprises the step of maintaining a longest length variable indicating the entry in said list with the longest length;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.
-
-
19. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:
-
inserting a key into the tree;
modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;
inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;
providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field, said list comprising a circularly linked list;
updating said list so as to maintain said entries in descending numerical order of the length field;
searching the tree for a search key;
determining the largest key length in said list;
concatenating the key length onto the search key to form a modified search key;
searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and
determining the next largest key length in said list by traversing the list to the next entry pointed to by the current entry and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.
-
Specification