¿Cómo encontrar 1 o más intervalos de tiempo parcialmente interseccionados en una lista de pocos millones?

Question

Necesito una idea para un algoritmo de búsqueda/índice eficiente y/o estructura de datos para determinar si un intervalo de tiempo se superpone a cero o más intervalos de tiempo en una lista, teniendo en cuenta que una superposición completa es un caso especial de superposición parcial. Hasta ahora no he encontrado nada rápido ni elegante ...

Considere una colección de intervalos con cada intervalo que tiene 2 fechas: inicio y fin.

Los intervalos pueden ser grandes o pequeños, pueden superponerse entre sí parcialmente o no se pueden abrir. En la notación de Java, algo como esto:

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 

El objetivo es encontrar de manera eficiente todos los intervalos que se cortan parcialmente un intervalo de entrada recién llegado. Para c como un ArrayList esto podría parecerse a ...

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; 
} 

Iterar a través de la lista entera requiere linealmente demasiados compara a cumplir mis objetivos de rendimiento. En lugar de ArrayList, se necesita algo mejor para dirigir la búsqueda y minimizar el número de comparaciones.

Mi mejor solución hasta el momento implica mantener dos listas ordenadas internamente y realizar 4 búsquedas binarias y alguna iteración de lista para cada solicitud. Alguna mejor idea?

---

Nota del editor: intervalos de tiempo son un caso específico que emplea segmentos lineales a lo largo de un solo eje, son los que la X, o en este caso, T (por tiempo).

Answer 1

Interval trees hará:

En computer science, un árbol de intervalo es una tree data structure para mantener intervals. Específicamente, le permite a uno encontrar eficientemente todos los intervalos que se superponen con cualquier intervalo o punto dado. A menudo se utiliza para consultas en ventanas, por ejemplo, para encontrar todas las carreteras en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el segment tree ...

Answer 2

parece que el artículo Wiki resuelve más de lo que pidió. ¿Estás atado a Java?

Tiene una "gran colección de objetos" que me dice "Base de datos" Ha preguntado sobre "capacidades de indexación de período incorporadas" y la indexación me dice la base de datos. Sólo

puede decidir si este SQL cumple su percepción de "elegante":

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 

Si el Inicio y columnas finales están indexados, una base de datos relacional (de acuerdo a la publicidad) será muy eficiente en esto.