Fréchet avstånd är ett populärt avstånd mått för kurvor som naturligt lämpar sig för grundläggande beräkningsuppgifter, såsom kluster, närmaste granne sökning, och sfärisk räckvidd sökning i motsvarande metriska utrymme. Dess inneboende komplexitet innebär dock i praktiken betydande utmaningar för beräkningarna. För att ta itu med detta problem studerar vi förvrängning av den probabilistiska inbäddning som är resultatet av att projicera kurvorna till en slumpmässigt vald linje. En sådan inbäddning kan användas i kombination med t.ex. Lokalt känslig hasch. Vi visar att i värsta fall och under rimliga antaganden, det diskreta Fréchet avståndet mellan två polygonala kurvor i IR 2 eller IR 3 komplexitet t bryts av en faktor linjär i t med konstant sannolikhet. Vi visar övre och nedre gränser på förvrängningen. Fréchetavståndet är ett avståndsmått för kurvor som naturligt lämpar sig för grundläggande beräkningsuppgifter, såsom klustring, sökning efter närmaste granne och sfärisk sökning i det motsvarande metriska utrymmet. Deras inneboende komplexitet innebär dock i praktiken betydande utmaningar för beräkningarna. Sfäriska sökningar under Fréchet avstånd var nyligen ämnet för den årliga ACM SIGSPAIAL GISCUP konkurrens 1, som belyser relevansen och svårigheten att utforma effektiva datastrukturer för detta problem. Samtidigt visar Afshani och Driemel lägre gränser på space-query-tradeoff i pekarmodellen [1] som visar att detta problem är ännu svårare än simplex-range sökning. Den beräkningsmässiga komplexiteten i att beräkna ett enda Fréchet-avstånd mellan två givna kurvor är ett välstuderat ämne [2, 6-9, 12, 15]. Man tror att det tar tid som är quadratic i längden av kurvorna och denna körtid kan uppnås genom att tillämpa dynamisk programmering. I denna litteratursamling utmärker sig fallet med endimensionella kurvor under det kontinuerliga Fréchetavståndet. I synnerhet är inga lägre gränser kända vid beräkning av det kontinuerliga Fréchet-avståndet mellan 1-dimensionella kurvor. Det har konstaterats att problemet har en särskild struktur i detta fall [10]. Kluster under Fréchet avstånd kan göras effektivt för 1-dimensionella kurvor [13], men verkar vara svårare för kurvor i planet eller högre dimensioner. Bringmann och Künnemann använder projektioner till linjer för att påskynda deras approximation algoritm för Fréchet avstånd [8]. De visar att avståndsberäkningen kan göras i linjär tid, om de konvexa skroven i de två kurvorna är åtskilda. Det är frestande att tro att kurvorna begränsas till endimensionellt utrymme gör * Driemel har fått stöd av NWO Veni-projektet "Clustering time series and trajectories (10019853)".
Först nyligen studerade REF de första probabilistiska inbäddningarna av Fréchet-avståndet genom att projicera kurvorna på en slumpmässig linje.
Probabilistic Embeddings of the Fréchet Distance
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}