Method for determining a most probable K location

• US 20070233723A1
• Filed: 04/04/2006
• Published: 10/04/2007
• Est. Priority Date: 04/04/2006
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Mazzagatti, Jane
• Granted Patent: US 8,238,351 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

The process of traversing a K may involve determining a match between a root node and a Result node of a node on the asCase list of a current K node. When learning is off and a match is not found, the procedure may ignore the particle being processed. An alternative solution determines which node on the asCase list is the most likely to be the next node. While the K Engine is traversing and events are being recorded into a K structure, a count field may be added to each K node to contain a record of how many times each K path has been traversed. The count field may be updated according to the processes traversing the K. Typically, the count is incremented only for learning functions. This count field may be used in determining which node may be the most (or least) probable.

Claims

1. A method for processing a particle stream having at least one particle in a KStore system having a current K node, comprising:

receiving said at least one particle within said particle stream to provide a received particle;

determining a match in accordance with said received particle and said current K node to provide a match determination; and

determining a most probable node in accordance with said match determination.

2. The method for processing a particle of claim 1, further comprising determining said most probable node if said match determination is negative.

3. The method for processing a particle stream of claim 1, further comprising determining said most probable node if said match determination is positive.

4. The method for processing a particle of claim 1, further comprising determining said most probable node in accordance with an asCase node of said current K node.

5. The method for processing a particle stream of claim 4, further comprising determining said most probable node in accordance with a node count of said asCase node.

6. The method for processing a particle stream of claim 5, wherein said node count is representative of a number of build operations performed on said asCase node.

7. The method for processing a particle stream of claim 5, wherein said node count is representative of a number of query operations performed on said asCase node.

8. The method for processing a particle stream of claim 5, wherein said most probable node is provided with a count field for storing said node count further comprising providing said most probable node with at least one additional field for storing at least one further node count.

9. The method for processing a particle stream of claim 5, wherein said asCase node is provided with at least one additional field further comprising:

storing a value representative of a number of build operations performed on said asCase node in one of said count field and said at least one additional field; and

storing a value representative of a number of query operations performed on said asCase node in the other of said count field and said at least one additional field.

10. The method for processing a particle stream of claim 5, further comprising determining said most probable node in accordance with a plurality of asCase nodes of said current K node.

11. The method for processing a particle stream of claim 10, wherein the asCase nodes of said plurality of asCase node are provided with respective node counts further comprising determining said most probable node in accordance with a node count of an asCase node of said plurality of asCase nodes.

12. The method for processing a particle stream of claim 11, further comprising determining said most probable node in accordance with a largest node count of said plurality of node counts.

13. The method for processing a particle stream of claim 12, further comprising determining said largest node count of said plurality of node counts while searching said asCase nodes.

14. The method for processing a particle stream of claim 11, further comprising determining said most probable node in accordance with a least node count of said plurality of node counts.

15. The method for processing a particle stream of claim 4, further comprising determining said most probable node in accordance with a location of a node on the asCase list of the current K node.

16. The method for processing a particle stream of claim 4, further comprising determining said most probable node in accordance with a further asCase node of the nodes on the asCase list of the current K node.

17. The method for processing a particle stream of claim 4, further comprising traversing from a current K node to a plurality of end product nodes to determine an end product node list.

18. The method for processing a particle stream of claim 17, further comprising determining said most probable node in accordance with said determined end product node list.

19. The method for processing a particle stream of claim 18, further comprising determining a most probable node for a further particle in accordance with a previously determined end product node list.

20. The method for processing a particle stream of claim 4, further comprising determining a most probable node in accordance with a Result node of an asCase node.

21. The method for processing a particle stream of claim 1, further comprising determining a most probable node in accordance with an adjacent node.

22. The method for processing a particle stream of claim 21, further comprising determining a most probable node in accordance with a plurality of adjacent nodes.

23. The method for processing a particle stream of claim 1, further comprising determining a most probable node in accordance with a Case node of current K node.

24. The method for processing a particle stream of claim 1, wherein a most probable node determines a most probable path.

25. The method for processing a particle stream of claim 1, further comprising setting said current K node to said most probable node.

26. The method for processing a particle stream of claim 1, further comprising setting said current K node to a matched node if said match determination is positive.

27. The method for processing a particle stream of claim 1, further comprising determining whether said KStore includes any KStore levels higher than said current KStore level to provide a higher KStore level determination.

28. The method for processing a particle stream of claim 27, wherein said KStore is provided with current K node data further comprising determining a higher level current K node on a higher KStore level in accordance with said current K node data.

29. The method for processing a particle stream of claim 1, wherein said determining a match further comprises:

determining a completed level in accordance with said received particle and matched end product node above the elemental root nodes;

determining a root node in accordance with the current KStore level;

determining a higher level current K node on a higher KStore level in accordance with said current K node data;

determining a match in accordance with said current level root node and said higher level current K node to provide a higher level match determination and

determining a most probable node in accordance with said higher level match determination.

30. The method for processing a particle stream of claim 29, further comprising determining an asCase node of a higher level current K node.

31. The method for processing a particle stream of claim 30, further comprising determining said most probable node in accordance with said asCase node of said higher level current K node.

32. The method for processing a particle stream of claim 30, further comprising determining said most probable node in accordance with a plurality of asCase nodes of said higher level current K node.

33. The method for processing a particle stream of claim 32, further comprising determining said most probable node in accordance with a node count of an asCase node of said plurality of asCase nodes.

34. The method for processing a particle stream of claim 33, further comprising determining said most probable node in accordance with a largest node count of said plurality of node counts.

35. The method for processing a particle stream of claim 34, further comprising determining said largest node count of said plurality of node counts while searching said asCase nodes of said higher level current K node.

36. The method for processing a particle stream of claim 33, further comprising determining said most probable node in accordance with a least node count of said plurality of node counts.

37. The method for processing a particle stream of claim 31, further comprising determining said most probable node in accordance with a location of a node on the asCase list of the higher level current K node.

38. The method for processing a particle stream of claim 31, further comprising determining said most probable node in accordance with a further asCase node of the asCase list of the higher level current K node.

39. The method for processing a particle stream of claim 31, further comprising traversing from higher level current K node to a plurality of end product nodes to determine an end product node list.

40. The method for processing a particle stream of claim 39, further comprising determining a most probable node list in accordance with said determined end product node list.

41. The method for processing a particle stream of claim 29, further comprising setting said higher level current K node to said most probable node.

42. The method for processing a particle stream of claim 1, further comprising setting said higher level current K node to a matched node if said match determination is positive.