omfångsökning

Omfångsökning, eller range search, är ett vanligt problem inom datavetenskap där man söker bland en uppsättning objekt med tillhöriga värden eller koordinater och hämtar alla objekt vars attribut ligger inom ett specificerat intervall eller en hyperrektangel. En enkel metod är att skanna igenom alla objekt och filtrera de som uppfyller villkoren, men detta blir ineffektivt när mängden data är stor.

Effektiva metoder använder indexstrukturer för att minska antalet objekt som behöver kontrolleras. I en-dimensionella fall kan balanserade sökträd eller B-träd användas för att snabbt hitta gränserna och samla träffarna. I två eller fler dimensioner används datastrukturer som kd-träd, range-träd och R-träd, vilka organiserar data spatialt och möjliggör snabb återgivning av alla objekt inom ett givet område. I vissa fall används även approximerade metoder eller speciella indexstrukturer i databaser (t exempel GiST- eller R-tree-baserade index) för att hantera större eller mer komplexa dataset. Teoretiskt kan sämsta fallet bli O(n) i olämpliga eller mycket dåligt fördelade data, medan praktiska implementationer ofta uppnår nära logaritmisk tid för att hitta gränser och proportionalt tid för att returnera träffarna.

Användningsområden inkluderar geografiska informationssystem, databassökningar med tids- eller rumsliga intervall, grafiska applikationer och datavetenskapliga analyser där det är viktigt att snabbt isolera objekt inom ett visst område.

Se även: range query, närhets- och multidemensional sökning, spatiala databaser.