Abstrakt. I det här dokumentet diskuterar vi en ny typ av fråga i rumsliga databaser, kallad Trip Planning Query (TPQ). Med tanke på en uppsättning av intressanta punkter ¢ i rymden, där varje punkt tillhör en viss kategori, en utgångspunkt £ och en destination ¤, TPQ hämtar den bästa resan som börjar på £, passerar genom minst en punkt från varje kategori, och slutar på ¤. Till exempel, en förare som reser från Boston till Providence kanske vill stanna till en bensinstation, en bank och ett postkontor på väg, och målet är att ge honom bästa möjliga rutt (när det gäller avstånd, trafik, vägförhållanden, etc.). Svårigheten med denna fråga ligger i förekomsten av flera val per kategori. I denna uppsats studerar vi snabba approximationsalgoritmer för TPQ i ett metriska utrymme. Vi tillhandahåller ett antal approximationsalgoritmer med approximativa proportioner som beror på antingen antalet kategorier, det maximala antalet poäng per kategori eller båda. Därför, för olika fall av problemet, kan vi välja algoritmen med bästa approximation förhållande, eftersom de alla kör i polynom tid. Dessutom använder vi några av de föreslagna algoritmerna för att härleda effektiv heuristik för stora datamängder som lagras i externt minne. Slutligen ger vi en experimentell utvärdering av de föreslagna algoritmerna med hjälp av både syntetiska och verkliga datauppsättningar.
Reseplaneringsfrågan (TPQ) föreslogs ursprungligen i REF.
On trip planning queries in spatial databases
{'venue': 'In SSTD', 'journal': None, 'mag_field_of_study': ['Computer Science']}