{"entities":{"Q390107":{"pageid":391874,"ns":120,"title":"Item:Q390107","lastrevid":77643914,"modified":"2026-05-06T09:44:02Z","type":"item","id":"Q390107","labels":{"en":{"language":"en","value":"Sequential dependency computation via geometric data structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6249139"}},"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":"Q390107$B8870588-DC34-419A-BF4A-764ADB87CE23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1fa03d37b332b4b9f06d8152028b50e12c95bd8","datavalue":{"value":{"text":"Sequential dependency computation via geometric data structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q390107$11FAFC88-0575-4A17-993C-0C4D531C5599","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9debdae97ae9cedb8a0cdb3ef717579d6a54f715","datavalue":{"value":"1295.65017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$851C1ADE-F328-4C57-91E5-A168121E55E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$6C6E7172-F426-45B9-86B6-29663EDF93B9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4faea9ea96f54af129daa2771004ab771cecfe4f","datavalue":{"value":{"time":"+2014-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q390107$1CDE5E7F-2A92-4CEC-A384-EB2039A94CFC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c9684a93e5f98988685744c9cbf253435c411cf8","datavalue":{"value":{"entity-type":"item","numeric-id":510384,"id":"Q510384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$AAC43B1A-17DF-4B6D-995F-B5321DEAE6EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$37989DF9-CA47-4307-B428-F129A21D36DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$F79721F6-FC13-44CC-8C93-5BCAD7B96781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a10afe9a405e1bf11f61b5935389dcc675bc6610","datavalue":{"value":"65Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$751B1B7F-140C-46EB-97B5-2C5B1EA35520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e53f88ab24e1da510f2fd88cf614c6c4cc09d513","datavalue":{"value":"62-07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$ED2873C2-C480-4E71-BF23-9986A26CA1BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd617f9d0fec58a219ee24586cc73ce6577bed23","datavalue":{"value":"65C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$46B2EFDF-887A-4D29-BC23-BCC352259EBD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1495fc401dbc1d52ae86e3e71ae13343bd56ec74","datavalue":{"value":"6249139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$85B9AA07-C2EB-466E-81D2-11A57F25BF5E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q390107$00B95D0B-5792-43D4-BB8E-67FEC4B94379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58b187afe44b62e3e6d298a06b128d676f926241","datavalue":{"value":"geometric data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q390107$FC6CC5A7-C351-4E02-B437-0AA2A1C89566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6e2a8d36436036611a0f22458e052ece65ed489","datavalue":{"value":"gap dependency","type":"string"},"datatype":"string"},"type":"statement","id":"Q390107$77EF3A66-95CC-4FE8-ADEC-BDFA83796F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b375891bb49aa0689200493d0eef4f137028a63f","datavalue":{"value":"recurrence relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q390107$BE8ECBB7-B3B8-48A8-9765-221D7F2E1210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q390107$D9EA3888-2B97-48DB-8141-98E1DDC28178","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4911ab413899ccff5e4c11996ce5c27900b98070","datavalue":{"value":{"entity-type":"item","numeric-id":247838,"id":"Q247838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$75FE9D43-5E5E-42FF-BDC3-73D3B924ECFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad2e86f5f3dec5ee08f5279d9401b2d10e41bcfa","datavalue":{"value":{"entity-type":"item","numeric-id":1117702,"id":"Q1117702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$3C75094A-ABB3-4249-BAF0-FF0F83E004DB","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":"Q390107$6EE11A3B-9CB2-4CE0-9779-302B4081F7D0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"383f909a4a33a7a0718194ff0e3b5a354cf9635e","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2013.08.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q390107$8E028824-61BC-4363-9933-D7393F03957A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"771b9bcab89949f6cbaad4e88d1842ed988093a3","datavalue":{"value":"W2015984909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$7385B0F1-098F-495E-954E-BB6F92E3FB23","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6462e8c5c0aea01f2a594c3439645ce7174b0eb2","datavalue":{"value":{"entity-type":"item","numeric-id":4947407,"id":"Q4947407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$9E1119CD-DBDC-4B6D-8493-F87EF60DE73C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c60834422b0e6530340f43a2157202d8404a02fb","datavalue":{"value":{"entity-type":"item","numeric-id":908708,"id":"Q908708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$D30E5CE1-77E4-4220-91FC-823469973E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8081c943c6d3079b757e0bce0d00c430b2388882","datavalue":{"value":{"entity-type":"item","numeric-id":4943856,"id":"Q4943856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$E91F4FEE-DD77-49FD-8C8A-D84980D49B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca1f3f05745aa62eb383c9b56e848bc43e251cf8","datavalue":{"value":{"entity-type":"item","numeric-id":5404401,"id":"Q5404401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390107$E9FD9369-6CC7-44F9-9B76-C25545D66E00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25d080b2a6d55d02ba3128f41cb25c66f1ddfd7f","datavalue":{"value":"10.1016/J.COMGEO.2013.08.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390107$7C8B447F-4A8F-4400-A81B-4B5458979448","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3100e605f8cfab051178a67f8ff52879df5f1395","datavalue":{"value":"Let \\(G_1,G_2\\) be nonnegative integers, not both zero, with \\(G_1\\leq G_2\\). A finite nonempty sequence of integers is said to be valid if the difference between successive terms is between \\(G_1\\) and \\(G_2\\) inclusive. In the gap dependency problem one has to find the minimum number of insertions and deletions required to convert a given sequence of integers \\(S=\\langle a_1,\\dots,a_n\\rangle\\) into a valid sequence. This problem has applications in obtaining statistics about a database, and is known to have a solution that runs in \\(O(\\tfrac{G_2}{G_2-G_1}\\,n\\log{n})\\) time.NEWLINENEWLINEThe problem can be reduced to finding, for each \\(1\\leq i\\leq n\\), the minimum number \\(T(i)\\) of insertions and deletions needed to transform the subsequence \\(\\langle a_1,\\dots,a_i\\rangle\\) into a valid sequence ending in \\(a_i\\). These quantities may be computed from the recurrence relation NEWLINE\\[NEWLINET(i)=\\min\\bigl\\{i-1, \\min_{j<i,a_j<a_i}[T(j)+i-2-j+\\mathrm{dcost}(a_i-a-j)] \\bigr\\} NEWLINE\\]NEWLINE Here \\(\\mathrm{dcost}(k)\\) is the smallest number of insertions that are needed to make the sequence \\(\\langle 0\\rangle\\) valid, and can be computed in constant time. The authors present a novel way in which the computation of the minima over \\(j<i\\) and \\(a_j<a_i\\) in the above recurrence relation for \\(T(i)\\) may be transformed into an orthogonal range search. With a judicious choice of data structure, this leads to an algorithm that solves the gap dependency problem in \\(O(n\\log{n}\\log\\log{n})\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q390107$E36765C0-FB45-47C0-927F-3C3EFAE64B9B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a26418a7e31bada4ab5e077cc97d0fa8db9b51ee","datavalue":{"value":{"entity-type":"item","numeric-id":4629964,"id":"Q4629964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78efc661d7b7027cc08aee60481c77f16c7082b4","datavalue":{"value":{"amount":"+0.6540581583976746","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":"Q390107$8C39EBF1-8EE1-47CE-A11B-A9101AFD382F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe62d3c16fa219ef98d6ca2cedf19aae304d362f","datavalue":{"value":{"entity-type":"item","numeric-id":3304143,"id":"Q3304143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd4bf260ac5db4104015047a406b27a454ce34bc","datavalue":{"value":{"amount":"+0.6484515070915222","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":"Q390107$C82C4B53-3B32-4605-8539-3EB4B0E25239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b699cfb04deb67652187aa6aca0149d1439af6cd","datavalue":{"value":{"entity-type":"item","numeric-id":1987516,"id":"Q1987516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"216d3405e60f879733846d18b5b6100cb0ee4e33","datavalue":{"value":{"amount":"+0.6465943455696106","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":"Q390107$D7E89D11-24CF-4A6F-8389-8C3EC4D70C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a07a9b0d921aa7a586f72ad44840c7b11b1bd67b","datavalue":{"value":{"entity-type":"item","numeric-id":5321704,"id":"Q5321704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41922172a34029632df26b24cee81887c797ee9d","datavalue":{"value":{"amount":"+0.6458417773246765","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":"Q390107$0AEEF195-BC13-4714-845A-67AC19D15224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"308c5827d8b0a82e4cd3635e38fcacdf151a7e8b","datavalue":{"value":{"entity-type":"item","numeric-id":3173480,"id":"Q3173480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1561ecb5c7982c7938db3ab657adbc853a9bbcbc","datavalue":{"value":{"amount":"+0.6386037468910217","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":"Q390107$5D8FC11E-C18B-48A6-8589-80E01D9E8235","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sequential dependency computation via geometric data structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sequential_dependency_computation_via_geometric_data_structures"}}}}}