Abstract-Shortest sökväg i transportnät är utan tvekan en av de viktigaste online söktjänster idag (t.ex. Google Maps, MapQuest, etc), med tillämpningar som spänner över logistik, rumslig optimering, eller dagliga körbeslut. Ofta tillhandahåller ägaren av vägnätet data (t.ex. en transportmyndighet) sin databas till tredje part frågetjänster, som är ansvariga för att svara kortaste sökväg frågor som deras kunder. Frågan som uppstår här är att en frågetjänst kan vara att returnera sub-optimala vägar antingen avsiktligt (för att tjäna sina egna syften som beräkningsbesparingar eller kommersiella skäl) eller eftersom det har äventyrats av Internet angripare som förfalskar resultaten. För att ovanstående tillämpningar ska lyckas är det därför viktigt att varje rapporterad sökväg åtföljs av ett bevis som gör det möjligt för kunderna att kontrollera att sökvägen är korrekt. Detta är den första studien om kortaste vägverifiering i outsourcade nätverksdatabaser. Vi föreslår begreppet autentiserade tips, som används för att minska storleken på bevisen. Vi utvecklar flera autentiseringstekniker och kvantifierar deras kompromisser med avseende på byggkostnader och bevisstorlek offline. Experiment på verkliga vägnät visar att våra lösningar verkligen är effektiva och leder till kompakta frågebevis.
Yiu m.fl. REF föreslår behörighetskontroll av kortaste sökvägar på vägnät.
Efficient verification of shortest path search via authenticated hints
{'venue': '2010 IEEE 26th International Conference on Data Engineering (ICDE 2010)', 'journal': '2010 IEEE 26th International Conference on Data Engineering (ICDE 2010)', 'mag_field_of_study': ['Computer Science']}