{"entities":{"Q997827":{"pageid":999675,"ns":120,"title":"Item:Q997827","lastrevid":57313296,"modified":"2026-03-30T09:31:50Z","type":"item","id":"Q997827","labels":{"en":{"language":"en","value":"Ramsey partitions and proximity data structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5177826"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$6B8CB875-D091-4635-8C24-0FDB5E80174E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"21087ced16e1309bdcf47d3d790fdb25bf979ddf","datavalue":{"value":{"text":"Ramsey partitions and proximity data structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q997827$FFD76FF6-511D-4FED-824E-585D40002140","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1bda22b006287835fbfdf788dc57c75f810bfda0","datavalue":{"value":"1122.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997827$36DE28AF-F902-4474-B8A2-17B55CEA25A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa1d27dbe5fc1b4ba00a1bf3c0a33f4f828f5be4","datavalue":{"value":"10.4171/JEMS/79","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997827$AF9E5187-F56F-44F4-8D3B-B0DE58F88255","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2129463e4fb202d617a918e802d846c3730ad87","datavalue":{"value":{"entity-type":"item","numeric-id":610753,"id":"Q610753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$A0A88D9F-8720-478B-807A-38690518CE27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e15064a955e2b0fc1477893d6cd3b38b1f1b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":185634,"id":"Q185634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$15215B5F-7BAF-4EBF-9D2D-BEFC4B34B6B9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"26780b1287f0091cd789fa2d15704011bf65df86","datavalue":{"value":{"entity-type":"item","numeric-id":171275,"id":"Q171275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$1CA96A11-0E4A-4F06-B3D4-75576CE8F93C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ba85540cb4336ce59517f6ba0ec3ed1362787641","datavalue":{"value":{"time":"+2007-08-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q997827$08F5536A-A788-414C-A790-477A70E52C70","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"200d8ce4a8a08da11764e9cab2c502868b970d9e","datavalue":{"value":"https://arxiv.org/abs/cs/0511084","type":"string"},"datatype":"url"},"type":"statement","id":"Q997827$3A6A40B1-65AC-4DA6-A7BB-255A86ED5D5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"45486968093feeddc2eaf0637809c3dd26db7142","datavalue":{"value":"http://www.ems-ph.org/journals/show_abstract.php?issn=1435-9855&vol=9&iss=2&rank=3","type":"string"},"datatype":"url"},"type":"statement","id":"Q997827$9FF128AB-F156-41BC-B00A-AA939CCD1908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fcc4c126c664933ce974257ca08d403af0bfe4f8","datavalue":{"value":"http://www.ems-ph.org/journals/show_pdf.php?issn=1435-9855&vol=9&iss=2&rank=3","type":"string"},"datatype":"url"},"type":"statement","id":"Q997827$2124CEED-D293-4AE2-A6B9-62043488B91B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d3b071fa3f97b0cd7e6e705ebf350f133140dcd","datavalue":{"value":"Summary: This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The nonlinear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (also known as the nonlinear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman). We then proceed to construct optimal Ramsey partitions, and use them to show that for every \\(\\varepsilon\\in(0,1)\\), every \\(n\\)-point metric space has a subset of size \\(n^{1-\\varepsilon}\\) which embeds into Hilbert space with distortion \\(O(1/\\varepsilon)\\). This result is best possible and improves part of the metric Ramsey theorem of \\textit{Y. Bartal, N. Linial, M. Mendel} and \\textit{A. Naori} [Ann. Math. (2) 162, 643--709 (2005; Zbl 1114.46007)], 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 \\textit{M. Thorup} and \\textit{U. Zwick} in [J. Assoc. Comput. Mach. 52, 1--24 (2005)]. Namely, we show that for every \\(n\\)-point metric space \\(X\\), and \\(k\\geq 1\\), there exists an \\(O(k)\\)-approximate distance oracle whose storage, requirement is \\(O(n^{1+1/k})\\), and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking.","type":"string"},"datatype":"string"},"type":"statement","id":"Q997827$67AEF67A-84E0-4B5E-A7F6-79379FF9977A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997827$FEC38CEF-A2F1-43B8-94A5-5F4FF6DED59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997827$920EA15B-C64B-4C50-9D48-37EA2C1621D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997827$0E9E8A9B-80E1-47F3-9029-B92A2863BC55","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee20a83b445fa3ab230af2d3df44c04ef2e8c5d7","datavalue":{"value":"5177826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997827$78E1EC13-C27C-482D-927C-8F5FCCB7653A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$0ECD3E74-BFCB-4834-8DC1-A89D48674161","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"605b778690b09ee78ae522e189d613585d021aff","datavalue":{"value":{"entity-type":"item","numeric-id":3581404,"id":"Q3581404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$75E6F2C9-3107-4A7C-BE09-8E3728D58152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01f91abdf6291a73a28c0c5d6b9c16690ebd0dc1","datavalue":{"value":{"entity-type":"item","numeric-id":3158524,"id":"Q3158524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$793BC6BA-4821-4217-A7B4-4681AAF96D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e0a6be99733eaeb2e2c0607e2cc442871e0104","datavalue":{"value":{"entity-type":"item","numeric-id":4210147,"id":"Q4210147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$C225189E-0C2F-4A51-B23F-4BBBF129357F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972a8bf34e7833efe7d50db13efe7b7a685cc396","datavalue":{"value":{"entity-type":"item","numeric-id":4508365,"id":"Q4508365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$A91DF673-7F83-4F34-B3F4-45AAD0F7B272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0037a94b770b923218ce260e5fa382b3caf10982","datavalue":{"value":{"entity-type":"item","numeric-id":596133,"id":"Q596133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$213D800A-81CD-4813-8150-B92F461C71DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80f52879ef8b98007a3c7339bc4e06b576933cc9","datavalue":{"value":{"entity-type":"item","numeric-id":1096846,"id":"Q1096846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$2FCD65EA-7CFF-4B6B-8AA6-D06F60DD6B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17eb8af3c7c9b7ff8c2635ff9b3fd8d17bed4b31","datavalue":{"value":{"entity-type":"item","numeric-id":4651539,"id":"Q4651539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$B53716C8-96CB-43FF-B061-4B917D4D18EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440ba0d9dbee427a1b508f6b771488e2dd84f87d","datavalue":{"value":{"entity-type":"item","numeric-id":4369857,"id":"Q4369857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$5E4A7661-F083-4698-9A7A-9C3B77254601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a73e0e4bbbee48dd64148f09a60032790810bb6","datavalue":{"value":{"entity-type":"item","numeric-id":2921658,"id":"Q2921658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$A9E6BFC1-8623-4236-9CC1-FDCA300DDDBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9562975b659ee36323bc10f44914f734dbe22ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4210144,"id":"Q4210144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$B565146C-FEB2-41DC-941D-7929C2DF083B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$BB19B6AE-52BC-4329-8A89-C41FD9EBCFC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2489700dabd9de7c8130e086b86c339d6ff0a3de","datavalue":{"value":{"entity-type":"item","numeric-id":5543308,"id":"Q5543308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$6239229D-4729-4EDA-9EFD-0442C3E3E4EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77edea93649703069ebe293e1a5e337050174e5c","datavalue":{"value":{"entity-type":"item","numeric-id":5917578,"id":"Q5917578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$FEAA9519-170D-4A1C-86E6-6BE0B965E79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4bddf54130ed36fd250dd95b7c6dacd4beef135","datavalue":{"value":{"entity-type":"item","numeric-id":4829019,"id":"Q4829019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$C63B382B-9CA3-4E23-A903-78A3834063E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1780111e011426b744f71f8db81e0e5f9287ea16","datavalue":{"value":{"entity-type":"item","numeric-id":5470729,"id":"Q5470729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$7EC88682-B62F-43DD-A121-11F440B664B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05e150681c1d0241ecb463ace4c088cbd7d131cd","datavalue":{"value":{"entity-type":"item","numeric-id":3319776,"id":"Q3319776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$F3E2AD80-87D2-4440-ADA4-E8F06B14DAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e089c6b6850b045b5c203bff59161ae09733bf7d","datavalue":{"value":{"entity-type":"item","numeric-id":1586729,"id":"Q1586729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$4378F4B5-C93E-49AE-B536-86D5A6DD63C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46bdb922108405c2f2f54676442fca7042dce85d","datavalue":{"value":{"entity-type":"item","numeric-id":2571745,"id":"Q2571745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$43A15998-2503-49E2-8A13-350B40909147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3c5f04d0a16e2231f11ce28024640b8a16b02cc","datavalue":{"value":{"entity-type":"item","numeric-id":1770278,"id":"Q1770278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$8380912F-FC91-40F4-A6AE-5604CDC5FADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda0716344d26183535d0b48ba2c329efdfdcef2","datavalue":{"value":{"entity-type":"item","numeric-id":1912794,"id":"Q1912794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$D8DF16C7-DC9D-4192-88EE-5091DECE4DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e57556bfe51a9429dedd5e53334c3a1293cff51f","datavalue":{"value":{"entity-type":"item","numeric-id":1763640,"id":"Q1763640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$7E32EB6C-6FA5-439F-BD9F-B69F2BD85E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b52c3720020853b3b190be4f2a9cc366b3f73780","datavalue":{"value":{"entity-type":"item","numeric-id":2566038,"id":"Q2566038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$778BCAAE-CA89-40B1-A47D-A1416C147894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b5c2a2555a6adb5115824b34a87580b6889dc09","datavalue":{"value":{"entity-type":"item","numeric-id":5716780,"id":"Q5716780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$BC61C554-3EF9-4C1B-88C9-ED1E6C6E74A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5b1f87c3d87894daa16828ce703f061534bc1c8","datavalue":{"value":{"entity-type":"item","numeric-id":3580975,"id":"Q3580975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$86970534-59D2-4127-9A8D-CC8BF559623C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc0938da24d4d7b62d960ae809bc0cd5ef797e5d","datavalue":{"value":{"entity-type":"item","numeric-id":1115187,"id":"Q1115187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$351F0539-495E-4BD7-BB52-6531A6210C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6683c384f607c91537e854f0ac90a517a630c9e","datavalue":{"value":{"entity-type":"item","numeric-id":4796165,"id":"Q4796165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997827$E6704A54-12FC-4DB2-8C08-CEA9E8678DDE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55fb59f68046a5105859fe43cda10f48a07a773d","datavalue":{"value":{"entity-type":"item","numeric-id":1932671,"id":"Q1932671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b8fe2328bb7411d8f8aeedbe6e7ac409702b968","datavalue":{"value":{"amount":"+0.7759964466094971","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q997827$6696A9E5-5A21-41CA-AB89-BF19A3CE18D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:997827","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:997827"}}}}}