En vanlig typ av fråga i rumsliga nätverk (t.ex. vägnätverk) är att hitta K närmaste grannar (KN) för ett givet frågeobjekt. Med dessa nätverk beror avstånden mellan objekten på deras nätverksanslutning och det är beräknings dyrt att beräkna avstånden (t.ex. kortaste vägar) mellan objekt. I detta dokument föreslår vi ett nytt tillvägagångssätt för att effektivt och korrekt utvärdera KNN-frågor i rumsliga nätverksdatabaser med hjälp av första ordningens Voronoi-diagram. Detta tillvägagångssätt bygger på att dela upp ett stort nätverk till små Voronoi-regioner och sedan förhandsberäkna avstånd både inom och över regionerna. Genom att lokalisera precomputationen inom regionerna sparar vi både på lagring och beräkning och genom att utföra beräkning över hela nätverket endast för gränspunkterna i de angränsande regionerna, undviker vi global pre-computation mellan varje node-par. Våra empiriska experiment med flera verkliga datauppsättningar visar att vår föreslagna lösning överträffar metoder som bygger på on-line avståndsberäkning med upp till en storleksordning, och ger en faktor av fyra förbättring av selektiviteten av filtersteget jämfört med indexbaserade metoder.
Kolahdouzan och Shahabi REF föreslog: "en ny metod för att utvärdera K-Nearest Neighbor (kNN) frågor i rumsliga nätverksdatabaser med hjälp av första ordningens Voronoi diagram baserat på partitionering av ett stort nätverk till små Voronoi regioner, och sedan pre-computing avstånd både inom och över regionerna".
Voronoi-based k nearest neighbor search for spatial network databases
{'venue': 'In VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}