Att identifiera en föredragen rutt är ett viktigt problem som hittar applikationer i karttjänster. När en användare planerar en resa inom en stad, kanske användaren vill hitta "en mest populära rutt så att den passerar genom köpcentrum, restaurang och pub, och restiden till och från hans hotell är inom 4 timmar." Ingen av algoritmerna i det befintliga arbetet med ruttplanering kan dock användas för att besvara sådana frågor. Motiverade av detta definierar vi problemet med keywordaware optimal rutt fråga, betecknad av KOR, vilket är att hitta en optimal rutt så att den täcker en uppsättning användardefinierade sökord, en specificerad budget begränsning är nöjd, och en objektiv poäng för rutten är optimal. Problemet med att svara på KOR-frågor är NP- hårt. Vi utformar en approximationsalgoritm OSScaling med bevisbara approximationsgränser. Baserat på denna algoritm, ytterligare en effektivare approximation algoritm BucketBound föreslås. Vi designar också en girig approximationsalgoritm. Resultat av empiriska studier visar att alla föreslagna algoritmer är kapabla att svara på KOR frågor effektivt, medan BucketBound och Greedy algoritmer kör snabbare. De empiriska studierna ger också insikt i exaktheten hos de föreslagna algoritmerna.
REF konstruerar en optimal rutt som täcker användarspecificerade kategorier som hör samman med platser.
Keyword-aware Optimal Route Search
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}