Lock-free wild card search data structure and method

• US 6,662,184 B1
• Filed: 09/22/2000
• Issued: 12/09/2003
• Est. Priority Date: 09/23/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation, Mascotech, Inc. (Metaldyne Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Friedberg, Stuart A.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): THAI, HANH B
• Application Number:
  US09/668,776
• Time in Patent Office: 1,173 Days
• Field of Search: 707/100, 707/103.R, 707/103.Y, 707/103, 707/103.Z
• US Class Current: 707/754
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A data structure adapted for storage in a computer memory for receiving executable instructions. The data structure is a modified binary tree in the form of a quaternary tree guaranteeing at least two of four way branching at each internal node. In addition to the binary nodes, the tree may comprise a wildcard node and/or an epsilon node. The wildcard nodes point at keys of arbitrary descendants, and epsilon nodes reference an end of a data string at a specific length. In addition to the data structure, a method of traversing the data structure is disclosed for searching and retrieving data stored thereon. A method of modifying the data stored on the data structure is also disclosed. The searching algorithms include flags for controlling the tightness of a search and filters for searching prefixes and suffixes of a string. In conjunction with traversing the tree, a method of modifying the data structure is disclosed. The modification process includes a insertion process for adding data to the data structure, and a deletion process for removing data from the data structure. Both the insertion and deletion processes maintain and guarantee the two of four way branching of the data structure. Accordingly, the novel data structure is designed to permit users to access the data structure at the same time as a modification is occurring.

Claims

1. A computer-readable medium having stored thereon a search tree data structure usable for classifying data in a computer system, the search tree comprising:

a plurality of internal nodes, each internal node including;

at least two pointer fields corresponding to specific alphabetic values;

a wildcard pointer field corresponding to all of the alphabetic values;

an epsilon pointer field corresponding to the end of a data string at a specific length; and

pointers in at least two of the pointer fields, such that the tree guarantees two of four way branching at each internal node.

2. The search tree data structure of claim 1, wherein the internal nodes point at keys of possible children in the form of arbitrary descendants.

3. The search tree data structure of claim 1, wherein at least some of the pointers points to external nodes.

4. The search tree data structure of claim 3, wherein the external nodes include pointers to siblings.

5. The search tree data stricture of claim 1, wherein the search tree is a quaternary search tree;

wherein the internal nodes include two alphabetic value pointer fields referencing binary bit values; and

wherein the search tree guarantees at least two of four way branching at each internal node.

6. A method for classifying data, comprising the steps of:

creating the search tree data structure of claim 5; and

traversing the search tree.

7. A method for classifying data, comprising the steps of:

creating a quaternary search tree data structure comprising a plurality of internal nodes, each internal node including;

two pointer fields corresponding to bit values;

a wildcard pointer field corresponding to both bit values;

an epsilon pointer field corresponding to the end of a data string at a specific length; and

pointers in at least two of the pointer fields, such that the search tree guarantees two of four way branching at each internal node; and

traversing the search tree.

8. The method of claim 7, further comprising the step of returning multiple data string matches upon completion of the traversing step.

9. The method of claim 8, wherein the data string matches include partial data string matches.

10. The method of claim 7, wherein the step of traversing includes:

controlling tightness of data string matches using a flag; and

searching prefixes and suffixes of a data string using a filter.

11. The method of claim 10,

wherein the flag is a best;

and

wherein the step of traversing selects matches more specific than any other matches.

12. The method of claim 10,

wherein the filter is a long filter;

and

wherein the step of traversing the tree searches for a key data string having a length greater than the search data string.

13. The method of claim 10,

wherein the filter is a short filer;

and

wherein the step of traversing the tree searches for a key data string having a length shorter than the search data string.

14. The method of claim 10,

wherein the filter is a not equal filter;

and

wherein the step of traversing the tree searches for a key data string having a length not equal to the search data string.

15. The method of claim 10,

wherein the filter is a long or short filer;

and

wherein the step of traversing the tree searches for a key data string having a length longer or shorter than search data string.

16. The method of claim 7, further comprising the step of inserting a node into the search tree.

17. The method of claim 16, wherein the step of inserting a node includes the steps of:

creating a new external node with the new key string;

determining an insertion location for the external node; and

adding the new external node to the tree while maintaining two of four way branching at each internal node of the search tree and while maintaining consistency of concurrent traversals of the search tree.

18. The method of claim 7, further comprising the step of deleting a node from the search tree.

19. The method of claim 18, wherein the step of deleting a node includes the steps of:

removing the external node from the search tree while maintaining two of four way branching at each internal node of the search tree and while maintaining consistency of concurrent traversals of the search tree; and

destroying the removed external node upon completion of all references to it.

20. An article comprising:

a computer-readable signal-bearing medium;

means in the medium for creating a search tree data structure usable for classifying data in a computer system, the search tree comprising a plurality of internal nodes, each internal node including;

at least two pointer fields corresponding to specific alphabetic values;

a wildcard pointer field corresponding to all of the alphabetic values;

an epsilon pointer field corresponding to the end of a data string at a specific length, and

pointers in at least two of the pointer fields, such that the tree guarantees two of four way branching at each internal node; and

means in the medium for traversing the tree of the data structure.

21. The article of claim 20, further comprising means in the medium for returning data string matches upon completion of the traversal of the tree.

22. The article of claim 21, wherein the data string matches are returned to a transmission routing device.

23. The article of claim 20, wherein the medium is a recordable data storage medium.

24. The article of claim 20, wherein the medium is a modulated carrier signal.

25. A computer system having a computer-readable medium comprising:

a quaternary search tree data structure comprising a plurality of internal nodes, each internal node including;

at least two pointer fields corresponding to specific alphabetic values;

a wildcard pointer field corresponding to all of the alphabetic values;

an epsilon pointer field corresponding to the end of a data string at a specific length; and

pointers in at least two of the pointer fields, such that the search tree guarantees two way branching at each internal node; and

tree traversal logic responsive to a search data string and to the search tree; and

tree modification logic responsive to a modify data string and to the search tree.

26. The system of claim 25, father comprising a search flag;

wherein the tree traversal logic controls the tightness of a match between the search data string and a node data string in response to the search flag.

27. The system of claim 26, wherein the flag is selected from the group consisting of matching all bit values;

matching only exact bit values;

matching the best from a list of values; and

combinations thereof.

28. The system of claim 25, further comprising a search filter;

wherein the tree traversal logic searches prefix and suffix data string in response to the search filter.

29. The system of claim 28, wherein the search filter is selected from the group consisting of:

data of equal length to the search data string;

data strings having a length greater than the search data string;

data strings having a length shorter than the search data string;

data strings having a length not equal to the search data string; and

data strings shorts or longer than the search data strings.

30. The system of claim 25, further comprising:

a search flag; and

a search filter;

wherein the tree traversal logic controls the tightness of a match between the search data string and a node data string in response to the search flags; and

wherein the tree traversal logic searches prefix and suffix data of the data string in response to the search filter.

31. The system of claim 25, further including a routing device, response to data string matches returned by the tree traversal logic, for routing data transmissions between telecommunication nodes represented by the data string matches.