{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,6]],"date-time":"2024-07-06T15:22:31Z","timestamp":1720279351466},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>We consider external algorithms for skyline computation without pre-processing. Our goal is to develop an algorithm with a good worst case guarantee while performing well on average. Due to the nature of disks, it is desirable that such algorithms access the input as a stream (even if in multiple passes). Using the tools of randomness, proved to be useful in many applications, we present an efficient multi-pass streaming algorithm, RAND, for skyline computation. As far as we are aware, RAND is the first randomized skyline algorithm in the literature.<\/jats:p>\n          <jats:p>RAND is near-optimal for the streaming model, which we prove via a simple lower bound. Additionally, our algorithm is distributable and can handle partially ordered domains on each attribute. Finally, we demonstrate the robustness of RAND via extensive experiments on both real and synthetic datasets. RAND is comparable to the existing algorithms in average case and additionally tolerant to simple modifications of the data, while other algorithms degrade considerably with such variation.<\/jats:p>","DOI":"10.14778\/1687627.1687638","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"85-96","source":"Crossref","is-referenced-by-count":17,"title":["Randomized multi-pass streaming skyline algorithms"],"prefix":"10.14778","volume":"2","author":[{"given":"Atish","family":"Das Sarma","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Ashwin","family":"Lall","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Jun","family":"Xu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875488"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_16"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1111020"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.60"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066181"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.131"},{"key":"e_1_2_1_8_1","first-page":"595","volume-title":"Intelligent Information Systems","author":"Chomicki J.","year":"2005","unstructured":"J. Chomicki , P. Godfrey , J. Gryz , and D. Liang . Skyline with presorting: Theory and optimizations . In Intelligent Information Systems , pages 595 -- 604 , 2005 . Also appeared in ICDE'03. J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting: Theory and optimizations. In Intelligent Information Systems, pages 595--604, 2005. Also appeared in ICDE'03."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0029-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.70"},{"key":"e_1_2_1_13_1","first-page":"275","volume-title":"VLDB'02","author":"Kossmann D.","year":"2002","unstructured":"D. Kossmann , F. Ramsak , and S. Rost . Shooting stars in the sky: an online algorithm for skyline queries . In VLDB'02 , pages 275 -- 286 . VLDB Endowment , 2002 . D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: an online algorithm for skyline queries. In VLDB'02, pages 275--286. VLDB Endowment, 2002."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.137"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90071-O"},{"key":"e_1_2_1_17_1","first-page":"267","volume-title":"VLDB","author":"Morse M. D.","year":"2007","unstructured":"M. D. Morse , J. M. Patel , and H. V. Jagadish . Efficient skyline computation over low-cardinality domains . In VLDB , pages 267 -- 278 , 2007 . M. D. Morse, J. M. Patel, and H. V. Jagadish. Efficient skyline computation over low-cardinality domains. In VLDB, pages 267--278, 2007."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.42"},{"key":"e_1_2_1_20_1","first-page":"15","volume-title":"VLDB","author":"Pei J.","year":"2007","unstructured":"J. Pei , B. Jiang , X. Lin , and Y. Yuan . Probabilistic skylines on uncertain data . In VLDB , pages 15 -- 26 , 2007 . J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic skylines on uncertain data. In VLDB, pages 15--26, 2007."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.129"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265537"},{"key":"e_1_2_1_24_1","first-page":"51","volume-title":"STACS","author":"Schweikardt N.","year":"2009","unstructured":"N. Schweikardt . Lower bounds for multi-pass processing of multiple data streams . In STACS , pages 51 -- 61 , 2009 . N. Schweikardt. Lower bounds for multi-pass processing of multiple data streams. In STACS, pages 51--61, 2009."},{"key":"e_1_2_1_25_1","first-page":"301","volume-title":"VLDB '01","author":"Tan K.-L.","year":"2001","unstructured":"K.-L. Tan , P.-K. Eng , and B. C. Ooi . Efficient progressive skyline computation . In VLDB '01 , pages 301 -- 310 , San Francisco, CA, USA , 2001 . Morgan Kaufmann Publishers Inc. K.-L. Tan, P.-K. Eng, and B. C. Ooi. Efficient progressive skyline computation. In VLDB '01, pages 301--310, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.48"},{"key":"e_1_2_1_28_1","first-page":"1","volume-title":"In Workshop on Recommendation and Personalization in E-Commerce","author":"Torlone R.","year":"2002","unstructured":"R. Torlone , P. Ciaccia , and U. Romatre . Which are my preferred items . In In Workshop on Recommendation and Personalization in E-Commerce , pages 1 -- 9 , 2002 . R. Torlone, P. Ciaccia, and U. Romatre. Which are my preferred items. In In Workshop on Recommendation and Personalization in E-Commerce, pages 1--9, 2002."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367887"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453967"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.115"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.83"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.142"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:23:50Z","timestamp":1672226630000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687638"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687638","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}