I en begränsad kortaste sökväg (CSP) fråga, varje kant i vägnätet är associerad med både en längd och en kostnad. Med tanke på ett ursprung s, en destination t, och en kostnadsbegränsning., är målet att hitta den kortaste vägen från s till t vars totala kostnad inte överstiger. Eftersom exakt CSP är NP-hård, tidigare arbete fokuserar främst på ungefärliga lösningar. Trots detta är befintliga metoder fortfarande oöverkomligt dyra för stora vägnät. Två huvudsakliga skäl är i) att de misslyckas med att utnyttja de speciella egenskaperna hos vägnät och ii) att de flesta av dem behandlar frågor utan index; de få befintliga index förbrukar stora mängder minne och ändå har begränsad effektivitet i att minska frågekostnader. Motiverade av detta föreslår vi COLA, den första praktiska lösningen för ungefärlig CSP-bearbetning på stora vägnät. COLA utnyttjar fakta om att ett vägnät effektivt kan delas upp, och att det finns en relativt liten uppsättning landmärken som ofta visas i CSP resultat. Följaktligen indexerar COLA hörnen ligger på partitionsgränserna, och tillämpar en on-the-fly algoritm som kallas α-Dijk för vägberäkning inom en partition, som effektivt beskär vägar baserade på landmärken. Omfattande experiment visar att på kontinentsstora vägnät, COLA besvarar en ungefärlig CSP fråga under andra gången, medan befintliga metoder tar timmar. Intressant, även utan ett index, α-Dijk algoritmen i COLA fortfarande överträffar tidigare lösningar med mer än en storleksordning.
I kontinentala vägnät med längd- och kostnadsmått använder COLA REF grafpartition för att minimera sökvägens längd inom en kostnadsbegränsning.
Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}