{"entities":{"Q1095647":{"pageid":1106399,"ns":120,"title":"Item:Q1095647","lastrevid":69826806,"modified":"2026-04-13T10:36:46Z","type":"item","id":"Q1095647","labels":{"en":{"language":"en","value":"On the dynamization of data structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028881"}},"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":"Q1095647$662835F9-4A08-444B-A44D-3656123C5B8D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fea23db38a84521b4e50810a319e2020d9d62312","datavalue":{"value":{"text":"On the dynamization of data structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095647$90830E6B-0895-4FA6-B2A7-EA8AF4FAD623","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba1d2bebef6fac7ca83eb8f2962dc333aa5932d5","datavalue":{"value":"0632.68025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095647$DA262051-1810-411E-9D4B-9BA77B1637A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec3f5384d667787050d5ef1bfff72d4c2d5d44a4","datavalue":{"value":"10.1007/BF01934693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095647$33EEDCD4-EB91-475D-9562-EA09B94A9F60","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"479e341059cbc6d104a48e7c44c89d6cf761c36f","datavalue":{"value":{"entity-type":"item","numeric-id":586790,"id":"Q586790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095647$CB71EFB7-7B26-4DDE-AD51-5C43F9016EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dfc346dd3ddaf676df84be6326180d484533e88","datavalue":{"value":{"entity-type":"item","numeric-id":751241,"id":"Q751241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095647$21358630-CCA6-49A7-A384-C53BCECFE3B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"962b53bdbe33ef4d98cb55d05a0d4ab0cd458f34","datavalue":{"value":{"entity-type":"item","numeric-id":222939,"id":"Q222939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095647$0611DFA0-AFEE-43B0-834A-CD36EDED24ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095647$89DEA2AF-56A5-4821-80A8-6815A1749253","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1095647$56F4EEFC-AB9E-4467-B52B-0421F517A127","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3909dc1b29853a46250e631cc152793987959790","datavalue":{"value":"We present a simple dynamization method that preserves the query and storage costs of a static data structure and ensures reasonable update costs. In this method, the majority of data elements are maintained in a single data structure, and the updates are handled using ``smaller'' auxiliary data structures. We analyze the query, storage, and amortized update costs for the dynamic version of a static data structure in terms of a function f, such that \\(f(n)<n\\), that bounds the sizes of the auxiliary data structures (where n is the number of elements in the data structure). The conditions on f for minimal (with respect to asymptotic upper bounds) amortized update costs are then obtained.    The proposed method is shown to be particularly suited for the cases where the merging of two data structures is more efficient than building the resultant data structure from scratch. Its effectiveness is illustrated by applying it to a class of data structures that have linear merging cost; this class consists of data structures such as Voronoi diagrams, K-d trees, quadtrees, multiple attribute trees, etc.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$EE65D05F-2379-4FB0-883E-4F826C863E8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095647$B2E3B580-67F6-4E69-BC31-A876E23EB14C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"adb19ba35bc46107ddbbbe86535d1fb7d4364a8c","datavalue":{"value":"4028881","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095647$F37F5167-48DB-4853-B08C-CFF596F051DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"920a54ac56e165d0d214a71d4797f0ed3c0553eb","datavalue":{"value":"amortized insertion and deletion costs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$90B27957-4CA1-45ED-959A-ED87FB7FBC36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7003567b45e7b022142cf2f8f62166b068d72ad3","datavalue":{"value":"query and storage costs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$1840AA23-CDA9-40E3-95AB-0DE7733A43EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4331ef31f4817cae35bbce455911a23a94c1850b","datavalue":{"value":"update costs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$497ED978-9469-4975-A883-E9F82F3720C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c57a76a761299ab25ca140867f4d73db8831009","datavalue":{"value":"merging of two data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$50220786-63A6-4572-ADAE-675BFDCB244B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c9bb8c83eea2f786dd1c606d066d5ce4bda8f05","datavalue":{"value":"merging cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$9D61B19B-2650-4136-A49E-0571E7BC1332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2a942004e7c3ebf174ed889f18fd8e1f8b9b24b","datavalue":{"value":"Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$136EA99E-EE69-4171-8E32-E3E20A7280BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7362796125a0bf9e89de8491f89a650353c58dd","datavalue":{"value":"K- d trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$C21124C5-889A-408C-9138-DF66FBB19EAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"258c977067bd6002ebb9424c27682ab44478cb34","datavalue":{"value":"quadtrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$A1548792-86A9-4DF0-A0EA-32D658F0BC05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af0e30f8d3ea4fb2262051cf67fb947e21ff8725","datavalue":{"value":"multiple attribute trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095647$57BA4119-6A6A-4309-8E11-DC18FF0EC92A","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":"Q1095647$37E1971F-0D4E-455A-952A-81E00745886E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f09abd8d09729dc67252881c661ea2453195bec5","datavalue":{"value":{"entity-type":"item","numeric-id":3219753,"id":"Q3219753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095647$82C32BA3-1532-4719-8582-DFC69C027741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08bbfa2750c080ec67d6b7bc35b58e0a9bc36c96","datavalue":{"value":{"entity-type":"item","numeric-id":3694703,"id":"Q3694703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095647$7B231E70-2D21-4662-B15A-A925FA50712C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c2dadd3475fedd4b1bea03e039af1dc4e5f1845","datavalue":{"value":"https://doi.org/10.1007/bf01934693","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095647$63C5824D-7D18-4E3E-9159-AE0A9B9E7901","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1af5a63547a1b87cc6dbc24c87ac6d2ed2590440","datavalue":{"value":"W2076407808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095647$129BFE9A-ECCE-4E48-B3E0-EB18D99D6D76","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6646b1232764a777064750443230962b00b3c1a6","datavalue":{"value":{"entity-type":"item","numeric-id":3188996,"id":"Q3188996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e245c25269f00e4cbc17f54a1f292aa3bc36296","datavalue":{"value":{"amount":"+0.7862734794616699","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":"Q1095647$04930A99-91FB-48FF-B905-AA14F9B9782E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f95a5c867d46de79128b31f1ee13ced958c8b39","datavalue":{"value":{"entity-type":"item","numeric-id":4210167,"id":"Q4210167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13596b280cf6e7e904a8f58f1618e09905387b20","datavalue":{"value":{"amount":"+0.7801417708396912","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":"Q1095647$0A9E5A2D-6F11-4D7A-8A48-3E0AC2E5E04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18cc201f9e6453f1e51f96293f4e4c81e1862d6c","datavalue":{"value":{"entity-type":"item","numeric-id":5501304,"id":"Q5501304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13596b280cf6e7e904a8f58f1618e09905387b20","datavalue":{"value":{"amount":"+0.7801417708396912","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":"Q1095647$E97E4C37-E98F-49E1-BB7F-2464D6C84663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48e8a050aa145b2ab064e83fa229b57484f4c5e2","datavalue":{"value":{"entity-type":"item","numeric-id":4562277,"id":"Q4562277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d17c64efb8425d2612c73549d5e0aa54367effaf","datavalue":{"value":{"amount":"+0.7769827246665955","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":"Q1095647$FCED9A4B-8434-43AB-B8EF-F7A3F6BCD909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be086542311727e1ea61ad50256b4d1a7c4bf700","datavalue":{"value":{"entity-type":"item","numeric-id":917273,"id":"Q917273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"324528a809a3c5eff3c7bd6981e81ee63f00bc54","datavalue":{"value":{"amount":"+0.7715206742286682","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":"Q1095647$F8359FEC-E247-4544-BD27-CA72106F5EFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the dynamization of data structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_dynamization_of_data_structures"}}}}}