ABSTRACT Kortaste sökvägen frågor har använts i stor utsträckning i platsbaserade tjänster (LBS). För att beräkna den kortaste vägen från ett ursprung till en destination behöver en LBS-leverantör vanligtvis känna till kartuppgifterna för det underliggande vägnätet, vilket kan vara ganska kostsamt, särskilt om sådana uppgifter behöver hållas kontinuerligt och uppdaterat. Ett kostnadseffektivt sätt är att LBS-leverantörer lägger ut den kortaste sökvägen på molnbaserade karttjänster som Google Maps, genom att hämta detaljerad sökvägsinformation från dem genom externa förfrågningar. På grund av den höga kostnaden för att få tillgång till data genom externa förfrågningar och användningsgränser för karttjänster, föreslår vi två optimeringstekniker i detta dokument, nämligen Path sharing och path caching, för att minska antalet externa förfrågningar och användarens svarstid. Till skillnad från tidigare arbete där det underliggande vägnätet ges, optimerar detta papper sökvägen behandling endast baserat på frågekällor och destinationer. Den grundläggande idén med att dela sökväg optimering är att sökväg information av en fråga kan delas med en annan fråga q om q värden ursprung och destination båda ligger på sökvägen. För att uppnå detta föreslår vi en effektiv metod för att beräkna om en frågeorigin/destination ligger på en väg som endast baseras på det euklideiska avståndet mellan dem. Sökväg caching, en förlängning av sökväg delning, låter en LBS leverantör svara sökväg frågor direkt baserat på cachesökvägar. För att uppnå detta formulerar vi först problemet med att bygga sökväg cache som en knapsack problem och utforma en girig algoritm för att lösa det; sedan, vi utformar en effektiv cache struktur för att stödja effektiv cache uppslagning. Omfattande experiment på Bing Maps och verkliga datamängder utförs, och resultaten visar effektiviteten, skalbarheten och tillämpligheten av våra föreslagna tillvägagångssätt. INDEX TERMS Kortaste sökvägar, platsbaserade tjänster, karttjänster, molntjänster, delning av sökvägar, sökvägar.
Zhang m.fl. REF insåg sökningen av den kortaste sökvägen genom molnbaserade karttjänster med delning av sökvägar och cachelagring av sökvägar, utan att känna till den underliggande grafstrukturen eller nätverkstopologin, även om endast de raka linjerna för delning av sökvägar beaktas.
Efficient Path Query Processing Through Cloud-Based Mapping Services
{'venue': 'IEEE Access', 'journal': 'IEEE Access', 'mag_field_of_study': ['Computer Science']}