Ricerca per intervallo

La ricerca per intervalli (in inglese range searching) è uno dei problemi geometrici fondamentali della geometria computazionale e delle basi di dati. Data una collezione di oggetti (solitamente punti nello spazio d-dimensionale) e una regione di query (l'intervallo), l'obiettivo è identificare o contare in modo efficiente gli oggetti che si trovano all'interno della regione.

Si distinguono principalmente in due varianti del problema:

  1. Range Reporting Query: elencare tutti i punti che cadono all'interno dell'intervallo.
  2. Range Counting Query: restituire solo il numero totale di punti nell'intervallo.

Descrizione formale del problema

Sia P={p1,p2,…,pn} un insieme di n punti nello spazio euclideo ℝd. Data una famiglia di sottoinsiemi 𝒬 di ℝd (chiamata spazio delle query), una query di ricerca per intervallo riceve in input un elemento Q∈𝒬 e deve calcolare:

Le forme più comuni per la query Q sono:

Strutture dati principali (caso ortogonale)

Per superare l'approccio ingenuo di complessità lineare O(n) ottenuto scansionando l'intero set di dati, si pre-elaborano i punti costruendo strutture dati specifiche.

k-d tree (alberi k-dimensionali)

Il k-d tree è un albero binario di ricerca in cui ogni nodo non foglia divide lo spazio in due semispazi rispetto a una delle coordinate, alternando ciclicamente le dimensioni ad ogni livello.

  • Spazio: O(n)
  • Tempo di costruzione: O(nlog⁡n)
  • Tempo di query (in 2D): O(n+k) per il reporting, dove k è il numero di punti riportati.

Range tree (Alberi a intervalli)

Il Range Tree è una struttura dati multilivello orientata ad ottenere tempi di query polilogaritmici, a scapito di una maggiore occupazione di memoria. Un range tree d-dimensionale è composto da un albero binario bilanciato sulla prima coordinata, in cui ogni nodo interno punta a un range tree (d−1)-dimensionale sui punti del suo sottoalbero.

  • Spazio: O(nlogd−1n)
  • Tempo di query: O(logdn+k)
    Nota (ottimizzazione): utilizzando una tecnica nota come frazionamento a cascata (fractional cascading) è possibile ridurre il tempo di query in d dimensioni a O(logd−1n+k).

Compromesso fra spazio e tempo

Nella geometria computazionale esiste un bilanciamento intrinseco tra la quantità di memoria utilizzata (spazio di memorizzazione) e la velocità di risposta alla query. La tabella seguente riassume le prestazioni nel caso bidimensionale (d=2):

Struttura Dati Spazio di Memoria Tempo di Query (Reporting)
K-d Tree O(n) O(n+k)
Range Tree standard O(nlog⁡n) O(log2n+k)
Range Tree con Fractional Cascading O(nlog⁡n) O(log⁡n+k)

Applicazioni

Le tecniche di range searching trovano applicazione in molteplici ambiti dell'informatica: