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.
Ett mycket färskt dokument från Indyk och Wagner REF tar upp det svårare problemet med att tillnärma de inre produkterna mellan par av punkter upp till ett relativt fel på ε, för specialfallet k = n, och bestämmer det minsta antalet bitar som krävs här upp till en logfaktor(1/ε).
Near-Optimal (Euclidean) Metric Compression
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}