{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:49:48Z","timestamp":1759682988857,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T00:00:00Z","timestamp":1335830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0347600"],"award-info":[{"award-number":["IIS-0347600"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,5]]},"abstract":"<jats:p>The skyline query can help identify the \u201cbest\u201d objects in a multi-attribute dataset. During the past decade, this query has received considerable attention in the database research community. Most research focused on computing the \u201cskyline\u201d of a dataset, or the set of \u201cskyline objects\u201d that are not dominated by any other object. Such algorithms are not appropriate in an online system, which should respond in real time to skyline query requests with arbitrary subsets of the attributes (also called subspaces). To guarantee real-time response, an online system should precompute the skylines for all subspaces, and look up a skyline upon query. Unfortunately, because the number of subspaces is exponential to the number of attributes, such pre computation has very expensive storage cost and update cost. We propose the Compressed SkyCube (CSC) that is much more compact, yet can still return the skyline of any subspace without consulting the base table. The CSC therefore combines the advantage of precomputation in that it can respond to queries in real time, and the advantage of no-precomputation in that it has efficient space cost and update cost. This article presents the CSC data structures, the CSC query algorithm, the CSC update algorithm, and the CSC initial computation scheme. A solution to extend to high-dimensional data is also proposed.<\/jats:p>","DOI":"10.1145\/2188349.2188357","type":"journal-article","created":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T15:51:28Z","timestamp":1338565888000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Online subspace skyline query processing using the compressed skycube"],"prefix":"10.1145","volume":"37","author":[{"given":"Tian","family":"Xia","sequence":"first","affiliation":[{"name":"Teradata Corporation, El Segundo, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donghui","family":"Zhang","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab, Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zheng","family":"Fang","sequence":"additional","affiliation":[{"name":"University of Massachusetts Lowell, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cindy","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Massachusetts Lowell, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Massachusetts Lowell, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6,4]]},"reference":[{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 506--521","author":"Agarwal S.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). 256--273","author":"Balke W.-T.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1111020"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 179--187","author":"Bentley J. L.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322095"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 421--430","author":"B\u00f6rzs\u00f6nyi S.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90156-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066181"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142530"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_30"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.131"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/645340.650249"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 717--816","author":"Chomicki J.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183675"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03417-6_24"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24627-5_7"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 229--240","author":"Godfrey P.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183676"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427865_10"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.142"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.185"},{"volume-title":"Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery (PKDD). 255--266","author":"Jin W.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 249--260","author":"Jin W.","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 275--286","author":"Kossmann D.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 185--196","author":"Lee J.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.137"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Lin X.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90071-O"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.56"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872814"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Pei J.","key":"e_1_2_1_33_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 253--264","author":"Pei J.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189774"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920948"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1093"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","author":"Sharifzadeh M.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989298"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90042-7"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 301--310","author":"Tan K.-L.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.48"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.149"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453967"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367894"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_10"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142529"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 241--252","author":"Yuan Y.","key":"e_1_2_1_49_1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559897"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559899"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2188349.2188357","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2188349.2188357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:11Z","timestamp":1750236551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2188349.2188357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["10.1145\/2188349.2188357"],"URL":"https:\/\/doi.org\/10.1145\/2188349.2188357","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,5]]},"assertion":[{"value":"2010-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}