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:

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

Descrizione formale del problema Sia un insieme di punti nello spazio euclideo . Data una famiglia di sottoinsiemi di (chiamata spazio delle query), una query di ricerca per intervallo riceve in input un elemento e deve calcolare:

Reporting: Counting:

Le forme più comuni per la query sono:

Ortogonale (orthogonal range searching): è un box / iperrettangolo allineato agli assi, definito come . Simmetrica / Sferica: è una sfera euclidea definita da un centro e un raggio. Semispazio (halfspace range searching): è un semispazio delimitato da un iperpiano.

Strutture dati principali (caso ortogonale) Per superare l'approccio ingenuo di complessità lineare 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: Tempo di costruzione: Tempo di query (in 2D): per il reporting, dove è 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 -dimensionale è composto da un albero binario bilanciato sulla prima coordinata, in cui ogni nodo interno punta a un range tree -dimensionale sui punti del suo sottoalbero.

Spazio: Tempo di query: Nota (ottimizzazione): utilizzando una tecnica nota come frazionamento a cascata (fractional cascading) è possibile ridurre il tempo di query in dimensioni a .

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 (): Struttura DatiSpazio di MemoriaTempo di Query (Reporting)K-d TreeRange Tree standardRange Tree con Fractional Cascading

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

Basi di dati spaziali e GIS: Interrogazioni geografiche (es. "Trova tutti i ristoranti nel raggio di 5 km" o "Trova le proprietà all'interno di questo perimetro rettangolare"). Computer Grafica: rimozione (culling) dettagli non visibili) e algoritmi di collisione spaziale. Information Retrieval: Ricerca multi-attributo (es. "Trova gli utenti con Età tra 20 e 30 anni E Reddito tra 30.000€ e 50.000€").

Note

Categoria:Algoritmi di ricerca Categoria:Database management system