Räckviddsrapportering

I beräkningsgeometri och databasteori frågar en intervallrapporteringsfråga om en lista över de punkter som matchar frågan. Frågan specificeras ofta av en geometrisk form, som innehåller alla punkter som ska matcha, och kallas ett intervall. Räckviddsrapportering är ett specialfall av intervallsökning , där frågor kan returnera andra typer av samlad information om punkter i ett intervall.

Frågor om intervallrapportering hanteras ofta genom att bygga en datastruktur från en samling punkter som kan svara på frågor effektivt. Eftersom den värsta utdatastorleken för en intervallrapporteringsfråga, mätt som en funktion av datamängdsstorleken n , kan vara sig själv, har mycket av forskningen om intervallrapporteringsdatastrukturer undersökt utdatakänsliga algoritmer , där frågetiden analyseras i termer av både n och antalet rapporterade punkter (ofta betecknad k ).

Till exempel, för endimensionell (numerisk) data med frågeintervall som är intervall , kan intervallrapporteringsfrågor hanteras genom att lagra data i en sorterad array. Med den här strukturen kan man använda binär sökning för att hitta punkten närmast början av ett frågeintervall, och sedan skanna arrayen från den punkten och framåt för att lista alla punkter i intervallet. Lagring av denna datastruktur använder O ( n ) (linjärt) utrymme, och det hanterar frågor i tid O (log n + k ) per fråga.

• Agarwal, PK ; Erickson, J. (1999), "Geometric Range Searching and Its Relatives" (PDF) , i Chazelle, Bernard ; Goodman, Jacob ; Pollack, Richard (red.), Advances in Discrete and Computational Geometry: Proces of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry—Ten Years Later, 14-18 juli 1996, Mount Holyoke College, Contemporary Matematik, vol. 223, American Mathematical Society Press, s. 1–56 .