Searching temporal data

I developing an application (in C#) where objects are开发者_StackOverflow active under a period of time, they have from and to properties of DateTime-type. Now I want to speed up my search routine for queries like: Are there other active objects in this timeperiod/at this time.

Is there any existing temporal index I can use or can I use QuadTree/other tree-structures to search in an efficient way.

You should also take a look at the interval tree:

In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.

And that reminds me of this SO question.

Why not just order your data in a list, and then use a binary search-like algorithm to limit the number of objects you consider.

This is an interesting sorting problem, as you need to consider both the start and end date of each element. If you used a simple sorting algorithm, then you could sort by either start date or end date, but sorting by both wouldn't be very effective, as an element with an early start date could have a very late end date, or an element with a late start date could have an early end date, meaning that you can't really pre-sort this list based on the criteria "are any of these elements active right now?"

If you're looking for a super-efficient mechanism to do this, I may not have an answer for you, but if you're just looking for something easy to do with existing C# data structures, I'd consider creating two sorted lists, one sorted by start date and the other sorted by end date. Search the start-date-sorted list for elements that start before right now and search the end-date-sorted list for elements that end after right now. Intersect those results to get your final answer.

As I mentioned, I'm sure there is a more efficient mechanism out there to do this, but if I wanted to keep it simple and just use what I had available, I would consider doing that.

There is an i4o (indexes for objects) library. May be it would be useful.