En algoritm presenteras för att hitta de k närmaste grannarna i ett rumsligt nätverk på bästa första sätt med hjälp av nätverksavstånd. Algoritmen är baserad på precomputing de kortaste banor mellan alla möjliga hörn i nätverket och sedan göra användning av en kodning som drar nytta av det faktum att de kortaste banor från vertex u till alla återstående hörn kan dekomponeras i undergrupper baserat på de första kanterna på de kortaste banor till dem från u. Därför, i värsta fall, mängden arbete beror på antalet objekt som undersöks och antalet länkar på de kortaste vägar till dem från q, snarare än beroende på antalet hörn i nätverket. Mängden lagring som krävs för att hålla reda på undergrupper minskas genom att dra nytta av deras rumsliga samstämmighet som fångas med hjälp av en kortaste väg quadtree. I synnerhet har experiment på ett antal stora vägnät samt en teoretisk analys visat att lagringen har minskat från O(N 3 ) till O(N 1.5 ) (dvs. med en storleksordning som motsvarar kvadratroten). Förutsättningen av de kortaste vägarna längs nätverket frikopplar i huvudsak processen för att beräkna kortaste vägar längs nätverket från att hitta grannarna, och därmed också frikoppla domänen S av frågeobjekten och det av de objekt från vilka grannarna är hämtade från domänen V av hörnen i det rumsliga nätverket. Detta innebär att så länge det rumsliga nätverket är oförändrat kan algoritmen och den underliggande representationen av de kortaste sökvägarna i det rumsliga nätverket användas med olika uppsättningar objekt.
Samet m.fl. REF bygga en kortaste vägen fyrkantiga träd för att stödja k-neerest granne frågor i rumsliga nätverk.
Scalable network distance browsing in spatial databases
{'venue': 'SIGMOD Conference', 'journal': None, 'mag_field_of_study': ['Computer Science']}