Räckviddssökning

Enkel sökning av intervall.

Inom datavetenskap består räckviddssökningsproblemet i att bearbeta en uppsättning S av objekt, för att avgöra vilka objekt från S som skär ett frågeobjekt, kallat intervallet . Till exempel, om S är en uppsättning punkter som motsvarar koordinaterna för flera städer, hitta delmängden av städer inom ett givet intervall av latituder och longituder .

Avståndssökningsproblemet och datastrukturerna som löser det är ett grundläggande ämne för beräkningsgeometri . Tillämpningar av problemet uppstår inom områden som geografiska informationssystem (GIS), datorstödd design (CAD) och databaser .

Variationer

Det finns flera varianter av problemet, och olika datastrukturer kan vara nödvändiga för olika variationer. För att få en effektiv lösning måste flera aspekter av problemet specificeras:

Objekttyper: Algoritmer beror på om S består av punkter , linjer , linjesegment , rutor , polygoner .... De enklaste och mest studerade objekten att söka i är punkter.
Områdestyper: Frågeintervallen måste också dras från en förutbestämd uppsättning. Några väl studerade uppsättningar av intervall, och namnen på respektive problem är axeljusterade rektanglar (ortogonal intervallsökning), simpliceringar , halvrum och sfärer / cirklar .
Frågetyper: Om listan över alla objekt som skär frågeintervallet måste rapporteras kallas problemet för intervallrapportering och frågan kallas en rapportfråga . Ibland krävs bara antalet objekt som skär området. I det här fallet kallas problemet för intervallräkning , och frågan kallas en räknefråga . Tomhetsfrågan rapporterar om det finns minst ett objekt som skär området . I semigruppversionen anges en kommutativ semigrupp ( S ,+), varje punkt tilldelas en vikt från S och det krävs att semigruppsumman av vikterna för de punkter som skär intervallet redovisas.
Dynamisk räckviddssökning vs. statisk räckviddssökning: I den statiska inställningen är uppsättningen S känd i förväg. I dynamiska inställningar kan objekt infogas eller raderas mellan frågor.
Offline intervallsökning: Både uppsättningen objekt och hela uppsättningen av frågor är kända i förväg.

Data struktur

Ortogonal räckviddssökning

En 2D ortogonal intervallfråga. I det här fallet skulle en intervallrapporteringsfråga returnera de två inringade punkterna, en intervallräkningsfråga skulle returnera 2 och en tomhetsfråga skulle returnera falskt.

Vid ortogonal intervallsökning består mängden S av $n$ punkter i $d$ dimensioner, och frågan består av intervall i var och en av dessa dimensioner. Frågan består alltså av en flerdimensionell axeljusterad rektangel . Med en utdatastorlek på $k$ använde Jon Bentley ett kd-träd för att uppnå (i Big O-notation ) O $\displaystyle O(n)}$ mellanslag och $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ frågetid. Bentley föreslog också att använda intervallträd , vilket förbättrade frågetiden till $O(\log ^{d}n+k)$ men ökade utrymmet till $O(n\log ^{d-1}n)$ . Dan Willard använde downpointers, ett specialfall av fraktionerad kaskad för att minska frågetiden ytterligare till $O(\log ^{d-1}n+k)$ .

Medan ovanstående resultat uppnåddes i pekarmaskinsmodellen , har ytterligare förbättringar gjorts i ordet RAM -modell för beräkning i låga dimensioner (2D, 3D, 4D). Bernard Chazelle använde compress range trees för att uppnå $O(\log n)$ frågetid och $O(n)$ utrymme för räckviddsräkning. Joseph JaJa och andra förbättrade senare denna frågetid till $O\left({\dfrac {\log n}{\log \log n}}\right)$ för intervall räkning, som matchar en nedre gräns och därmed är asymptotiskt optimal .

Från och med 2015 är de bästa resultaten (i låga dimensioner (2D, 3D, 4D)) för avståndsrapportering som hittats av Timothy M. Chan , Kasper Larsen och Mihai Pătrașcu , som också använder komprimerade avståndsträd i ordet RAM-beräkningsmodell. en av följande:

$O(n)$ mellanslag, $O(\log ^{\epsilon }n+k\log ^{\epsilon }n )$ frågetid
$O(n\log \log n)$ mellanslag, $O(\log \log n+ k\log \log n)$ frågetid
$O(n\log ^{\epsilon }n)$ mellanslag, $O(\log \log n+k)$ frågetid

I det ortogonala fallet, om en av gränserna är oändlig kallas frågan tresidig. Om två av gränserna är oändliga är frågan dubbelsidig, och om ingen av gränserna är oändliga är frågan fyrsidig.

Dynamisk räckviddssökning

Medan i statisk områdessökning är uppsättningen S känd i förväg, dynamisk områdessökning, infogning och radering av punkter tillåts. I den inkrementella versionen av problemet är endast infogning tillåtna, medan den dekrementella versionen endast tillåter raderingar. För det ortogonala fallet Kurt Mehlhorn och Stefan Näher en datastruktur för sökning av dynamiskt omfång som använder dynamisk fraktionerad kaskad för att uppnå $O(n\log n)$ mellanslag och $O(\log n\log \log n+k)$ frågetid. Både inkrementella och dekrementella versioner av problemet kan lösas med $O(\log n+k)$ frågetid, men det är okänt om allmän dynamisk intervallsökning kan göras med den frågan tid.

Färgat område sökning

Problemet med färgomfångsräkning tar hänsyn till fallet där punkter har kategoriska attribut. Om kategorierna betraktas som färger av punkter i geometriskt utrymme, är en fråga för hur många färger som förekommer i ett visst område. Prosenjit Gupta och andra beskrev en datastruktur 1995 som löste 2D ortogonal färgområdesräkning i $O(n^{2}\log ^{2}n)$ mellanslag och $O(\log ^{2}n)$ frågetid.

Ansökningar

Förutom att beaktas i beräkningsgeometri , intervallsökning och ortogonal intervallsökning i synnerhet, har applikationer för räckviddsfrågor i databaser . Färgad intervallsökning används också för och motiveras genom att söka igenom kategoriska data. Att bestämma raderna i en databas med bankkonton som representerar personer vars ålder är mellan 25 och 40 och som har mellan 10 000 och 20 000 USD kan till exempel vara ett ortogonalt rapporteringsproblem där ålder och pengar är två dimensioner.

Se även

Vidare läsning

de Berg, Mark; van Kreveld, Marc; Overmars, Mark ; Schwarzkopf, Otfried (2000), Computational Geometry (2:a upplagan), Berlin: Springer-Verlag, ISBN 3-540-65620-0
Matoušek, Jiří (1994), "Geometric range searching" , ACM Computing Surveys , 26 (4): 421–461, doi : 10.1145/197405.197408 , S2CID 17729301 .