Interval tree for identifying intervals that intersect with a query interval

• US 7,512,617 B2
• Filed: 12/29/2004
• Issued: 03/31/2009
• Est. Priority Date: 12/29/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Lock, Hendrick C. R., Booss, Daniel
• Primary Examiner(s): Chace; Christian P.
• Assistant Examiner(s): Syed; Farhan M
• Application Number:
  US11/026,359
• Publication Number:
  US 20060143206A1
• Time in Patent Office: 1,553 Days
• Field of Search: 707/1, 707/100, 707/101, 707/200
• 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:

scheduling a task for a software application that manages a plurality of tasks by processing program code on a processing unit to perform the following;

performing a read operation on a cache and/or database at a region of said cache and/or database where information contained at node of an interval tree is stored, said information comprising first and second interval keys, a pointer and an interval, said first and second interval keys having corresponding first and second intervals, said pointer pointing to a lower node having lower interval keys, each of said lower interval keys having corresponding intervals that either;

a) all start within a range between said first interval'"'"'s start and said second interval'"'"'s start;

or,

b) all end within a range between said first interval'"'"'s end and said second interval'"'"'s end;

wherein said interval identifies the earliest start and latest end amongst all intervals having keys at or beneath said node within said interval tree;

determining if intervals associated with interval keys of said node and/or said node'"'"'s children have the potential to intersect a query interval by determining if said query interval overlaps said interval, wherein, said potential to intersect is deemed to exist if said query interval overlaps said interval;

looking amongst said intervals for an intersection with said query interval if said potential to intersect is deemed to exist, or, referring to another node that is higher than said node within said interval tree if said potential to intersect is deemed not to exist; and

,

scheduling said task because other scheduled tasks do not conflict with said task over said query interval, said scheduled task recorded in a machine readable storage medium.

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

a) above applies 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

b) above applies.

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 and latest end amongst all intervals associated with 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 interval identifying the earliest start and latest end amongst all intervals associated with interval keys at said leaf node within said interval tree.

8. The method of claim 7 wherein a second pointer is associated with said second interval, said second pointer pointing 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 interval keys'"'"' corresponding intervals 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.

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

scheduling a task for a software application that manages a plurality of tasks by processing program code on a processing unit to perform the following;

performing a read operation on a cache and/or database at a region of said cache and/or database where information contained at node of an interval tree is stored, said information comprising first and second interval keys, a pointer and an interval, said first and second interval keys having corresponding first and second intervals, said pointer pointing to a lower node having lower interval keys, each of said lower interval keys having corresponding intervals that either;

a) all start within a range between said first interval'"'"'s start and said second interval'"'"'s start;

or,

b) all end within a range between said first interval'"'"'s end and said second interval'"'"'s end;

wherein said interval identifies the earliest start and latest end amongst all intervals having keys at or beneath said node within said interval tree; and

,

determining if intervals associated with interval keys of said node and/or said node'"'"'s children have the potential to intersect a query interval by determining if said query interval overlaps said interval, wherein, said potential to intersect is deemed to exist if said query interval overlaps said interval;

looking amongst said intervals for an intersection with said query interval if said potential to intersect is deemed to exist, or, referring to another node that is higher than said node within said interval tree if said potential to intersect is deemed not to exist; and

,

scheduling said task because other scheduled tasks do not conflict with said task over said query interval, said scheduled task recorded in a machine readable storage medium.

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

a) above applies 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

b) above applies.

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 and latest end amongst all intervals associated with 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 interval identifying the earliest start and latest end amongst all intervals associated with interval keys at said leaf node within said interval tree.

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

19. The article of manufacture of claim 11 wherein said interval keys'"'"' corresponding intervals 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:

a processing unit;

program code stored on a machine readable storage medium, said program code capable of being executed by said processing unit to perform a method, said method comprising;

scheduling a task for a software application that manages a plurality of tasks by processing program code on a processing unit to perform the following;

performing a read operation on a cache and/or database at a region of said cache and/or database where information contained at node of an interval tree is stored, said information comprising first and second interval keys, a pointer and an interval, said first and second interval keys having corresponding first and second intervals, said pointer pointing to a lower node having lower interval keys, each of said lower interval keys having corresponding intervals that either;

a) all start within a range between said first interval'"'"'s start and said second interval'"'"'s start;

or,

b) all end within a range between said first interval'"'"'s end and said second interval'"'"'s end;

wherein said interval identifies the earliest start and latest end amongst all intervals having keys at or beneath said node within said interval tree; and

,

determining if intervals associated with interval keys of said node and/or said node'"'"'s children have the potential to intersect a query interval by determining if said query interval overlaps said interval, wherein, said potential to intersect is deemed to exist if said query interval overlaps said interval;

looking amongst said intervals for an intersection with said query interval if said potential to intersect is deemed to exist, or, referring to another node that is higher than said node within said interval tree if said potential to intersect is deemed not to exist; and

,

scheduling said task because other scheduled tasks do not conflict with said task over said query interval, said scheduled task recorded in a machine readable storage medium.

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

a) above applies 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

b) above applies.

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 and latest end amongst all intervals associated with 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 interval identifying the earliest start and latest end amongst all intervals associated with interval keys at said leaf node within said interval tree.

28. The computing system of claim 27 wherein a second pointer is associated with said second interval, said second pointer pointing 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 interval keys'"'"' corresponding intervals 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.