Databases
StackOverflow2013
Postsdbo
POAlgorithm to produce a difference of two collections of intervals
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm to produce a difference of two collections of intervals
    primarykey
    data
    text
    <h2>Problem</h2> <p>Suppose I have two collections of intervals, named A and B. How would I find a difference (a relative complement) in a most time- and memory-efficient way?</p> <p>Picture for illustration: <img src="https://i.stack.imgur.com/fj7bb.png" alt="enter image description here"></p> <p>Interval endpoints are <strong>integers</strong> ( ≤ 2<sup>128</sup>-1 ) and they are always both 2<sup>n</sup> long and aligned on the m×2<sup>n</sup> lattice (so you can make a binary tree out of them).</p> <p>Intervals can overlap in the input but this does not affect the output (the result if flattened would be the same).</p> <p>The problem is because there are MANY intervals in both collections (up to 100,000,000), so naïve implementations will probably be slow.</p> <p>The input is read from two files and it is sorted in such a way that smaller sub-intervals (if overlapping) come immediately after their parents in order of size. For example:</p> <pre><code>[0,7] [0,3] [4,7] [4,5] [8,15] ... </code></pre> <h2>What have I tried?</h2> <p>So far, I've been working on a implementation that generates a binary search tree while doing so aggregates neighbouring intervals ( <code>[0,3],[4,7] =&gt; [0,7]</code> ) from both collections, then traverses the second tree and "bumps out" the intervals that are present in both (subdividing the larger intervals in the first tree if necessary).</p> <p>While this appears to be working for small collections, it requires more and more RAM to hold the tree itself, not to mention the time it needs to complete the insertion and removal from the tree.</p> <p>I figured that since intervals come pre-sorted, I could use some dynamic algorithm and finish in one pass. I am not sure if this is possible, however.</p> <hr> <p>So, how would I go about solving this problem in a efficient way?</p> <p><strong>Disclaimer:</strong> This is not a homework but a modification/generalization of an actual real-life problem I am facing. I am programming in C++ but I can accept an algorithm in any [imperative] language.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTibor
    1. USTibor
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm to produce a difference of two collections of intervals
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAlgorithm to produce a difference of two collections of intervals
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POAlgorithm to produce a difference of two collections of intervals
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHow'bout a simple linear one-pass search? Seems to need less memory, especially if you store only one pair of intervals at a time.
      singulars
      1. POAlgorithm to produce a difference of two collections of intervals
      1. This table or related slice is empty.
    2. CO+1, @H2CO3. I feel like this problem is somewhat similar to [finding the intersection of two sorted arrays](http://stackoverflow.com/a/2400236/953482), so the linear search could possibly be applied here.
      singulars
      1. POAlgorithm to produce a difference of two collections of intervals
      1. USKevin
    3. CO@Kevin yes, basically I'm just thinking KISS and a b-tree seems a bit of an overhead.
      singulars
      1. POAlgorithm to produce a difference of two collections of intervals
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload