{"entities":{"Q1097702":{"pageid":1108454,"ns":120,"title":"Item:Q1097702","lastrevid":69635220,"modified":"2026-04-13T08:21:23Z","type":"item","id":"Q1097702","labels":{"en":{"language":"en","value":"Jump interpolation search trees and symmetric binary numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035165"}},"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":"Q1097702$65E8212A-0591-4ACB-9BBD-8EE94A0B32D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"192d889acc44a13216b7032aed401f50d9ab59fc","datavalue":{"value":{"text":"Jump interpolation search trees and symmetric binary numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097702$20694FCF-4B46-43A3-8B48-1DDB8D30F97C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6403959e86fc72c6657868077c6a3a6005158a8f","datavalue":{"value":"0635.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097702$225F1C22-9836-49C5-A01F-6325B7BD1E28","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e16a8f2b03e480ba136a7bee419fd66b975641a9","datavalue":{"value":"10.1016/0020-0190(87)90005-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097702$79C4C280-E2D3-4F65-9DFA-6DCC1CBF32DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$3A01026E-9B41-4CE5-8B82-B8538AB29498","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":"Q1097702$AA7511F7-28F9-4DD9-8EFE-ABE07DB79A65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1097702$26710C4F-7DBA-4D9A-9705-681D0BAFECA7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"62edde6c1c1259dda442e594b51468f3e6c6cc48","datavalue":{"value":"Interpolation normally needs more than one interpolation step and, consequently, one has to interpolate repetitively from intermediate positions to the intended goal. At first sight this seems to necessitate that one must be able to leap from every position in a file to most, if not all, others as is indeed the case in arrays where O(N 2) pointers are available implicitly. In files with records of variable sizes, however, it would be unrealistic, by reasons of space complexity, to provide O(N 2) pointers. But, fortunately, for an interpolation step, accuracy is required only relative to the jump size. Loosely speaking, a far reaching interpolation jump may be determined less accurately than a short one, without loss of efficiency. The purpose of this paper is to introduce particular data structures which allow efficient interpolation in this sense and which, being trees, have at the same time an affordable space complexity. These structures represent therefore an interesting class of interpolation search trees, which is quite different from the class of interpolation search trees investigated by \\textit{K. Mehlhorn} and \\textit{A. Tsakalidis} [Lect. Notes Comput. Sci. 194, 424-434 (1985; Zbl 0569.68050)] where the roots have degrees of O(\\(\\sqrt{N})\\), whereas for the trees introduced here it is O(log N).    Moreover the trees studied in this paper have properties which by themselves are worth mentioning. One is that the searching complexity without interpolation is 1/3(log N)(1\\(+o(1))\\) which is better than for most other trees investigated. Furthemore, the trees presented here bear an intimate relation to an interesting class of binary representations of integers with a minimal number of nonzero digits.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097702$35DCE0BC-A5AF-46D6-9A27-1ACC1D8E108B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097702$5D12D714-BDB5-469C-B3A1-779B8692CE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097702$090D6D1D-B40F-42B5-B4EA-7491419CD7F7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e5bb438e2d43f8eb042b304c1f3498881b186dbe","datavalue":{"value":"4035165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097702$102FDE7C-9A78-4CF6-9123-E2F6337C9CEB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a00a041c7fb3e2adcb808f0a828fa00df5a163f5","datavalue":{"value":"number representations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097702$A39B120F-ECBB-48FE-8355-64CF381EDBAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ba602e42c6a230e684e89a4090445f00fc7b858","datavalue":{"value":"data structures for searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097702$30B4CD5B-9051-4E0A-B295-52596080F36A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e20ec6afb054a049240872a3d9dccdc97f09e8","datavalue":{"value":"search algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097702$DC037740-3283-4761-BE60-5AEEE2E4F21F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6f9d23bcbaffdde9377e1aab1d1b760188ae78f","datavalue":{"value":"interpolation search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097702$5A4DB61D-BAAB-425B-9A23-55F66C7814C4","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":"Q1097702$1AEB639D-71EC-4144-85C1-21F463C0A9C7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7db7800f42afeae616ced0e1b4eda1950ec4613e","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90005-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097702$95313D41-5D6A-43CA-9FCD-8D30F49D93C0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b252b21ed47b87235d08a511a7d209e4252abd3f","datavalue":{"value":"W2093980096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097702$68E1B589-FA82-48F0-8CAF-D535F034A99B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e8db212234423bc28895972282f2a07027d743","datavalue":{"value":{"entity-type":"item","numeric-id":5342152,"id":"Q5342152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$5A79B01E-28E8-47CB-974E-D75F7B68BB55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e0aafe4c2a93c70d54cd35396484215be92862e","datavalue":{"value":{"entity-type":"item","numeric-id":1257344,"id":"Q1257344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$FBD82EB1-2DAD-43DC-B6A8-B8FF9AA902AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$40F74303-084F-4083-80BE-35053A11C26D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f25433626f9fdb23ce5f4960207e089b0e524638","datavalue":{"value":{"entity-type":"item","numeric-id":3919074,"id":"Q3919074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$80071C34-2EA6-4D4D-8CAB-9960A2E6E73E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20389d1440f135b3c81232178e37d77b1abe8b46","datavalue":{"value":{"entity-type":"item","numeric-id":3686050,"id":"Q3686050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$FB51C759-7F3E-49F0-891E-6B4D14DCF1F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1570cedada623a9706352d869c0e98026959282","datavalue":{"value":{"entity-type":"item","numeric-id":4157947,"id":"Q4157947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$8D315EB0-73E5-401B-B17B-5277BDECFC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666ba8367cc7645a1d0022e864975b17180aeaf1","datavalue":{"value":{"entity-type":"item","numeric-id":1245570,"id":"Q1245570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097702$D8DF6E42-4148-4518-ADCE-91531D0079F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89df850cb9bd4e943ef5526a38dcaaaecf937b38","datavalue":{"value":{"entity-type":"item","numeric-id":4369769,"id":"Q4369769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9dfbd960c5fa7f44508a456eba4115aeb0c6b60","datavalue":{"value":{"amount":"+0.8459108","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":"Q1097702$FF0A9AC2-DB30-4AF0-91A7-5B5890BFE14A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2762d4da2c6c6d2502919064b0dc0fa23132c8a3","datavalue":{"value":{"entity-type":"item","numeric-id":893318,"id":"Q893318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71f50eee90b3294b7b42fe0769f8debe50be0c12","datavalue":{"value":{"amount":"+0.8427219","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":"Q1097702$A671B9DD-10F4-4893-AFD7-205445FD879C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9fb875f8d357e6694f798e73b27ee9d9dad9f71","datavalue":{"value":{"entity-type":"item","numeric-id":2849342,"id":"Q2849342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71f50eee90b3294b7b42fe0769f8debe50be0c12","datavalue":{"value":{"amount":"+0.8427219","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":"Q1097702$8B760F8B-F3E4-4A4D-9D98-3BB89D8B7A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e295b55b7526ac2f7c783ce25cfad460f5b1eaf2","datavalue":{"value":{"entity-type":"item","numeric-id":3565419,"id":"Q3565419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2edbfc6b69b25696b323017d83f8654ef5c78e3","datavalue":{"value":{"amount":"+0.83812433","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":"Q1097702$1BDE4DA0-E857-48E3-B34A-62CD6066880A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"233fd1ad70593f694fc589ce28a830a7eb1122e0","datavalue":{"value":{"entity-type":"item","numeric-id":5195043,"id":"Q5195043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22df9ce46a32620ed00f56a091af8cf2e28a8604","datavalue":{"value":{"amount":"+0.8354621","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":"Q1097702$D37D63D3-8956-40B9-8FF2-535239288586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce6f511d735f84cb2373d74cecfdc29207a1be79","datavalue":{"value":{"entity-type":"item","numeric-id":4436358,"id":"Q4436358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5163f36430c0eec3fc295911884a3f8d8751f680","datavalue":{"value":{"amount":"+0.8337577","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":"Q1097702$39C9EE43-50C1-44C5-B730-399D5FB131B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4ca8982f54882b2c7ce94bb074091d227eeedd1","datavalue":{"value":{"entity-type":"item","numeric-id":1310968,"id":"Q1310968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fdc3497aa063ed3f095b828875a6b27f1db1097","datavalue":{"value":{"amount":"+0.8336667","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":"Q1097702$4CFB9607-7B6E-40A4-AB50-69BB0AF7AACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90240e568169a3e3270f4be7e89f65bc520c58c3","datavalue":{"value":{"entity-type":"item","numeric-id":1062762,"id":"Q1062762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18bbb752f2816ff4b09ef7f48c995595cdf1ee24","datavalue":{"value":{"amount":"+0.8324413","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":"Q1097702$3848890D-E3D6-4E96-95C7-859BE74A5A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21efa35b6e0b9f10fa087b135d86b996797aa8f1","datavalue":{"value":{"entity-type":"item","numeric-id":557924,"id":"Q557924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1bd3573baafb89d5e492208d4a5f1b6ab289c9f","datavalue":{"value":{"amount":"+0.8315876","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":"Q1097702$4DFD7F1D-F39B-4A83-B98F-F5A1013D7A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d981e45b9675d2690a16d6917a42f3445d45f167","datavalue":{"value":{"entity-type":"item","numeric-id":911247,"id":"Q911247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3db1d15f7b47b846755290416ba955107cffcac1","datavalue":{"value":{"amount":"+0.83027816","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":"Q1097702$B3609064-2674-4D83-914B-25BAB2C77AA3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Jump interpolation search trees and symmetric binary numbers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Jump_interpolation_search_trees_and_symmetric_binary_numbers"}}}}}