CODEWITHSUNDEEP
javaalgorithmdata-structures
Werner Lehmann
Werner Lehmann

Reputation: 911

How to find 1 or more partially intersecting time-intervals in a list of few million?

I need an idea for an efficient index/search algorithm, and/or data structure, for determining whether a time-interval overlaps zero or more time-intervals in a list, keeping in mind that a complete overlap is a special case of partial overlap . So far I've not not come up with anything fast or elegant...

Consider a collection of intervals with each interval having 2 dates - start, and end.

Intervals can be large or small, they can overlap each other partially, or not at all. In Java notation, something like this:

interface Period 
{
  long getStart(); // millis since the epoch
  long getEnd();
  boolean intersects(Period p); // trivial intersection check with another period
}

Collection<Period> c = new ArrayList<Period>(); // assume a lot of elements

The goal is to efficiently find all intervals which partially intersect a newly-arrived input interval. For c as an ArrayList this could look like...

Collection<Period> getIntersectingPeriods(Period p)
{
  // how to implement this without full iteration?
  Collection<Period> result = new ArrayList<Period>();
  for (Period element : c)
    if (element.intersects(p))
      result.add(element);
  return result;
}

Iterating through the entire list linearly requires too many compares to meet my performance goals. Instead of ArrayList, something better is needed to direct the search, and minimize the number of comparisons.

My best solution so far involves maintaining two sorted lists internally and conducting 4 binary searches and some list iteration for every request. Any better ideas?

Editor's Note: Time-intervals are a specific case employing linear segments along a single axis, be that X, or in this case, T (for time).

Upvotes: 9

Views: 1726

Answers (2)

Jules
Jules

Reputation: 6346

Interval trees will do:

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree...

Upvotes: 11

WGroleau
WGroleau

Reputation: 455

Seems the Wiki article solves more than was asked. Are you tied to Java?

You have a "huge collection of objects" which says to me "Database" You asked about "built-in period indexing capabilities" and indexing says database to me.

Only you can decide whether this SQL meets your perception of "elegant":

 Select A.Key as One_Interval,
        B.Key as Other_Interval
 From Big_List_Of_Intervals as A join Big_List_Of_Intervals as B
   on A.Start between B.Start and B.End OR
      B.Start between A.Start and A.End

If the Start and End columns are indexed, a relational database (according to advertising) will be quite efficient at this.

Upvotes: 0

Related Questions