Interval tree for identifying intervals that intersect with a query interval

• US 20060143206A1
• Filed: 12/29/2004
• Published: 06/29/2006
• Est. Priority Date: 12/29/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Booss, Daniel, Lock, Hendrik C.R.
• Granted Patent: US 7,512,617 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method operable with a computing system is described for identifying which time interval keys within an interval tree intersect with a query interval. The method comprises accessing information from a node of the interval tree. The node comprises a time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath the node within the interval tree. The method also comprises determining if one or more of the node'"'"'s children have the potential to intersect a query interval based upon the time interval.

Claims

1. A method, comprising:

accessing information from a node of an interval tree that is at least partially cached and/or stored in a database, said node comprising a time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said node within said interval tree; and

,

determining if one or more of said node'"'"'s children have the potential to intersect a query interval based upon said time interval.

2. The method of claim 1 wherein said node is said interval tree'"'"'s root node.

3. The method of claim 1 wherein said node is an index node within said interval tree.

4. The method of claim 1 wherein said interval tree sorts by start time and said determining comprises:

determining if said query interval starts after said latest end time;

determining if said query interval ends before said earliest start time.

5. The method of claim 1 wherein said interval tree sorts by end time.

6. The method of claim 1 wherein a child node of said node has potential to intersect said query interval, said method further comprising:

accessing information from said child node, said child node comprising a second time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said child node within said interval tree.

7. The method of claim 6 wherein said child node is a leaf node, said second time interval identifying the earliest start time and latest end time amongst all time interval keys at said leaf node within said interval tree.

8. The method of claim 7 wherein said second time interval also includes a pointer from said child node to said node, said method further comprising jumping from said child node to said node with said pointer.

9. The method of claim 1 wherein said time interval keys correspond to activities scheduled on a resource.

10. The method of claim 9 wherein said accessing is in response to an inquiry into whether another activity can be scheduled on said resource over the course of said query interval.

16. The article of manufacture of claim 11 wherein a child node of said node has potential to intersect said query interval, said method further comprising:

accessing information from said child node, said child node comprising a second time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said child node within said interval tree.

17. The article of manufacture of claim 16 wherein said child node is a leaf node, said second time interval identifying the earliest start time and latest end time amongst all time interval keys at said leaf node within said interval tree.

18. The article of manufacture of claim 17 wherein said second time interval also includes a pointer from said child node to said node, said method further comprising jumping from said child node to said node with said pointer.

32. The apparatus of claim 1 wherein said node is said interval tree'"'"'s root node.

33. The apparatus of claim 1 wherein said node is an index node within said interval tree.

34. The apparatus of claim 1 wherein said interval tree sorts by start time and said determining comprises:

determining if said query interval starts after said latest end time;

determining if said query interval ends before said earliest start time.

35. The apparatus of claim 1 wherein said interval tree sorts by end time.

11. An article of manufacture including program code which, when executed by a machine, causes the machine to perform a method, the method comprising:

accessing information from a node of an interval tree that is at least partially cached and/or stored in a database, said node comprising a time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said node within said interval tree; and

,

determining if one or more of said node'"'"'s children have the potential to intersect a query interval based upon said time interval.

12. The article of manufacture of claim 11 wherein said node is said interval tree'"'"'s root node.

13. The article of manufacture of claim 11 wherein said node is an index node within said interval tree.

14. The article of manufacture of claim 11 wherein said interval tree sorts by start time and said determining comprises:

determining if said query interval starts after said latest end time;

determining if said query interval ends before said earliest start time.

15. The article of manufacture of claim 11 wherein said interval tree sorts by end time.

19. The article of manufacture of claim 11 wherein said time interval keys correspond to activities scheduled on a resource.

20. The article of manufacture of claim 19 wherein said accessing is in response to an inquiry into whether another activity can be scheduled on said resource over the course of said query interval.

21. A computing system comprising instructions disposed on a computer readable medium, said instructions capable of being executed by said computing system to perform a method, said method comprising:

accessing information from a node of an interval tree that is at least partially cached and/or stored in a database, said node comprising a time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said node within said interval tree; and

,

determining if one or more of said node'"'"'s children have the potential to intersect a query interval based upon said time interval.

22. The computing system of claim 21 wherein said node is said interval tree'"'"'s root node.

23. The computing system of claim 21 wherein said node is an index node within said interval tree.

24. The computing system of claim 21 wherein said interval tree sorts by start time and said determining comprises:

determining if said query interval starts after said latest end time;

determining if said query interval ends before said earliest start time.

25. The computing system of claim 21 wherein said interval tree sorts by end time.

26. The computing system of claim 21 wherein a child node of said node has potential to intersect said query interval, said method further comprising:

accessing information from said child node, said child node comprising a second time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said child node within said interval tree.

27. The computing system of claim 26 wherein said child node is a leaf node, said second time interval identifying the earliest start time and latest end time amongst all time interval keys at said leaf node within said interval tree.

28. The computing system of claim 27 wherein said second time interval also includes a pointer from said child node to said node, said method further comprising jumping from said child node to said node with said pointer.

29. The computing system of claim 21 wherein said time interval keys correspond to activities scheduled on a resource.

30. The computing system of claim 29 wherein said accessing is in response to an inquiry into whether another activity can be scheduled on said resource over the course of said query interval.

31. An apparatus, comprising:

means for accessing information from a node of an interval tree that is at least partially cached and/or stored in a database, said node comprising a time interval that identifies the earliest start time and latest end time amongst all time interval keys at or beneath said node within said interval tree; and

,

means for determining if one or more of said node'"'"'s children have the potential to intersect a query interval based upon said time interval.