Denna artikel tar upp två problem som ligger vid skärningspunkten mellan geometrisk analys och teoretisk datavetenskap: Den icke-linjära isomorfa Dvoretzky-teoretiken och utformningen av goda ungefärliga avståndsorakler för stor distorsion. Vi introducerar begreppet Ramsey-partitioner av ett ändligt metriska utrymme, och visar att förekomsten av goda Ramsey-partitioner innebär en lösning på det metriska Ramsey-problemet för stor distorsion (alias. Den icke-linjära versionen av den isomorfiska Dvoretzky-teoremen, som infördes av Bourgain, Figiel och Milman [8]. Vi fortsätter sedan att konstruera optimala Ramsey-partitioner, och använder dem för att visa att för varje ε (0,1) har varje n-punkts metriska utrymme en delmängd av storlek n 1−ε som inbäddar i Hilbert utrymme med distorsion O(1/ε). Detta resultat är bäst möjligt och förbättrar en del av den metriska Ramsey teorem av Bartal, Linial, Mendel och Naor [5], förutom att avsevärt förenkla sitt bevis. Vi använder våra nya Ramsey-partitioner för att designa ungefärliga avståndsorakler med en universell konstant frågetid, vilket täpper till en lucka som Thorup och Zwick lämnade kvar i [32]. Nämligen, vi visar att för varje n-punkt metrisk utrymme X, och k ≥ 1, finns det en O (k)-ungefärlig avstånd orakel vars lagringskrav är O n 1+1/k, och vars frågetid är en universell konstant. Vi diskuterar också applikationer av Ramsey-partitioner på olika andra geometriska datastrukturproblem, såsom utformningen av effektiva datastrukturer för ungefärlig rankning. Motiverad av sökandet efter en icke-linjär version av Dvoretzkys teorem utgjorde Bourgain, Figiel och Milman [8] följande problem, som idag är känt som det metriska Ramsey problemet: Med tanke på en målförvrängning α > 1 och ett heltal n, vad är den största k sådan att varje n-punkts metriska utrymme har en delmängd av storlek k som bäddar in i Hilbert utrymme med distorsion α? (Ring att ett metriska utrymme (X, d X) sägs inbädda i Hilbert utrymme med distorsion α om det finns en kartläggning f : X → L 2 sådan att för varje x, y X, vi har. Detta problem har sedan dess undersökts av flera författare, delvis motiverat av upptäckten av dess tillämpningar till online-algoritmer - vi hänvisar till [5] för en diskussion om historia och tillämpningar av det metriska Ramsey problemet. Det senaste arbetet med det metriska Ramsey problemet beror på Bartal, Linial, Mendel och Naor [5], som fick olika nästan optimala övre och nedre gränser i flera sammanhang. Bland resultaten i [5] är följande teorem som behandlar fallet av stor distorsion: För varje ε  på 0, 1), varje n-punkt metriska utrymme har en delmängd av storlek n 1−ε som inbäddar i en ultrametrisk med distorsion O Eftersom ultrametrics inbäddade isometrically i Hilbert utrymme, är detta verkligen en metrisk Ramsey teorem. Dessutom visades [5] att detta resultat är optimalt upp till log(2/ε)-faktorn, dvs. Det finns godtyckligt stora metriska n-punktsutrymmen, av vilka varje delmängd av storlek n 1−ε orsakar förvrängning (1/ε) i varje inbäddning i Hilbertrymden. Huvudresultatet av detta papper avslutar denna lucka: Under de fyra år som gått sedan vårt arbete på [5] har det skett en anmärkningsvärd utveckling i strukturteorin för finita metriska utrymmen. I synnerhet har teorin om slumpmässiga partitioner av metriska utrymmen förfinats avsevärt och har visat sig ha många tillämpningar inom matematik och datavetenskap (se till exempel [17, 25, 24, 1] och hänvisningarna i den). Utgångspunkten i det här dokumentet var vårt försök att se över det metriska Ramsey-problemet med hjälp av slumpmässiga partitioner. Det visar sig att detta tillvägagångssätt verkligen kan användas för att lösa det metriska Ramsey problemet för stor distorsion, även om det kräver införandet av en ny typ av slumpmässig partition, en förbättrad "pudding ojämlikhet" för kända partitioner, och en ny tillämpning av den slumpmässiga partitionsmetoden i inställningen av Ramsey problem. I Avsnitt 2 introducerar vi begreppet Ramsey-partitioner, och visar hur de kan användas för att ta itu med det metriska Ramsey-problemet. Vi fortsätter sedan i sektion 3 för att konstruera optimala Ramsey-partitioner, vilket ger Theorem 1.1. Vår konstruktion är inspirerad delvis av Bartals probabilistiska inbäddning i träd [4], och bygger på en slumpmässig partition på grund av Calinescu, Karloff och Rabani [9], med en förbättrad analys som stärker arbetet av Fakcharoenphol, Rao och Talwar [17]. I synnerhet är vårt bevis på Theorem 1.1 själv inneslutet, och betydligt enklare än beviset på resultatet från [5] som citeras ovan. Men byggandet av [5] är deterministiskt, medan vårt bevis för Theorem 1.1 är probabilistiskt. Dessutom ser vi inte ett enkelt sätt att använda vår nya strategi för att förenkla bevisen för ett annat huvudresultat av [5], nämligen fasövergången vid distorsion α = 2 (vi hänvisar till [5] för detaljer, eftersom detta resultat inte kommer att användas här). Resultaten av [5] som användes på ett avgörande sätt i vårt arbete [27] om den metriska versionen av Milmans subrymdsteoretik omfattas inte heller av detta dokument. Algoritmiska tillämpningar för konstruktion av närhetsdatastrukturer. Den huvudsakliga algoritmiska tillämpningen av det metriska Ramsey-teoremet i [5] är att erhålla de mest kända lägre gränserna på konkurrensförhållandet för det randomiserade k-serverproblemet. Vi hänvisar till [5] och hänvisningarna där för mer information om detta ämne, eftersom Theorem 1.1 inte ger förbättrade k-server nedre gränser. Men, Ramsey partitioner är användbara för att få positiva resultat, och inte bara algoritmiska lägre gränser, som vi nu beskriver. En ändlig metriska utrymme kan tänkas på som anges av dess n × n avståndsmatris. Men i många algoritmiska sammanhang är det värt att förbehandla denna data så att vi lagrar betydligt mindre än n 2 nummer, och fortfarande kunna snabbt ta reda på ungefär avståndet mellan två frågepunkter. Med andra ord, citera Thorup och Zwick [32], "I de flesta applikationer är vi inte riktigt intresserade av alla avstånd, vi bara vill ha förmågan att hämta dem snabbt, om det behövs". Behovet av sådan "kompakt" representation av mätvärden förekommer också naturligt i matematik; till exempel de metoder som utvecklats inom den teoretiska datavetenskapen (speciellt [11, 20] ) är ett viktigt verktyg i det senaste arbetet av Fefferman och Klartag [18] om utvidgningen av C m funktioner definieras på n punkter i R d till alla R d. En inflytelserik kompakt representation av mätvärden som används i teoretisk datavetenskap är den ungefärliga distansen oracle [3, 14, 32, 20]. Anges formellt, a (P, S, Q, D)-ungefärlig avstånd oracle på en ändlig metriska utrymme (X, d X ) är en datastruktur som tar förväntad tid P att förbehandla från den givna avståndsmatrisen, tar utrymme S att lagra, och ges två frågepunkter x, y  på X, beräknar i tid Q ett antal E(x, y) uppfyller I vad som följer kommer vi att avvika från ovanstående något besvärlig terminologi, och helt enkelt diskutera D-ungefärliga avstånd oracles (betonar distorsion D), och ange i ord värdena för andra relevanta parametrar (nämligen förbehandlingstid, lagringsutrymme och frågetid). Ett viktigt papper av Thorup och Zwick [32] konstruerar de mest kända avstånd orakel. Nämligen, de visar att för varje heltal k, varje n-punkt metrisk utrymme har en (2k − 1)-ungefärlig avstånd oracle som kan förbehandlas i tid O n 2, kräver lagring O k · n 1+1/k, och har frågetid O (k). Dessutom framgår det i [32] att denna snedvridning/nedläggning av lagringen är så gott som snäv:
Hans tillvägagångssätt var att börja med att åberopa Mendel och Naor Ref avstånd oracle för att få en initial distans uppskattning.
Ramsey partitions and proximity data structures
{'venue': 'J. European Math. Soc. 9(2): 253-275, 2007', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}