{"entities":{"Q579942":{"pageid":581709,"ns":120,"title":"Item:Q579942","lastrevid":62944878,"modified":"2026-04-11T09:09:28Z","type":"item","id":"Q579942","labels":{"en":{"language":"en","value":"An implicit data structure supporting insertion, deletion, and search in \\(O(\\log ^ 2\\,n)\\) time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016202"}},"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":"Q579942$0911EE91-1630-419D-8C87-0C2923C5B577","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2daba175c36872d742d331b6a25583dc7c5a70c","datavalue":{"value":{"text":"An implicit data structure supporting insertion, deletion, and search in \\(O(\\log ^ 2\\,n)\\) time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579942$7F7A1A14-B5C9-4DA8-9C9E-8548BDEC5426","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83be8b0131455059a6bc1515c451fbb1391180d4","datavalue":{"value":"0625.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579942$EE19181B-3880-4965-B687-527DE5C74333","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50527249b9074d103bb078c017c65eac8336f96d","datavalue":{"value":"10.1016/0022-0000(86)90043-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579942$8078D5F0-C8DE-43FB-BDE8-3199108F60F1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f4dc151011ded6306ac4932c4d08c776e790b87","datavalue":{"value":{"entity-type":"item","numeric-id":287449,"id":"Q287449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$BEDE9610-336D-404F-BB7F-BF69485FF453","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$466145C0-D79E-4997-82B4-69962FF97469","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q579942$18B5B9A3-45C2-4D69-B29E-65EB3810B0BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b6eb42c7b49a89bf4a52d941d485665b67989e78","datavalue":{"value":"We introduce a data structure that requires only one pointer for every k data values and supports searches in O(log n) time and insertions and deletions in \\(O(k+\\log n)\\) time. By choosing k to be O(log n), pointers can be encoded into the relative order of data values and this technique can be used to support insert, delete and search in \\(O(\\log^ 2 n)\\) time while using only the storage needed for the data.","type":"string"},"datatype":"string"},"type":"statement","id":"Q579942$BF5D13F1-B4C2-4CCA-ADAF-933FD6D7873D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579942$83AED915-2AAA-4F6B-A810-06E0158D3613","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1473e0df139c2f130a679fc8356b7cbd283c388e","datavalue":{"value":"4016202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579942$A237B1B9-F693-434C-9ACB-0EFFE9B577D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q579942$D3F5660A-0C43-46D5-BD0F-BC73D6FDF9BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d77162588362d38acc5567d3255fa45e1f8e7a25","datavalue":{"value":"insertions","type":"string"},"datatype":"string"},"type":"statement","id":"Q579942$90D32BF5-2E8B-43C5-9308-B869385DB634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44d130647d012cc5557f5b67dcc52c6f8ab397b3","datavalue":{"value":"deletions","type":"string"},"datatype":"string"},"type":"statement","id":"Q579942$D017A5C8-5C5E-4DE4-9D28-D2D80943C8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df4a9fa42a823ec549977451ee26e4eccb17d524","datavalue":{"value":"pointers","type":"string"},"datatype":"string"},"type":"statement","id":"Q579942$803A43E5-E38C-4E71-920A-FEA3F60E4190","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"40511068b347a60aa196b665fa4c4acc6f9d4e19","datavalue":{"value":{"entity-type":"item","numeric-id":46612,"id":"Q46612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$502F7D6B-12FC-4EC2-AC46-8AC5328D4E78","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":"Q579942$C8F39E11-5208-4E2F-B6B5-8FEED92D006B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea0e8da99cad994c3d516d02c058bdfc5056e221","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90043-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q579942$4A776D5B-F36F-412E-9A5A-71F3537C1E78","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fe9d59a680fe1400f9ca025b21456b587d9ec324","datavalue":{"value":"W2156305878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579942$C66B7566-371C-4DDE-A221-3013583277DF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2a49dc99efbc1380fe41a78c12c4b153d4dd458","datavalue":{"value":{"entity-type":"item","numeric-id":3326852,"id":"Q3326852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$D1CBEBDE-92AD-4C30-9B61-9277066B825A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5a450d4a6d699c0669f00fab6d982ad381bef26","datavalue":{"value":{"entity-type":"item","numeric-id":792764,"id":"Q792764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$E894E198-C322-4778-9D2E-F81BFBC729D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c8a659f7245b4a85efedb83f71c0a5e053efe1","datavalue":{"value":{"entity-type":"item","numeric-id":3962473,"id":"Q3962473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$191E3877-6ED9-4171-90E3-D96CE7EAB889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2572c3c5ec8573e21946b21819751c664a1a444","datavalue":{"value":{"entity-type":"item","numeric-id":4656634,"id":"Q4656634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$8CC9E7CE-D8A3-468B-A788-5B56FF91DD8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c4b432264b1d95c77c217a25bbd889f27e5418d","datavalue":{"value":{"entity-type":"item","numeric-id":1146004,"id":"Q1146004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$6EDF1C96-3BB3-439F-A248-084BF9381D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bf7b697634edfdfe302eab3cb935ce81a2b61b5","datavalue":{"value":{"entity-type":"item","numeric-id":3673089,"id":"Q3673089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579942$85A894E0-F23A-4DF6-B95C-8A519719736E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27db14a94bbdd4f99b8b0c3f9d3c66424d1be85b","datavalue":{"value":{"entity-type":"item","numeric-id":3753486,"id":"Q3753486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aec8c6dac66884e6f303d56b1b7790d9564220fe","datavalue":{"value":{"amount":"+0.8799965381622314","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":"Q579942$F5CE3071-77DB-412D-81A0-D1F364D2DF27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6055ada10f353e43e3f3168e68289b3f9275dfe","datavalue":{"value":{"entity-type":"item","numeric-id":4471357,"id":"Q4471357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"261b1d9b7a98856449aea94c40082106072a60ce","datavalue":{"value":{"amount":"+0.8667232394218445","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":"Q579942$DC3318EE-C504-4D3D-B440-F89F746CAA8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbcb9ecaec154ed188405d47d8d50b5aa4330c34","datavalue":{"value":{"entity-type":"item","numeric-id":1186547,"id":"Q1186547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13e47080d04091c95374a89e1e15fe894a7a7487","datavalue":{"value":{"amount":"+0.8126837611198425","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":"Q579942$84506D3E-5F33-417E-90EF-92C272610365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a20a982f3b567ce273da249f19d2d0a1d018690","datavalue":{"value":{"entity-type":"item","numeric-id":5900747,"id":"Q5900747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"547b2436c20f638c433f6b1b3ae873db18007847","datavalue":{"value":{"amount":"+0.8125677108764648","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":"Q579942$9DE75D39-5DD3-4B3D-9D9F-E38B0345672D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca3ebfd7e40581bc10de5412d9f6f5fc68517c5d","datavalue":{"value":{"entity-type":"item","numeric-id":598254,"id":"Q598254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"272cc6c026baba17b98af72dae99c3d5c1f5499b","datavalue":{"value":{"amount":"+0.7963842749595642","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":"Q579942$36BDDF02-B2A9-40CE-A120-8D44E0EF004E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An implicit data structure supporting insertion, deletion, and search in \\(O(\\log ^ 2\\,n)\\) time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_implicit_data_structure_supporting_insertion,_deletion,_and_search_in_%5C(O(%5Clog_%5E_2%5C,n)%5C)_time"}}}}}