Med den ökande tillgången på terrängdata, t.ex. från flyglaserskanning, drar hanteringen av sådana data till sig allt större uppmärksamhet både inom industrin och den akademiska världen. I synnerhet, rumsliga frågor, t.ex., k-nearest granne och omvända närmaste granne frågor, i Euclidean och rumsliga nätverksutrymmen utvidgas till terränger. Sådana frågor alla förlitar sig på en viktig operation, att hitta kortaste ytavstånd. Kortaste ytavståndsberäkning är dock mycket tidskrävande. Vi föreslår tekniker som möjliggör effektiv beräkning av lägre och övre gränser för den kortaste ytsträckan, vilket möjliggör snabbare frågebehandling genom att eliminera dyra avståndsberäkningar. Empiriska studier visar att våra gränser är mycket snävare än de mest kända gränserna i många fall och att de möjliggör upphastigheter på upp till 43 gånger för några välkända rumsliga frågor.
Algoritmen beräknar tätare nedre och övre gränser för det geodesiska avståndet än de i REF, som inte beror på den underliggande terrängen.
Finding Shortest Paths on Terrains by Killing Two Birds with One Stone
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}