Sorted intervals query

Question

I'm in search for a data structure which efficiently operates over closed intervals with the following properties:

• dynamically add or remove an interval

• set, and anytime change, a number ("depth") for each interval. no two depths are ever the same

• find all intervals that overlap with any given interval, sorted by "depth"

The closest structure I found is Interval tree but it lists the found intervals in arbitrary order with respect to their depths. I could collect all the "unsorted" intervals as reported and sort them afterwards but I was hopping it was possible to avoid to sort the result for every query.

Please, does anyone know of such data structure or have any suggestion how (if at all possible) to enhance the Interval tree to support such sorting?

Example:

1. add [1,2] to the empty structure and set its depth to 1
2. add [10,100], depth = 2
3. add [5,55], depth = 3
4. query for [5,50] reports [10,100] and [5,55]
5. set depth of [10,100] to 3, and of [5,55] to 2
6. query for [5,50] reports [5,55] and [10,100]

Edit

I'm more interested in fast adds/removes and queries, than in updating of depths. A depth can take as much as O(n), if that helps speed-up the other operations.

Answer 1

Let's assume that the algorithm you want exists. Then let's create a set of a million intervals, each being [1, 1], with random depths, and insert them into such interval tree. Then let's query the interval [1, 1]. It should return all the intervals in sorted order, with complexity O(M + log N), but N = 1, so we are sorting a set of M elements in linear time.

In other words, sorting elements by depth after you get them from the interval tree is as good in terms of complexity as it is theoretically possible.

Answer 2

The depth as you set it, is equivalent to the position of intervals in their imaginary list. So, the usual list of pairs of numbers is enough. List can easily add, remove or switch its items.

If you will need also to find the depth for the given interval, make a function for it (you didn't mention the need, though)

Answer 3

Here's my solution in Java using a TreeMap which is basically a Binary-Tree

Test: http://ideone.com/f0OlHI

Complexity

     Insert : 2 * O(log n)

     Remove : 2 * O(log n)

     Search : 1 * O(log n)

ChangeDepth : 7 * O(log n)

findOverlap : O(n)

---

IntervalDataSet.java

class IntervalDataSet
{
    private TreeMap<Integer,Interval> map;

    public IntervalDataSet ()
    {
        map = new TreeMap<Integer,Interval> ();
    }

    public void print ()
    {
        for(Map.Entry<Integer,Interval> entry : map.entrySet())
        {
          Integer key = entry.getKey();
          Interval value = entry.getValue();

          System.out.println(key+" => ["+value.min+","+value.max+"] ");
        }
    }

    public boolean changeDepth (int depth, int newDepth)
    {
        if (!map.containsKey(depth)) return false;

        if (map.containsKey(newDepth)) return false;

        Interval in = map.get(depth);

        in.depth = newDepth;

        remove(depth); insert(in);

        return true;
    }

    public boolean insert (Interval in)
    {
        if (in == null) return false;

        if (map.containsKey(in.depth)) return false;

        map.put(in.depth, in); return true;
    }

    public boolean remove (int depth)
    {
        if (!map.containsKey(depth)) return false;

        map.remove(depth); return true;
    }

    public Interval get (int depth)
    {
        return map.get(depth);
    }

    public void print (int depth)
    {
        if (!map.containsKey(depth))
          System.out.println(depth+" => X ");
        else
          map.get(depth).print();
    }

    public void printOverlappingIntervals (Interval in)
    {
        for (Interval interval : map.values())
            if (interval.intersect(in))
                interval.print();
    }

    public ArrayList<Interval> getOverlappingIntervals (Interval in)
    {
        ArrayList<Interval> list = new ArrayList<Interval>();

        for (Interval interval : map.values())
            if (interval.intersect(in))
                list.add(interval);

        return list;
    }

    public int size ()
    {
        return map.size();
    }

}

Interval.java

class Interval
{
    public int min;
    public int max;
    public int depth;

    public Interval (int min, int max, int depth)
    {
        this.min = min;
        this.max = max;
        this.depth = depth;
    }

    public boolean intersect (Interval b)
    {
        return (b != null
            && ((this.min >= b.min && this.min <= b.max)
                || (this.max >= b.min && this.max <= b.max))
            );
    }

    public void print ()
    {
        System.out.println(depth+" => ["+min+","+max+"] ");
    }
}

Test.java

class Test
{
  public static void main(String[] args) 
  {
    System.out.println("Test Start!");
    System.out.println("--------------");

    IntervalDataSet data = new IntervalDataSet ();

    data.insert(new Interval( 1,3, 0 ));
    data.insert(new Interval( 2,4, 1 ));
    data.insert(new Interval( 3,5, 3 ));
    data.insert(new Interval( 4,6, 4 ));
    System.out.println("initial values");
    data.print();

    System.out.println("--------------");
    System.out.println("Intervals overlapping [2,3]");

    data.printOverlappingIntervals(new Interval( 2,3, -1 ));
    System.out.println("--------------");

    System.out.println("change depth 0 to 2");
    data.changeDepth( 0, 2 );
    data.print();
    System.out.println("--------------");

    System.out.println("remove depth 4");
    data.remove( 4 );
    data.print();
    System.out.println("--------------");

    System.out.println("change depth 1 to 4");
    data.changeDepth( 1, 4 );
    data.print();
    System.out.println("--------------");

    System.out.println("Test End!");
  }
}

---

IntervalDataSet2

Complexity

initialization : O(n)

   findOverlap : 2 * O(log n) + T(merge)

---

class IntervalDataSet2
{
    private Integer [] key;
    private TreeMap<Integer,Interval> [] val;
    private int min, max, size;

    public IntervalDataSet2 (Collection<Interval> init)
    {
        TreeMap<Integer,TreeMap<Integer,Interval>> map
            = new TreeSet<Integer,TreeMap<Integer,Interval>> ();

        for (Interval in : init)
        {
            if (!map.containsKey(in.min))
                map.put(in.min,
                    new TreeMap<Integer,Interval> ());

            map.get(in.min).put(in.depth,in);

            if (!map.containsKey(in.max))
                map.put(in.max,
                    new TreeMap<Integer,Interval> ());

            map.get(in.max).put(in.depth,in);
        }

        key = new Integer [map.size()];
        val = new TreeMap<Integer,Interval> [map.size()];

        int i = 0;
        for (Integer value : map.keySet())
        {
            key [i] = value;
            val [i] = map.get(value);
            i++ ;
        }

        this.size = map.size();
        this.min = key [0];
        this.max = key [size-1];

    }

    private int binarySearch (int value, int a, int b)
    {
        if (a == b)
            return a;

        if (key[(a+b)/2] == value)
            return ((a+b)/2);

        if (key[(a+b)/2] < value)
            return binarySearch(value, ((a+b)/2)+1, b);
        else
            return binarySearch(value, (a, (a+b)/2)-1);
    }

    public TreeMap<Integer,Interval> findOverlap (Interval in)
    {
        TreeMap<Integer,Interval> solution
            = new TreeMap<Integer,Interval> ();

        int alpha = in.min;
        int beta = in.max;

        if (alpha > this.max || beta < this.min)
            return solution;

        int i = binarySearch(alpha, 0,(size-1));
        int j = binarySearch(beta, 0,(size-1));

        while (alpha <= beta && key[i] < alpha) i++;
        while  (alpha <= beta && key[j] > beta) j--;

        for (int k = i; k <= j; k++)
            solution.addAll ( val[k] );

        return solution;
    }

}

Answer 4

In the end it is quite difficult to think about this problems. What you have are actually a one dimensional space actualy a line. By adding the depth you get a second coordinate. By requesting that the depth is unique you can draw a picture actually.

Your query is to intersect every interval (line) of your picture with a rectangle from x1 to x2 and every y in Y.

So the naive look at this problem is to compare each line in the order of y if it intersects. Since you want all results this would require O(n) in order to find the answer. And this answer must be also sorted by depth in O(m log m).

You an try to go with a one dimensional R-tree. Allowing you to define regions on the go. Within such a structure each node spans a region from min to max. You can now split this region further. Since there are intervals fitting in both sections since the split is actually splitting it, those are stored within the node (and not within the child nodes). Within those child nodes you get again such a list and so on.

For your search you inspect all nodes and child nodes which regions intersect with your search interval.

Within each node the list of intervals are sorted according their depth values.

So the problem is reduced to a number of sorted lists (of all intervalls that are likely to be contained within your search interval). Those lists must now be filtered for every interval that is truely intersecting with your search interval. But you do not need to filter all. Since if such a node interval is totally contained within your search interval all its intervals and all its children intervals are truely intersecting with your search interval (since they are totally contained within).

To combine all those lists you just use union combination where you select the next element of that union which has the smallest depth. You sort all those lists by the depth of its first element (the element with the smallest depth in each list). Now you look for the first element and move it to the result. You compare now the next element within the list with the first element of the next list and if the depth is still smaller you copy it to. If the depth becomes bigger you just sort it with the correct position taking log k (where k is the number of non-empty lists in your collection) and go on with the now first list and repeat it until all lists are empty or work through since you maintain cursor positions for each list.

This way you only sort the lists and compare it with the next element if it is still smaller or insert it.

This is the best structure I can think about. first you easily rule out almost all intervalls that can not intersect with it. Than you compose the result based on the lists of potentials where you have lists that you know are part of the result in full (one can argue that only a certain number of intervall lists must be checked since trees split very fast). By controlling the split strategy you control the cost of each part. If you for example only split on >10 intervals you will ensure k

The worst case is bad but I guess the expected actual performance will be good and way better as O(n + m log m) since you use already sorted distinct lists of potential intersections.

And remember if a node has child elements it itself contains a list of all intervals that intersect with the split point. Therefore if your search intervall also intersects with the split point every interval of this node is also part of your result.

So feel free to experiment with this structure. It should be easy to implement within a single day.