{"entities":{"Q1115187":{"pageid":1125936,"ns":120,"title":"Item:Q1115187","lastrevid":77753450,"modified":"2026-05-06T09:58:59Z","type":"item","id":"Q1115187","labels":{"en":{"language":"en","value":"An O(n log n) algorithm for the all-nearest-neighbors problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4085025"}},"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":"Q1115187$57BBE36C-E82F-42BC-B4EF-F2998BEC9FC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0f9ed12d1c7521c29e29605a9e8c1e9c4ea0ccd8","datavalue":{"value":{"text":"An O(n log n) algorithm for the all-nearest-neighbors problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115187$C70CCDD2-2326-41CB-B6B7-42381690AAF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd7190d31c674fa3eeef3cf0c4755c353b3e0d34","datavalue":{"value":"0663.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$0E40119A-BD51-4DC5-B40A-DD5A8DF550ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2098826db9c7674134f0a70454ae48f4f9332614","datavalue":{"value":"10.1007/BF02187718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$64F2FFAB-FC85-4AD9-84D2-B71583B03B3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8de4a6f713c83ebac2233da0ff14b109d2f769d","datavalue":{"value":{"entity-type":"item","numeric-id":687083,"id":"Q687083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$207F27FA-0112-4483-9A2B-92D52F2BF4DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$86453042-C34D-49EF-912B-B9EF0BC12E22","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1115187$5B8A451E-7391-4C0F-AACE-C599A638747A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"011b785e96473bf3c57aef1f67ba5c4ad30875c0","datavalue":{"value":"https://eudml.org/doc/131067","type":"string"},"datatype":"url"},"type":"statement","id":"Q1115187$DD508D06-D509-4EDA-9CA9-6EA9B2BDE99D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ebefa4708ad88d14a1e24501c59d3d761edff456","datavalue":{"value":"Given a set V of n points in k-dimensional space, and an \\(L_ q\\)-metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each point p in V, find all those points in V-\\(\\{\\) \\(p\\}\\) that are closest to p under the distance metric \\(L_ q\\). We give an O(n log n) algorithm for the all-nearest-neighbors problem, for fixed dimension k and fixed metric \\(L_ q\\). Since there is an \\(\\Omega\\) (n log n) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest- neighbors problem (for \\(k=1)\\), the running time of our algorithm is optimal up to a constant factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115187$2F4B9305-0458-480C-B092-31D44E29C848","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$35F8DF10-C55C-47D8-AC1E-01A967D9A27C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9e5da3a44a6865fa2cb8e31e2f51d7e1c349146a","datavalue":{"value":"51K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$5CF46CC6-74BF-4221-A357-9CE2B36587AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$A9AAFCB6-66B0-4EE8-99D1-9574255980BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$4381179F-DB9F-44A4-B0B3-FF166F6F2D7C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a46767a319776424a9ca11f2679c005e0b4b7beb","datavalue":{"value":"4085025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$756772B0-D2EF-4E67-93F6-52274C9C7F39","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115187$6FEF8FC2-0F53-4A42-9530-398C6F33A4B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9aea1be8fa999b1c7a1a274e1419d89bc90c677e","datavalue":{"value":"Minkowski metric","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115187$BB1E1DAC-4EE6-4E46-9D55-E882766A3CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76391b918e53c93022e3ba97c119cb7d09f89e61","datavalue":{"value":"all-nearest-neighbors problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115187$57FC5F53-F068-4733-9F21-FB4604DB9A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38358a8345a0af63d27d9e4ed593b085b0c68bb2","datavalue":{"value":"algebraic decision-tree model of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115187$AA0017CE-6B49-4FBE-9734-AB106BF25048","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"de112ac5609bb70c1a743d492c86d40e1857ae9c","datavalue":{"value":"Q29396159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115187$A0310992-6CE9-4386-93C5-8708BAD679BB","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":"Q1115187$9FE8246A-9EA1-41BA-BBCF-2297D884EC4A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dc7eb8caf969204b8972e6206e244f9c8f10485","datavalue":{"value":{"entity-type":"item","numeric-id":148390,"id":"Q148390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$79AC715E-F708-4A39-B8A0-932D5D7B2C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68f5eb037e61a7c76ed9ac94a6469f8dcdf10dcc","datavalue":{"value":{"entity-type":"item","numeric-id":1244819,"id":"Q1244819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$18ED5CF9-CD09-4EA1-956F-7EA7B97F2C5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b11f46880b422209c9517febd241f5ae6afb3de","datavalue":{"value":{"entity-type":"item","numeric-id":3883531,"id":"Q3883531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$881E9B54-FE76-4221-92FE-8DE043C05441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$D9D6C1C6-C693-402F-ABFE-5C11EA10A2F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e16d1dc4052e71d6b4ce452bdd1e1e49e7dff8b","datavalue":{"value":{"entity-type":"item","numeric-id":4144192,"id":"Q4144192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$66802A4E-0F67-43D5-911F-0578CDA48578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e32cd00e50889ce6fdac19be614a9be1a54020","datavalue":{"value":{"entity-type":"item","numeric-id":4164569,"id":"Q4164569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115187$23FFE66C-5F79-4721-AC6C-4A883D2951C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd5dddda6b3f617327830d091a6ecac9b81ea415","datavalue":{"value":{"entity-type":"item","numeric-id":1182607,"id":"Q1182607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60974921a7bc8d820f28a1c49c43a21a6aeb5179","datavalue":{"value":{"amount":"+0.861324667930603","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":"Q1115187$060A918B-89A2-4A22-8E9D-D28E820208F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce57a4d3ce71fa033901f4ad9d6fc596d5dd5493","datavalue":{"value":{"entity-type":"item","numeric-id":3805895,"id":"Q3805895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faa2883023715c493a851993a1f1232ae0d0d7c9","datavalue":{"value":{"amount":"+0.8500317931175232","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":"Q1115187$0A64F56F-4DA0-438F-92C3-AADCECCDEB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"271d8a683f50da58a98802d430f2c4f93143beb2","datavalue":{"value":{"entity-type":"item","numeric-id":1244819,"id":"Q1244819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca354edb77257064fc37d9b88136485231a25c56","datavalue":{"value":{"amount":"+0.8465532660484314","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":"Q1115187$E2340322-54FF-472E-BC5A-45AD1AF47FBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"109a14fce8698a3104a60cc9e66ddaffb4dbbdd7","datavalue":{"value":{"entity-type":"item","numeric-id":1293352,"id":"Q1293352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"332c2c3f4d3deecdc38a82f97047cc77c438f4f2","datavalue":{"value":{"amount":"+0.8438687324523926","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":"Q1115187$AAE99354-F55A-498E-A3C1-0F3F8F3906CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76b5666221147eb71bd7fc681a28ea55cf38be09","datavalue":{"value":{"entity-type":"item","numeric-id":3140429,"id":"Q3140429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4438a5d86986ec53116ce799ad3032a2923441e","datavalue":{"value":{"amount":"+0.8434945940971375","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":"Q1115187$C7BF4975-6ECC-4686-8540-DCA3B5639C31","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An O(n log n) algorithm for the all-nearest-neighbors problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_O(n_log_n)_algorithm_for_the_all-nearest-neighbors_problem"}}}}}