Detta dokument tar upp problemet med att övervaka de närmaste grannarna till en dynamisk förändring av vägnätet. Med tanke på en destination där en användare kommer att, denna nya fråga returnerar k - NN med avseende på den kortaste vägen som ansluter destinationen och användarens nuvarande plats, och därmed ger en lista över närmaste kandidater för referens genom att överväga hela den kommande resan. Vi namnger denna fråga k - Path Nearest Neighbor fråga (k - PNN). Eftersom användaren rör sig och kanske inte alltid följer den kortaste vägen, ändras sökvägen hela tiden. Utmaningen med att övervaka k-PNn för en godtyckligt rörlig användare är att dynamiskt bestämma uppdateringsplatserna och sedan uppdatera k-PN effektivt. Vi föreslår en tre-fas Bästa-första nätverksexpansion (BNE) algoritm för övervakning av k -PN och motsvarande kortaste vägen. I sökfasen hittar BNE den kortaste vägen till destinationen, under vilken en kandidat som garanterar att inkludera k - PNN genereras samtidigt. Sedan i verifieringsfasen, en heuristisk algoritm körs för att undersöka kandidaternas exakta avstånd till sökvägen, och det uppnår betydande minskning av antalet besökta noder. Övervakningsfasen handlar både om datoruppdateringsplatser och om att fräscha upp k-PNN i olika användarrörelser. Eftersom fastställandet av nätverksavståndet är en kostsam process, underhålls ett expansionsträd och kandidatuppsättningen noggrant av BNE-algoritmen, som kan ge effektiv uppdatering på den kortaste vägen och k-PN-resultaten. Slutligen utför vi omfattande experiment på verkliga vägnät och visar att våra metoder uppnår tillfredsställande prestanda.
Med tanke på en destination där en användare kommer att, denna nya fråga returnerar k-NN med avseende på den kortaste vägen som ansluter destinationen och användarens nuvarande plats REF.
Monitoring path nearest neighbor in road networks
{'venue': 'SIGMOD Conference', 'journal': None, 'mag_field_of_study': ['Computer Science']}