{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:41Z","timestamp":1740120221343,"version":"3.37.3"},"reference-count":30,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2019,12,1]]},"abstract":"<jats:p> We study data structures to answer window queries using stochastic input sequences. The first problem is the most likely maximal point in a query window: Let [Formula: see text] be constants, with [Formula: see text]. Let [Formula: see text] be a set of [Formula: see text] points in [Formula: see text], for some fixed [Formula: see text]. For [Formula: see text], each point in [Formula: see text] is associated with a probability [Formula: see text] of existence. A point [Formula: see text] in [Formula: see text] is on the maximal layer of [Formula: see text] if there is no other point [Formula: see text] in [Formula: see text] such that [Formula: see text]. Consider a random subset of [Formula: see text] obtained by including, for [Formula: see text], each point of [Formula: see text] independently with probability [Formula: see text]. For a query interval [Formula: see text], with [Formula: see text], we report the point in [Formula: see text] that has the highest probability to be on the maximal layer of [Formula: see text] in [Formula: see text] time using [Formula: see text] space. We solve a special problem as follows. A sequence [Formula: see text] of [Formula: see text] points in [Formula: see text] is given ([Formula: see text]), where each point [Formula: see text] has a probability [Formula: see text] of existence associated with it. Given a query interval [Formula: see text] and an integer [Formula: see text] with [Formula: see text], we report the probability of [Formula: see text] to be on the maximal layer of [Formula: see text] in [Formula: see text] time using [Formula: see text] space. <\/jats:p><jats:p> The second problem we consider is the most likely common element problem. Let [Formula: see text] be the universe. Let [Formula: see text] be a sequence of random subsets of [Formula: see text] such that for [Formula: see text] and [Formula: see text], element [Formula: see text] is added to [Formula: see text] with probability [Formula: see text] (independently of other choices). Let [Formula: see text] be a fixed real number with [Formula: see text]. For query indices [Formula: see text], [Formula: see text], [Formula: see text] and [Formula: see text], with [Formula: see text] and [Formula: see text], we decide whether there exists an element [Formula: see text] with [Formula: see text] such that [Formula: see text] in [Formula: see text] time using [Formula: see text] space and report these elements in [Formula: see text] time, where [Formula: see text] is the size of the output. <\/jats:p>","DOI":"10.1142\/s0218195919500092","type":"journal-article","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T06:07:05Z","timestamp":1588745225000},"page":"269-287","source":"Crossref","is-referenced-by-count":0,"title":["The Most Likely Object to be Seen Through a Window"],"prefix":"10.1142","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0154-5013","authenticated-orcid":false,"given":"Paz","family":"Carmi","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3468-217X","authenticated-orcid":false,"given":"Farah","family":"Chanchary","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, ON, K1S 5B6, Canada"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, ON, K1S 5B6, Canada"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, ON, K1S 5B6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2020,5,6]]},"reference":[{"key":"S0218195919500092BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462388"},{"key":"S0218195919500092BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9382-7"},{"key":"S0218195919500092BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559816"},{"issue":"2","key":"S0218195919500092BIB004","first-page":"340","volume":"79","author":"Agarwal P. K.","year":"2017","journal-title":"Convex hulls under uncertainty."},{"key":"S0218195919500092BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.09.006"},{"key":"S0218195919500092BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6309-2"},{"key":"S0218195919500092BIB007","first-page":"78","volume-title":"Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)","author":"Agrawal A.","year":"2017"},{"volume-title":"Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG2014)","year":"2014","author":"Bannister M. J.","key":"S0218195919500092BIB008"},{"key":"S0218195919500092BIB009","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.61"},{"key":"S0218195919500092BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"S0218195919500092BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"S0218195919500092BIB012","first-page":"240","volume-title":"31st International Symposium on Computational Geometry (SoCG 2015)","volume":"34","author":"Bokal D.","year":"2015"},{"key":"S0218195919500092BIB013","first-page":"28:1","volume-title":"32nd International Symposium on Computational Geometry (SoCG 2016)","volume":"51","author":"Chan T. M.","year":"2016"},{"key":"S0218195919500092BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30139-6_16"},{"key":"S0218195919500092BIB015","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00489"},{"key":"S0218195919500092BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53007-9_8"},{"key":"S0218195919500092BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-74180-2_17"},{"key":"S0218195919500092BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/3311"},{"volume-title":"Uncertainty in remote sensing and GIS","year":"2002","author":"Goodchild M. F.","key":"S0218195919500092BIB019"},{"key":"S0218195919500092BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.016"},{"key":"S0218195919500092BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998206"},{"key":"S0218195919500092BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.10.010"},{"key":"S0218195919500092BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.005"},{"key":"S0218195919500092BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.12.007"},{"volume-title":"Stochastic Simulation in Physics","year":"2001","author":"MacKeown P. K.","key":"S0218195919500092BIB026"},{"key":"S0218195919500092BIB027","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"S0218195919500092BIB028","series-title":"Texts in Statistical Science Series","volume-title":"Principles of Uncertainty","author":"Mena R. H.","year":"2011"},{"key":"S0218195919500092BIB029","first-page":"15","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases","author":"Pei J.","year":"2007"},{"key":"S0218195919500092BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_67"},{"key":"S0218195919500092BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0031-7"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195919500092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T06:07:17Z","timestamp":1588745237000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195919500092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,1]]},"references-count":30,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S0218195919500092"],"URL":"https:\/\/doi.org\/10.1142\/s0218195919500092","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2019,12,1]]}}}