{"entities":{"Q904110":{"pageid":905958,"ns":120,"title":"Item:Q904110","lastrevid":65225442,"modified":"2026-04-12T01:09:31Z","type":"item","id":"Q904110","labels":{"en":{"language":"en","value":"Efficient transformations for Klee's measure problem in the streaming model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6531081"}},"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":"Q904110$03033F8A-70C6-4835-8E1F-0F98D6D0B5D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eae6bc62865cffe875de32ad2a21fe076c390146","datavalue":{"value":{"text":"Efficient transformations for Klee's measure problem in the streaming model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q904110$D5884CF3-B89C-4D9F-B2B8-A6D99397B3B2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d559ce5b7a0a7b13631a9e46ded002de76494a81","datavalue":{"value":"1334.65052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904110$BE6C277F-8A2E-466A-AA0D-D8EA6D2B7A1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93bd2eb5d83463c23eeba6a60f9f833dcf199ef3","datavalue":{"value":{"entity-type":"item","numeric-id":782179,"id":"Q782179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$7B15B246-80F6-4B77-8647-2B540C31AEB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a716a510223e83b925a4ae0e966a305e8b8ade85","datavalue":{"value":{"entity-type":"item","numeric-id":235716,"id":"Q235716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$33ACB261-E023-4012-9874-0E47F860AB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb8112f391e48b28783318307853b48a4655e6fa","datavalue":{"value":{"entity-type":"item","numeric-id":586338,"id":"Q586338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$C7CCE3FF-4526-4484-A88B-812FFE95C5D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"912d466f6e275e0b572214952aa02b7106e789ce","datavalue":{"value":{"entity-type":"item","numeric-id":904109,"id":"Q904109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$ED92FC01-0108-49A9-834E-DDECA7C1CF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"50f4b28ae4b329b8bd751ec7b7d1ed9d0078cff8","datavalue":{"value":{"entity-type":"item","numeric-id":586336,"id":"Q586336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$C45161E6-6D40-4637-9169-CFFD7D65F695","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":"Q904110$7C37295E-F7D9-4553-87EB-38D33612E091","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8c2e70900021c1099dc2c52f195923a82bcef5cb","datavalue":{"value":{"time":"+2016-01-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q904110$2565E47F-E068-440E-AA4F-5EB5BCBF59CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84e2bd6a1bdb53d40546d37b5e5d9a6fd7dc8c1e","datavalue":{"value":"The two-dimensional Klee's measure problem is to compute the area of the union of a given set of axis-aligned rectangles. The authors study a variation of this problem, which they refer to as discrete Klee's measure problem with streaming inputs (KMP-SD). To be more precise, let \\(\\mathbb{Z}_n=\\{ 0,1,\\dots, 2^n-1\\}\\) (for some \\(n\\geq 0\\)) and let \\(Y=\\{ x_0, x_1, \\dots, x_{m-1} \\}\\) be a set of \\(m\\) rectangles in \\(\\mathbb{Z}_n \\times \\mathbb{Z}_n\\). That is, each \\(x_i\\) is a subset of rectangular shape of \\(\\mathbb{Z}_n \\times \\mathbb{Z}_n\\). The KMP-SD asks to determine the quantity  \\[  A_m= \\left | \\bigcup_{i=0}^{m-1} x_i \\right | \\]  for streaming inputs \\(x_i\\).   The authors point out that the optimal algorithmic solution for the classical (non-streaming) problem has a very large workspace requirement, which is too large in the context of streaming applications. While this optimal solution is deterministic and exact, recent work has focused on approximate solutions of the problem reducing workspace and time.   The main contributions of the paper are randomized approximation algorithms for the KMP-SD based on two particular deterministic transformations of the input called side-length-map and aspect-ratio-map. These procedures transform the input rectangles into one-dimensional ranges, such that any so called online range-efficient algorithm can be applied to these ranges to solve the KMP-SD.","type":"string"},"datatype":"string"},"type":"statement","id":"Q904110$D9947781-025C-4A5D-B781-0C1A04534668","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e4265a5412a56b6039db9291cd3f30418db99670","datavalue":{"value":{"entity-type":"item","numeric-id":247401,"id":"Q247401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$9F11137A-3EDB-4CB1-80A3-B3226E7300C0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904110$B6BB9D85-4B1C-4B0E-B4BE-FDB70F1FBF90","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0094c915e2bee3ad64f1823e302277880db21b42","datavalue":{"value":"6531081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904110$4FF49963-9C27-43C3-B6DF-4EB399771D0E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4bce1a97ed52af385dbd33289a04c4897fc6c5d3","datavalue":{"value":"Klee's measure problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q904110$23154DF7-26BD-42B6-B867-54B970D729BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0e621209abfae7c216fbce0dca2074087cc015","datavalue":{"value":"streaming model","type":"string"},"datatype":"string"},"type":"statement","id":"Q904110$8C7CA2F7-3756-4CBF-8372-823A74C59F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22afeb24c6d3572ec740fe790297a5e6501262ee","datavalue":{"value":"bounded aspect ratio rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q904110$537DF833-C011-4B49-8C80-AFA1B5913754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1722a4d9d9d099792b0bf576120a0a31d3460e42","datavalue":{"value":"bounded side length rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q904110$6FB2B9D4-846C-4DE0-90F5-4E5661CD59A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01519ccd061de77e4f96d99f701aae2e4e9cc2c","datavalue":{"value":"randomized approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q904110$6877A51F-0428-420A-AF97-085528B60B77","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":"Q904110$0C5D4926-ACD0-462F-BBC0-12A31403551A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d78e1bc710fd259fc588b4d4401857de483fd823","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2015.06.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q904110$7228A513-4E2A-4AA1-87D0-7B100D4E2544","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d6874f29b09ece7b9bbf3e90a9e52e1387c04a7e","datavalue":{"value":"W1114040662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904110$C1BC435F-457A-42BA-B635-786752AE0777","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f58b70e7e930f658a2fb005dbcf51ac805c5b1b","datavalue":{"value":{"entity-type":"item","numeric-id":3405831,"id":"Q3405831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$73A6FAF7-90D9-4FAD-BF49-6B1A0FDDD08C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfdc76fb3562ef6f4c9173dc95ee70d4835105e7","datavalue":{"value":{"entity-type":"item","numeric-id":4157950,"id":"Q4157950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$ECBFBE31-049B-4A5F-A7B3-10AA36B60BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8bd53686632a085e5393ba87c23c66889642b58","datavalue":{"value":{"entity-type":"item","numeric-id":4247679,"id":"Q4247679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$4327E5F0-B205-4EE8-849E-DB9B68A2803A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c86612b0f079f2bb071cd64fbd63ce96b66b9bf","datavalue":{"value":{"entity-type":"item","numeric-id":1037647,"id":"Q1037647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$32680F8C-B12C-436E-88BB-B4366134FB17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b33616ecbe2502fcc4cbfd0ae6ab6a777e1280b6","datavalue":{"value":{"entity-type":"item","numeric-id":845997,"id":"Q845997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$EDAE3373-C8D5-462F-A485-B9732B7B5DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7faae9af4da6c660435a45fe90739b231673546d","datavalue":{"value":{"entity-type":"item","numeric-id":3985807,"id":"Q3985807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$8CB9CD09-B9BD-4486-995A-6A9B7A345FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e0ad7d3fdc5428b5e67b4998be53d6d9981292d","datavalue":{"value":{"entity-type":"item","numeric-id":3948587,"id":"Q3948587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$6C33E02F-260D-4CC8-833D-B818E90D9F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13334f0e8b2188c06f8d73bc34722e35844ddcb3","datavalue":{"value":{"entity-type":"item","numeric-id":4228450,"id":"Q4228450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$FD238F28-67B3-456D-809A-CFB237A42B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f10375803d572bed863df5a6c490c6a03af36df","datavalue":{"value":{"entity-type":"item","numeric-id":5386204,"id":"Q5386204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$20303CFE-544E-41F6-BA47-85107BD8796C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2db425e522ed602fb3c2785ea7aa7e6f265090fb","datavalue":{"value":{"entity-type":"item","numeric-id":982950,"id":"Q982950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$59FDC39D-3F83-4C4C-B93E-FC965AAB538D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b278433ff640c9dcd41673af32fcd942fe478f03","datavalue":{"value":{"entity-type":"item","numeric-id":1007249,"id":"Q1007249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$A7384381-5BB1-4B34-A44A-31018E01E353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ec91f509c2e0906fc3fb4c9abd4cf552db827ae","datavalue":{"value":{"entity-type":"item","numeric-id":4828992,"id":"Q4828992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$CB68D895-9157-48D6-B2B3-D5F5BB8E90D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$C7E2A8C0-6D1E-4D20-B05C-2C74F02C3FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083ca8efd68a71cc74bf742e98ea704129c1b8fa","datavalue":{"value":{"entity-type":"item","numeric-id":419375,"id":"Q419375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$8BEEB2EA-1CFF-474D-A1E5-8197AB7C9D7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"154b9fa85e5544bb91e06976996916e885c3984c","datavalue":{"value":{"entity-type":"item","numeric-id":4682197,"id":"Q4682197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904110$E2E0906C-FA5B-42FB-A77E-E4E4D67615F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4c9507ab66ae724ef8f8997bce26ce2f67a7e90","datavalue":{"value":"10.1016/J.COMGEO.2015.06.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904110$81796B8F-3958-4E59-85EA-D931FCEFA23D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6714fa67ba2323fcc957339b7ec80fb07732c19e","datavalue":{"value":{"entity-type":"item","numeric-id":845997,"id":"Q845997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfc6ab6e0b9b504ed904c5b3995376f96216204d","datavalue":{"value":{"amount":"+0.787228524684906","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":"Q904110$DB17612C-0795-414A-97B7-D5EEA048120A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f7829842e6d3461ca94df0c63f1771d111a8bf1","datavalue":{"value":{"entity-type":"item","numeric-id":1037647,"id":"Q1037647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5b9c8629a0b1b831eefbbc7fa61d915bc5ec35c","datavalue":{"value":{"amount":"+0.7497547268867493","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":"Q904110$03FA7FA7-B890-4ED7-BBB4-728F7087B357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9b4aa38ad76234b03ed0dd4229502e15223ffaf","datavalue":{"value":{"entity-type":"item","numeric-id":2849910,"id":"Q2849910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1d1c44808da1038fd446902f64a276ad1d76b05","datavalue":{"value":{"amount":"+0.7396008372306824","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":"Q904110$113ADEC6-3563-4FE8-A250-463D92D21AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75a0cdfc3942bc35be672791853e619fa674c29a","datavalue":{"value":{"entity-type":"item","numeric-id":4247679,"id":"Q4247679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e24e8f6d6187f79d8ce9a42e77a47b8b90848db2","datavalue":{"value":{"amount":"+0.7390377521514893","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":"Q904110$2C345201-D823-42A7-AAE3-82847F2A705E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"410ab0ff3c141b6c6ca8f0f9c7caac3b87a613f6","datavalue":{"value":{"entity-type":"item","numeric-id":3985807,"id":"Q3985807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e24e8f6d6187f79d8ce9a42e77a47b8b90848db2","datavalue":{"value":{"amount":"+0.7390377521514893","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":"Q904110$5795FAA2-849F-461E-BDD1-88FF0C1E24CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient transformations for Klee's measure problem in the streaming model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_transformations_for_Klee%27s_measure_problem_in_the_streaming_model"}}}}}