Det metriska skissproblemet definieras enligt följande. Med tanke på ett mått på n punkter, och > 0, vill vi producera en liten storlek data struktur (sketch) som, med tanke på varje par av punkt index, återhämtar avståndet mellan punkterna upp till en 1 + distorsion. I detta papper betraktar vi mått som induceras av 2 och 1 normer vars spridning (förhållandet mellan diametern och närmaste par avstånd) begränsas av 0 > 0. En välkänd dimensionsreduktionssats på grund av Johnson och Lindenstrauss ger en skiss av storlek O( −2 log(șn)n log n), dvs. O( −2 log(șn) log n) bitar per punkt. Vi visar att denna gräns inte är optimal, och kan avsevärt förbättras till O( −2 log(1/ ) · log n + log log 0) bitar per punkt. Dessutom visar vi att vårt band är tätt upp till en faktor för logg(1/ ). Vi överväger också skissning av allmänna mått och ger en skiss av storlek O (n log(1/ ) + log log 0) bitar per punkt, som vi visar är optimal.
Därefter för d = ε −2 log n rymdanvändning per punkt av den metod som beskrivs i REF är O(d log(1/ε)).
Near-Optimal (Euclidean) Metric Compression
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}