Interval tree for identifying intervals that intersect with a query interval
AssigneeSap SE
InventorsHendrik Lock, Daniel Booss
Life of this patent
Estimating the term…
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.
Claims35
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.
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.
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.
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.
Dependencies are inferred from the claim text.