Ricerca per intervallo

La ricerca per intervalli (in inglese range searching) è uno dei problemi geometrici fondamentali della geometria computazionale e delle basi di dati.^[1] 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.^[2]^[3]

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 $P=\{p_{1},p_{2},\ldots ,p_{n}\}$ un insieme di $n$ punti nello spazio euclideo $\mathbb {R} ^{d}$ . Data una famiglia di sottoinsiemi ${\mathcal {Q}}$ di $\mathbb {R} ^{d}$ (chiamata spazio delle query), una query di ricerca per intervallo riceve in input un elemento $Q\in {\mathcal {Q}}$ e deve calcolare:

Reporting: $P\cap Q$
Counting: $|P\cap Q|$

Le forme più comuni per la query $Q$ sono:

Ortogonale (orthogonal range searching): $Q$ è un box / iperrettangolo allineato agli assi, definito come $[x_{1},x'_{1}]\times [x_{2},x'_{2}]\times \cdots \times [x_{d},x'_{d}]$ .
Simmetrica / Sferica: $Q$ è una sfera euclidea definita da un centro e un raggio.
Semispazio (halfspace range searching): $Q$ è un semispazio delimitato da un iperpiano.

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.^[4]

Spazio: $O(n)$
Tempo di costruzione: $O(n\log n)$
Tempo di query (in 2D): $O({\sqrt {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.^[5] 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(n\log ^{d-1}n)$
Tempo di query: $O(\log ^{d}n+k)$
Nota (ottimizzazione): utilizzando una tecnica nota come frazionamento a cascata (fractional cascading) è possibile ridurre il tempo di query in $d$ dimensioni a $O(\log ^{d-1}n+k)$ ^[1].

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({\sqrt {n}}+k)$
Range Tree standard	$O(n\log n)$	$O(\log ^{2}n+k)$
Range Tree con Fractional Cascading	$O(n\log n)$	$O(\log n+k)$

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

1 2 (EN) Mark de Berg, Otfried Cheong e Marc van Kreveld, Computational Geometry: Algorithms and Applications, Springer Berlin Heidelberg, 2008, DOI:10.1007/978-3-540-77974-2, ISBN 978-3-540-77973-5.
↑ (EN) Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, in Journal of the ACM, vol. 37, n. 2, 1990-04, pp. 200–212, DOI:10.1145/77600.77614.
↑ (EN) Pankaj K. Agarwal, Range Searching, in Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman (a cura di), Handbook of Discrete and Computational Geometry, Third Edition, Chapman and Hall/CRC, 2017, DOI:10.1201/9781315119601, ISBN 978-1-315-11960-1.
↑ (EN) Jon Louis Bentley, Multidimensional binary search trees used for associative searching, in Communications of the ACM, vol. 18, n. 9, 1975-09, pp. 509–517, DOI:10.1145/361002.361007.
↑ George S. Lueker, A data structure for orthogonal range queries, IEEE, 1978-10, pp. 28–34, DOI:10.1109/SFCS.1978.1.

[:0-1] 1 2 (EN) Mark de Berg, Otfried Cheong e Marc van Kreveld, Computational Geometry: Algorithms and Applications, Springer Berlin Heidelberg, 2008, DOI:10.1007/978-3-540-77974-2, ISBN 978-3-540-77973-5.

[2] (EN) Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, in Journal of the ACM, vol. 37, n. 2, 1990-04, pp. 200–212, DOI:10.1145/77600.77614.

[3] (EN) Pankaj K. Agarwal, Range Searching, in Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman (a cura di), Handbook of Discrete and Computational Geometry, Third Edition, Chapman and Hall/CRC, 2017, DOI:10.1201/9781315119601, ISBN 978-1-315-11960-1.

[4] (EN) Jon Louis Bentley, Multidimensional binary search trees used for associative searching, in Communications of the ACM, vol. 18, n. 9, 1975-09, pp. 509–517, DOI:10.1145/361002.361007.

[5] George S. Lueker, A data structure for orthogonal range queries, IEEE, 1978-10, pp. 28–34, DOI:10.1109/SFCS.1978.1.

[1]

[2]

[3]

[4]

[5]