Ramsey partitions and proximity data structures

Manor Mendel, Assaf Naor

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every ε ∈ (0,1), any n-point metric space has a subset of size n 1-ε which embeds into Hilbert space with distortion 0(1/ε). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in [26]. Namely, we show that for any n point metric space X, and k > 1, there exists an O (k)-approximate distance oracle whose storage requirement is O(n1+1/k), and whose query time is a universal constant. We also discuss applications to various other geometric data structures, and the relation to well separated pair decompositions.

שפה מקוריתאנגלית
כותר פרסום המארח47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
עמודים109-118
מספר עמודים10
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2006
אירוע47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, ארצות הברית
משך הזמן: 21 אוק׳ 200624 אוק׳ 2006

סדרות פרסומים

שםProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (מודפס)0272-5428

כנס

כנס47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
מדינה/אזורארצות הברית
עירBerkeley, CA
תקופה21/10/0624/10/06

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Ramsey partitions and proximity data structures'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי