{"entities":{"Q1180539":{"pageid":1191288,"ns":120,"title":"Item:Q1180539","lastrevid":46220629,"modified":"2025-12-24T08:28:57Z","type":"item","id":"Q1180539","labels":{"en":{"language":"en","value":"Divided \\(k-d\\) trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 26007"}},"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":"Q1180539$943B7E7F-9ADC-49C6-A8C2-42EDFA26D56F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"749f7487098ba2d590264981308e3b1d5a02210d","datavalue":{"value":{"text":"Divided \\(k-d\\) trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180539$596D74BF-15AB-491C-BABF-B285262904AC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a72ec005fa0e3ea9f5ed73a40825752d699c9221","datavalue":{"value":"0745.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$7FC25E40-771D-410A-A5CB-91C03EEF3EE6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a0bfa7973d2f17de2b81b92587ae4449167492d","datavalue":{"value":"10.1007/BF01759075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$45B28015-AA0F-4BB4-8CEC-DDF5B183F920","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0974031926d33b0875f26afb84ba01896d0efa16","datavalue":{"value":{"entity-type":"item","numeric-id":1120265,"id":"Q1120265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$AD29CDF1-1EB0-4103-B4C4-4F35A77EB191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f813421ca1324eea7267dc8879260a77170dbb2","datavalue":{"value":{"entity-type":"item","numeric-id":419362,"id":"Q419362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$17F4DFC6-F06A-4A44-AAE1-E01D773AC948","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$27540D5E-207F-4507-AD07-02B83F9203B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180539$954E6EF2-2B22-4084-9764-E83D321241A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11e6bc7868bfe257c41f9e73ea9db0c6ac83799c","datavalue":{"value":"The paper proposes a new dynamic data structure, the divided \\(k-d\\)-tree, supporting range queries in two and more dimensions. A modified version furthermore supports splits and concatenates in all dimensions. Exact match queries can be answered in time \\(O(\\log(n))\\). The worst case complexity for the dynamic updates and the range query is up to a multiplicative factor of \\(O(\\log^{1/d})\\) equal to that of the best known data structure for range queries in linear storage: the quad-tree and the \\(k-d\\)-tree; these structures are, however, not easy to maintain under inserts and deletes, and if they are made dynamic at all they can't be balanced and therefore the worst case search and update time can easily degrade.   The structure, which is easiest explained for dimension 2, shares in its design the key idea from the original \\(k-d\\)-tree; at every level of the tree divide the nodes in the subtree according to one of the dimensions. But rather than letting the dimensions alternate as in the original \\(k- d\\)-tree, the dimension remains fixed till about half way down the tree; subsequently the other dimension is used. By carefully balancing the tree size at the intermediate level the polylog factor in the performance estimates of the structure is optimized. The generalization for dimensions \\(d>2\\) is straightforward.   The structure is build from \\(2-3\\)-trees for which a well known efficient split-concatenate algorithm exists; this structure, with some modifications can be extended to make the devided \\(k-d\\)-tree concatenable in all dimensions with an update query time equal to the divided \\(k-d\\)- tree as described before.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180539$5A9EE4B5-6DAA-4868-A828-30706BE8D6EC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ca9cd2a9131e1d8839142cee57f1e863d7371382","datavalue":{"value":{"entity-type":"item","numeric-id":582045,"id":"Q582045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$43B53165-0637-401A-A79E-80DA07BF2810","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$C9FCD348-1FB6-49C3-A2CF-B5F1C1F84DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$BB8C38C9-EECB-4551-8B12-AFF669429F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$1C1CB689-DDB3-444B-A931-67C1F8D5D5F8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aa966a2c03ca960404d3d247c5a0b946fa6539cd","datavalue":{"value":"26007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$959C9740-523A-4824-B756-CE337D2F7BCF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8c0d9685aea0c090b360f522fc529eac4f486ae","datavalue":{"value":"dynamic data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180539$734FB693-89E3-4BAD-86C4-8CF7E4BD0725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab85e796cb2b90685e0f1f81bf58e2473ed9cbf1","datavalue":{"value":"\\(k-d\\)-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180539$DC51015A-CDD5-4FC6-A256-3FE3E6BE9EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"500b9493b9b7f6cb27c10220d4ded6cdfa7fe049","datavalue":{"value":"range queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180539$62026430-34E0-408E-80DF-293B599635BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5b425edfcbabb01d49b8a8b234bede1c0a834f5","datavalue":{"value":"quad-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180539$45025B38-113D-4321-86AB-E92AA68E56E4","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":"Q1180539$2FD73E5F-F7D5-4848-96DF-639E8968B1C6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$04C56884-5800-4A00-A2B6-EB18A4F0A325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eb040f4f53698848aa91aa2991b3af0b6cf962f","datavalue":{"value":{"entity-type":"item","numeric-id":4062679,"id":"Q4062679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$35551BB9-FDF6-436D-A46F-8E2D54389FB5","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":"Q1180539$423EB582-3064-4297-8107-3426C4873358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b7ec1e64faa28ff7142d9326d8b09ef039f5d48","datavalue":{"value":{"entity-type":"item","numeric-id":1256856,"id":"Q1256856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$EC711D72-6B51-4BFB-9D78-1BD69EE38592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4513c5833bc466d4a79387675503215f33e20eb0","datavalue":{"value":{"entity-type":"item","numeric-id":1394116,"id":"Q1394116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$A2F58CF5-B86F-43FA-821A-78B8C1994F6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$56DECD3B-DBF4-4CBB-8B1A-2B8964DD70E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecebae1c9f2b5a1bf78fe4ceaeea662c1f278df5","datavalue":{"value":{"entity-type":"item","numeric-id":1322468,"id":"Q1322468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$DC9A9ED7-91DB-4C7C-A11B-760847426AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd1462286ac5df294dbd58d9be71779e0279c3c","datavalue":{"value":{"entity-type":"item","numeric-id":797269,"id":"Q797269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$35C9777F-1F10-4985-AD13-0FF026EF2214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"900ec59125add65ef1a4c201cf6caf4bd0bcc622","datavalue":{"value":{"entity-type":"item","numeric-id":1152223,"id":"Q1152223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$F083499F-B4A4-4C6D-8DA7-16E643042E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7df946a2e9912da1ff2ed3e8b7297d553149a2c","datavalue":{"value":{"entity-type":"item","numeric-id":1166932,"id":"Q1166932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$95E273B5-659B-43D9-8974-5DFF9CE9128F","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":"Q1180539$293BE1F2-E4BB-450E-88E5-564005AFECF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90982d7813495812818b90d95d5cde9a55d1f5f","datavalue":{"value":{"entity-type":"item","numeric-id":3766892,"id":"Q3766892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180539$322D1143-0CA5-410B-8F52-C0D726BD905E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f0385edf9483b2f9a8bf1457f2f01b169a3bf5a5","datavalue":{"value":"https://doi.org/10.1007/bf01759075","type":"string"},"datatype":"url"},"type":"statement","id":"Q1180539$BE3E9BC4-18F7-4E05-BC52-89700033498E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f4a2f5331cb8fcc77e1f82260a9e623cf704ac0f","datavalue":{"value":"W1530943085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180539$8A6ADB4C-EDBD-4B7A-B7D4-D7BA815128B1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"943bc78eacf660a4e1d415c8de2f174711a4537b","datavalue":{"value":{"entity-type":"item","numeric-id":5405088,"id":"Q5405088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"895d500d032439f0b9ca2533491569f2a003a2e1","datavalue":{"value":{"amount":"+0.8124830722808838","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":"Q1180539$898854A3-20E0-4F19-AD7A-9079833D4EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3022804e87e4183cc252902c35c50e9ae3518f23","datavalue":{"value":{"entity-type":"item","numeric-id":3678701,"id":"Q3678701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cd33c0f0e1ac31e45b71dfc88636639b83c0f7d","datavalue":{"value":{"amount":"+0.8048285245895386","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":"Q1180539$0CAAD6C9-94AA-4152-AF05-17E70F7C8CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2956de18d395888f15c5656b5934a5b57f12696f","datavalue":{"value":{"entity-type":"item","numeric-id":2753934,"id":"Q2753934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcfbabcfe6da777a45e5a50fcd3f8e2ac4d10857","datavalue":{"value":{"amount":"+0.8038529753684998","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":"Q1180539$0A1A2612-3EE8-41CC-8B27-F5A267FEC7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1193edc75fe3d39fd6f63cf242bd2a6c1e10ed27","datavalue":{"value":{"entity-type":"item","numeric-id":906406,"id":"Q906406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28af003f95a12d7b605ef1ab354436b3e0e37dc6","datavalue":{"value":{"amount":"+0.8032315969467163","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":"Q1180539$9F9241A5-729E-45E9-A71D-96BE818290A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef1ebcfdc483bf12cc1049dedb07b96a9a8fccd4","datavalue":{"value":{"entity-type":"item","numeric-id":5405889,"id":"Q5405889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a326d2b35050318f69532139cdf0871b6367b556","datavalue":{"value":{"amount":"+0.791932225227356","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":"Q1180539$89D9261E-0266-4EC4-B7CD-086B87876408","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1180539","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1180539"}}}}}