Multidimensional hashed tree based URL matching engine using progressive hashing

• US 20050055437A1
• Filed: 09/09/2003
• Published: 03/10/2005
• Est. Priority Date: 09/09/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Srinivasan, Aravind, Burckart, Erik John
• Granted Patent: US 7,523,171 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A mechanism by which URLs are progressively hashed character by character and clauses of the URL are used to traverse a tree data structure for matching of the URL to resources/rules is provided. The hash code for a single character is appended to a prior hash code for a preceding character in the URL portion. At the time that the entire portion of the URL is hashed, as determined based on the presence of a delimiter character, the particular node in a tree data structure associated with the resulting hash code is identifiable within a hash table of a current node of the tree data structure. Each node in the tree data structure includes a multidimensional hash table for a portion of a URL. The multidimensional hash table is established and grown in a manner that ensures there are no hash collisions. Each portion of the URL is parsed in this manner and the tree data structure is traversed as each portion is processed until the entire URL is parsed at which time the resulting rules/resources may be identified from the leaf nodes of the tree data structure.

Claims

1. A method of matching a Uniform Resource Locator (URL) to a resource or rule, comprising:

progressively hashing a clause of the URL character by character to generate a hash code for the clause;

determining if a delimiting character is encountered;

using the hash code associated with the clause to traverse a tree data structure representing clauses of URLs and corresponding resources or rules, wherein each node of the tree data structure has an associated multidimensional hash table; and

matching the URL to resources or rules based on the traversing of the tree data structure.

2. The method of claim 1, wherein using the hash code includes calculating a target value based on the hash code and dimensions of a multidimensional hash table associated with a current node in the tree data structure.

3. The method of claim 2, wherein using the hash code further includes using the target value to identify an entry in the multidimensional hash table corresponding to a subtree associated with the clause.

4. The method of claim 3, wherein traversing the tree data structure includes setting the current node of the tree data structure to be a root node of the subtree associated with the clause.

5. The method of claim 2, wherein entries for subtrees in the multidimensional hash table are positioned in the multidimensional hash table using the equation:

T_h{(h % X), (h % Y), (h % Z)}

wherein T_h is a target object in the multidimensional hash table, h is a hash value for a root node of a subtree, and X, Y and Z are dimensions of the multidimensional hash table.

6. The method of claim 2, wherein the multidimensional hash table is created by growing the multidimensional hash table such that hash collisions are avoided.

7. The method of claim 6, wherein the multidimensional hash table is grown by a total number of dimensions for the multidimensional.

8. The method of claim 4, further comprising:

searching the current node for target resources or rules; and

adding any target resources or rules to a list of matched resources or rules.

9. The method of claim 4, further comprising:

determining if there are any child nodes of the current node corresponding to a “

wildcard”

node; and

adding any target resources or rules associated with the “

wildcard”

node to a list of matched resources or rules.

10. The method of claim 1, further comprising:

returning a list of matched resources or rules to a calling application.

11. A computer program product in a computer readable medium for matching a Uniform Resource Locator (URL) to a resource or rule, comprising:

first instructions for progressively hashing a clause of the URL character by character to generate a hash code for the clause;

second instructions for determining if a delimiting character is encountered;

third instructions for using the hash code associated with the clause to traverse a tree data structure representing clauses of URLs and corresponding resources or rules, wherein each node of the tree data structure has an associated multidimensional hash table; and

fourth instructions for matching the URL to resources or rules based on the traversing of the tree data structure.

12. The computer program product of claim 11, wherein the third instructions for using the hash code include instructions for calculating a target value based on the hash code and dimensions of a multidimensional hash table associated with a current node in the tree data structure.

13. The computer program product of claim 12, wherein the third instructions for using the hash code further include instructions for using the target value to identify an entry in the multidimensional hash table corresponding to a subtree associated with the clause.

14. The computer program product of claim 13, wherein the tree data structure is traversed by setting the current node of the tree data structure to be a root node of the subtree associated with the clause.

15. The computer program product of claim 12, wherein entries for subtrees in the multidimensional hash table are positioned in the multidimensional hash table using the equation:

T_h{(h % X), (h % Y), (h % Z)}

wherein T_h is a target object in the multidimensional hash table, h is a hash value for a root node of a subtree, and X, Y and Z are dimensions of the multidimensional hash table.

16. The computer program product of claim 12, wherein the multidimensional hash table is created by growing the multidimensional hash table such that hash collisions are avoided.

17. The computer program product of claim 16, wherein the multidimensional hash table is grown by a total number of dimensions for the multidimensional.

18. The computer program product of claim 14, further comprising:

fifth instructions for searching the current node for target resources or rules; and

sixth instructions for adding any target resources or rules to a list of matched resources or rules.

19. The computer program product of claim 14, further comprising:

fifth instructions for determining if there are any child nodes of the current node corresponding to a “

wildcard”

node; and

sixth instructions for adding any target resources or rules associated with the “

wildcard”

node to a list of matched resources or rules.

20. An apparatus for matching a Uniform Resource Locator (URL) to a resource or rule, comprising:

means for progressively hashing a clause of the URL character by character to generate a hash code for the clause;

means for determining if a delimiting character is encountered;

means for using the hash code associated with the clause to traverse a tree data structure representing clauses of URLs and corresponding resources or rules, wherein each node of the tree data structure has an associated multidimensional hash table; and

means for matching the URL to resources or rules based on the traversing of the tree data structure.