Vi föreslår en ny märkningsmetod för kortaste väg- och distansfrågor på vägnät. Vi presenterar ett nytt ramverk (dvs. Datastruktur och frågealgoritm) som kallas motorvägsbaserade märkningar och en förbehandlingsalgoritm för den namngivna beskurna motorvägsmärkning. Vår föreslagna metod har flera tilltalande drag från olika aspekter i litteraturen. Faktum är att vi drar nytta av den teoretiska analysen av det seminala resultatet av Thorup för distansorakler, mer detaljerade strukturer av verkliga vägnät, och den beskurna märkningsalgoritm som genomför beskärning Dijkstra algoritm. De experimentella resultaten visar att den föreslagna metoden är jämförbar med den tidigare toppmoderna märkningsmetoden i både frågetid och datastorlek, medan vår viktigaste förbättring är att förbehandlingstiden är mycket snabbare. och fortsätter [11, 4, 9, 10, 5, 6, 1, 2, 7]. En av de mest anmärkningsvärda händelserna på senare tid är uppkomsten av praktiska märkningsmetoder [1, 2]. Märkningsmetoder prekompilera etikett L(v) för varje vertex v och svarsavstånd mellan två punkter s och t med etiketterna L(s) och L(t) utan att titta på inmatningskurvan. Dessa praktiska metoder använder sig av de mest standardiserade märkningsramarna (dvs. datastruktur och frågealgoritm) som kallas navbaserade märkningar [1]. Etiketten L(v) är en uppsättning par (u, δ uv ), där u är en vertex och δ uv är avståndet mellan v och u. Eftersom märkningsmetoden kan svara på avstånd genom att endast titta på två på varandra följande segment av förhandsberäknade data, är deras frågetid känd för att vara den snabbaste bland alla andra föreslagna metoder. I detta dokument ska vi förbättra den toppmoderna algoritmen (dvs. märkningsmetoden) på flera sätt. I synnerhet presenterar vi en ny ram för märkning som kallas den motorvägsbaserade ramen för märkning och en förbehandlingsalgoritm för den ram som kallas beskurna motorvägsmärkning. Vår föreslagna metod har flera tilltalande drag från olika aspekter i litteraturen. Avståndsorakler. Tanken bakom vår strategi har en viss likhet med Thorups avstånd orakle för plana grafer [12]. Specifikt, vår strategi upprepade gånger separerar inmatningsgrafer genom kortaste vägar, och sedan lagrar avstånd från hörn till de kortaste vägar. Dessa är också nycklar i Thorups tidning. Vi kan faktiskt anpassa Thorups bevis för att i viss utsträckning motivera riktigheten och effektiviteten i vår föreslagna algoritm. Vägar. Flera tidigare metoder utnyttjar motorvägsstruktur i vägnät. Vägar är användbara eftersom de är centrala, i den meningen att många kortaste vägar måste passera genom motorvägar. Den navbaserade märkningsalgoritmen utnyttjar dock inte direkt motorvägar. Å andra sidan drar vårt tillvägagångssätt större nytta av dessa motorvägar. Präglad etikettering. Begreppet bestruken märkning [3] är den viktigaste ingrediensen i de senaste toppmoderna beräkningsalgoritmerna för distansfrågor på komplexa nätverk [3] och tillgänglighetsfrågorna på DEG [13].
Den beskurna vägmärkningsmetod som föreslagits av Akiba et al. REF bryter ner vägnätet i separata stigar och märkningen av en nod inkluderar avståndet till vissa noder av stigar.
Fast shortest-path distance queries on road networks by pruned highway labeling
{'venue': 'ALENEX', 'journal': None, 'mag_field_of_study': ['Computer Science']}