{"entities":{"Q1853173":{"pageid":1863915,"ns":120,"title":"Item:Q1853173","lastrevid":71501550,"modified":"2026-04-13T22:41:01Z","type":"item","id":"Q1853173","labels":{"en":{"language":"en","value":"Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856503"}},"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":"Q1853173$BE314FF0-57E2-4CFE-A54E-CA58F2A0B605","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f930989dfe3e80fd012f26b5d90e0fc14cae677","datavalue":{"value":{"text":"Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853173$D98E2E04-D68C-41E3-978A-4131F2F56420","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f5bd5388d10cb423ea929613f682c7c6303d127","datavalue":{"value":"1042.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853173$BD55F83C-FB0F-42FD-BACD-9FF705B4F9A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b6cb248528c24e6491db89b186241461b565ede","datavalue":{"value":"10.1016/S0020-0190(02)00344-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853173$8FEF97D5-8593-4990-8A6F-CB359FBB28A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0923fcc1a071ac7856fb3521f67450dafd6199a3","datavalue":{"value":{"entity-type":"item","numeric-id":340530,"id":"Q340530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$26C74328-5735-4F35-94CC-630473B654B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3eb16c5a8e9bfa4f01801ab5c4d2a359bd166b4b","datavalue":{"value":{"entity-type":"item","numeric-id":270015,"id":"Q270015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$7A05A79F-37AC-47B6-B3D8-E44FDBFB1D3B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$39BF4B91-B465-46EA-B663-DAB43C1BB571","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853173$BBFD599E-55EC-40E1-B0EF-C025D4946BC3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa213271f015882b07d29642cbd751ce48d39eb0","datavalue":{"value":"Proximity searches become very difficult on ``high dimensional'' metric spaces, that is, those whose histogram of distances has a large mean and/or a small variance. This so-called ``curse of dimensionality'', well known in vector spaces, is also observed in metric spaces. The search complexity grows sharply with the dimension and with the search radius. We present a general probabilistic framework applicable to any search algorithm and whose net effect is to reduce the search radius. The higher the dimension, the more effective the technique. We illustrate empirically its practical performance on a particular class of algorithms, where large improvements in the search time are obtained at the cost of a very small error probability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$868FB644-4229-4A7D-B94C-232D4DDE0689","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853173$C713DBCD-EC4B-46A6-8F7B-DCC342CFCF19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44ba45c31368af1cec99d891d1a62818a25e0b30","datavalue":{"value":"1856503","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853173$EF448819-028A-46BE-BC0B-8CCBF19FF59B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"025c9ce82a98680740654875af148d8a66c07646","datavalue":{"value":"Metric spaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$40698A20-581F-4622-A35A-8965B58B1D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"902ea1e764c15bc6a15e1aa8072aadc733adfd35","datavalue":{"value":"Proximity searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$CCB9F410-2805-4E0F-AC0D-B8395343895A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bbf3c324033e2f654ce92e3707a4d118894f2a0","datavalue":{"value":"Nearest neighbor searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$F36E6B47-92D5-49E6-AD44-0DA1737522C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5b632e2fbdabca98dea3a3f58a308869a881f6f","datavalue":{"value":"Distance based indexing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$050ECD33-6AA6-44AF-A38F-4052C8B213FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fde99e1a3e78525963ff37ff468b737833456fba","datavalue":{"value":"Probabilistic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$3849A8CC-7320-4FFC-A29D-A83F68FE03B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbff35acdd31439d13dd3892bdda5725c18fc300","datavalue":{"value":"Approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853173$B3E30EC2-8313-4450-8453-811FCE93D372","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":"Q1853173$726B90CA-7E4C-45C8-9CE3-D281A4EDED07","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1777c3456b27765bf751250b89e228679b0833fd","datavalue":{"value":{"entity-type":"item","numeric-id":3128920,"id":"Q3128920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$E3325D7E-7542-40C2-A48F-561DF61A19DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31c9cb15ff659dc821e997bee4aea76d2288201c","datavalue":{"value":{"entity-type":"item","numeric-id":4198073,"id":"Q4198073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$3CAF77F3-1CD3-4CEE-BDC2-70879A24126B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6cc08c962e336aae0dc30562b55c2aa19d79b6e","datavalue":{"value":{"entity-type":"item","numeric-id":1857244,"id":"Q1857244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$061750C5-1B4F-4C61-BB42-5960D744CD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24d018e913c5e7ae7fc78a554af4ccf295f22860","datavalue":{"value":{"entity-type":"item","numeric-id":2817599,"id":"Q2817599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$198FBF06-1683-41E3-AB4E-4D4C4CDEEFB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c18ae9a2fd669946157fd4e49e0a2e6180aa0ee9","datavalue":{"value":{"entity-type":"item","numeric-id":1293352,"id":"Q1293352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$C6DC5E58-02A3-4921-A4A9-53A4DCC0BC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2e403264e177a273137d3a06c292ecb02f28828","datavalue":{"value":{"entity-type":"item","numeric-id":4460275,"id":"Q4460275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853173$2C4C23C8-7FC8-4784-AB33-BADB2A3973F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9ffc8d0759765b75b09d0b3c1784d11106346a9","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00344-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853173$1C58C6C7-775E-42C8-A8A2-8506B5E95FBF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9cb66ca5022ed20e0382da371bdd31ccfb2eeea3","datavalue":{"value":"W2028975680","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853173$46CE23F7-F05F-4AC6-B1B5-C1F3B9AB6837","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614847d08937cbeb90dd1cd62d0aa8f32a51fd8c","datavalue":{"value":{"entity-type":"item","numeric-id":4418153,"id":"Q4418153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdd831cc7d0c5de43df0d8766a882e5f2afbcdd6","datavalue":{"value":{"amount":"+0.88920146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853173$4BC34784-06CD-4BDF-84DD-29166ECFFB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7537eeb506ecc36109059d828a44398fa2441b8","datavalue":{"value":{"entity-type":"item","numeric-id":5307550,"id":"Q5307550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5a5256abbd7318d1f61ca969b14a3eef5085d43","datavalue":{"value":{"amount":"+0.886016","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853173$770730A7-D30B-4716-92C0-B557CBC213BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b25b2aec56cc60833aa43035c02c5085c6706663","datavalue":{"value":{"entity-type":"item","numeric-id":294719,"id":"Q294719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ffcf389534122938f7625887e9bc5b9b2d87c70","datavalue":{"value":{"amount":"+0.86824095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853173$0A49C675-F50A-4E0C-A9F6-7C0938B5F6A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b7ef29e4349e6a1cb243321120a58093b656497","datavalue":{"value":{"entity-type":"item","numeric-id":876710,"id":"Q876710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43553a24fb2228778781d8cbd5b26d2d72cbb8e0","datavalue":{"value":{"amount":"+0.867373","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853173$8B3266E5-4F6F-4A15-85AC-15411849FAB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"806930cbcb289e87d49a150a25711a42a68cba07","datavalue":{"value":{"entity-type":"item","numeric-id":3586478,"id":"Q3586478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79569ccce6348c0c78f910c5773433d02c8a1eb3","datavalue":{"value":{"amount":"+0.86595726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853173$A9198556-954D-47E9-9DA5-AC4E6316DEB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Probabilistic_proximity_search:_Fighting_the_curse_of_dimensionality_in_metric_spaces."}}}}}