{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T17:02:50Z","timestamp":1771520570651,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T00:00:00Z","timestamp":1648944000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T00:00:00Z","timestamp":1648944000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U21A20513, 61872106, 61832003, 61632010, 61502121"],"award-info":[{"award-number":["U21A20513, 61872106, 61832003, 61632010, 61502121"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Incomplete skyline query is an important operation to filter out pareto-optimal tuples on incomplete data. It is harder than skyline due to intransitivity and cyclic dominance. It is analyzed that the existing algorithms cannot process incomplete skyline on massive data efficiently. This paper proposes a novel table-scan-based TSI algorithm to deal with incomplete skyline on massive data with high efficiency. TSI algorithm solves the issues of intransitivity and cyclic dominance by two separate stages. In stage 1, TSI computes the candidates by a sequential scan on the table. The tuples dominated by others are discarded directly in stage 1. In stage 2, TSI refines the candidates by another sequential scan. The pruning operation is devised in this paper to reduce the execution cost of TSI. By the assistant structures, TSI can skip majority of the tuples in phase 1 without retrieving it actually. The extensive experimental results, which are conducted on synthetic and real-life data sets, show that TSI can compute skyline on massive incomplete data efficiently.<\/jats:p>","DOI":"10.1007\/s41019-022-00183-7","type":"journal-article","created":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T16:02:24Z","timestamp":1649001744000},"page":"102-119","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Skyline Computation on Massive Incomplete Data"],"prefix":"10.1007","volume":"7","author":[{"given":"Jingxuan","family":"He","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5477-9249","authenticated-orcid":false,"given":"Xixian","family":"Han","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,3]]},"reference":[{"key":"183_CR1","unstructured":"Bharuka R, Sreenivasa Kumar P (2013) Finding skylines for incomplete data. In: Proceedings of the 24th australasian database conference - Vol 137, pp 109\u2013117"},{"key":"183_CR2","doi-asserted-by":"crossref","unstructured":"B\u00f6rzs\u00f6nyi S, Kossmann D, Stocker K (2001) The skyline operator. In: Proceedings of the 17th international conference on data engineering, pp 421\u2013430","DOI":"10.1109\/ICDE.2001.914855"},{"key":"183_CR3","doi-asserted-by":"crossref","unstructured":"Chomicki J, Godfrey P, Gryz J, Liang D (2003) Skyline with presorting. In: Proceedings of the 19th international conference on data engineering, pp 717\u2013719","DOI":"10.1109\/ICDE.2003.1260846"},{"key":"183_CR4","doi-asserted-by":"crossref","unstructured":"Godfrey P (2004) Skyline cardinality for relational processing. In: foundations of information and knowledge systems, Third International Symposium, FoIKS 2004:78\u201397","DOI":"10.1007\/978-3-540-24627-5_7"},{"issue":"1","key":"183_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s00778-006-0029-7","volume":"16","author":"Parke Godfrey","year":"2007","unstructured":"Godfrey Parke, Shipley Ryan, Gryz Jarek (2007) Algorithms and analyses for maximal vector computation. VLDB J 16(1):5\u201328","journal-title":"VLDB J"},{"issue":"11","key":"183_CR6","doi-asserted-by":"publisher","first-page":"2521","DOI":"10.1109\/TKDE.2012.203","volume":"25","author":"H Xixian","year":"2013","unstructured":"Xixian H, Jianzhong L, Donghua Y, Jinbao W (2013) Efficient skyline computation on big data. IEEE Trans Knowl Data Eng 25(11):2521\u20132535","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"183_CR7","doi-asserted-by":"crossref","unstructured":"Khalefa ME, Mokbel MF, Levandoski JJ (2008) Skyline query processing for incomplete data. In: Proceedings of the 24th international conference on data engineering, pp 556\u2013565","DOI":"10.1109\/ICDE.2008.4497464"},{"key":"183_CR8","doi-asserted-by":"crossref","unstructured":"Kossmann D, Ramsak F, Rost S (2002) Shooting stars in the sky: an online algorithm for skyline queries. In: Proceedings of the 28th international conference on very large data bases, pp 275\u2013286","DOI":"10.1016\/B978-155860869-6\/50032-9"},{"key":"183_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.is.2013.05.005","volume":"39","author":"Jongwuk Lee","year":"2014","unstructured":"Lee Jongwuk, Hwang Seung-Won (January 2014) Scalable skyline computation using a balanced pivot selection technique. Inf Syst 39:1\u201321","journal-title":"Inf Syst"},{"key":"183_CR10","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.ins.2016.04.048","volume":"361\u2013362","author":"Jongwuk Lee","year":"2016","unstructured":"Lee Jongwuk, Im Hyeonseung, You Gae-won (2016) Optimizing skyline queries over incomplete data. Inf Sci 361\u2013362:14\u201328","journal-title":"Inf Sci"},{"issue":"3","key":"183_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00778-009-0166-x","volume":"19","author":"Ken C Lee","year":"2010","unstructured":"Lee Ken C, Lee Wang-Chien, Zheng Baihua, Li Huajing, Tian Yuan (2010) Z-sky: an efficient skyline query processing framework based on z-order. VLDB J 19(3):333\u2013362","journal-title":"VLDB J"},{"issue":"2","key":"183_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10115-011-0441-1","volume":"32","author":"Cheng Luo","year":"2012","unstructured":"Luo Cheng, Jiang Zhewei, Hou Wen-Chi, He Shan, Zhu Qiang (2012) A sampling approach for skyline query cardinality estimation. Knowl Inf Syst 32(2):281\u2013301","journal-title":"Knowl Inf Syst"},{"issue":"1","key":"183_CR13","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/s11704-016-6195-x","volume":"12","author":"X Miao","year":"2018","unstructured":"Miao X, Yunjun G, Su G, Wanqi L (2018) Incomplete data management: a survey. Front Comput Sci 12(1):4\u201325","journal-title":"Front Comput Sci"},{"issue":"1","key":"183_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1061318.1061320","volume":"30","author":"Dimitris Papadias","year":"2005","unstructured":"Papadias Dimitris, Tao Yufei, Greg Fu, Seeger Bernhard (2005) Progressive skyline computation in database systems. ACM Trans Database Syst 30(1):41\u201382","journal-title":"ACM Trans Database Syst"},{"key":"183_CR15","doi-asserted-by":"crossref","unstructured":"Sheng C, Tao Y(2011) On finding skylines in external memory. In: Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, pp 107\u2013116","DOI":"10.1145\/1989284.1989298"},{"key":"183_CR16","unstructured":"Tan K-L, Eng P-K, Ooi BC (2001) Efficient progressive skyline computation. In: Proceedings of the 27th international conference on very large data bases, pp 301\u2013310"},{"issue":"8","key":"183_CR17","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1109\/TKDE.2007.1051","volume":"19","author":"Yufei Tao","year":"2007","unstructured":"Tao Yufei, Xiao Xiaokui, Pei Jian (2007) Efficient skyline and top-k retrieval in subspaces. IEEE Trans Knowl Data Eng 19(8):1072\u20131088","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"183_CR18","doi-asserted-by":"crossref","unstructured":"Zhang K, Gao H, Han X, Cai Z, Li J (2017) Probabilistic skyline on incomplete data. In: Proceedings of the 2017 ACM on conference on information and knowledge management, pp 427\u2013436","DOI":"10.1145\/3132847.3132930"},{"issue":"7","key":"183_CR19","doi-asserted-by":"publisher","first-page":"1405","DOI":"10.1109\/TKDE.2019.2904967","volume":"32","author":"Kaiqi Zhang","year":"2020","unstructured":"Zhang Kaiqi, Gao Hong, Han Xixian, Cai Zhipeng, Li Jianzhong (2020) Modeling and computing probabilistic skyline on incomplete data. IEEE Trans Knowl Data Eng 32(7):1405\u20131418","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"183_CR20","unstructured":"Shiming Z, Nikos M, Cheung DW (2009) Scalable skyline computation using object-based space partitioning. In: Proceedings of the 2009 ACM SIGMOD international conference on management of data, pp 483\u2013494"},{"issue":"2","key":"183_CR21","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00778-009-0148-z","volume":"19","author":"Z Zhenjie","year":"2010","unstructured":"Zhenjie Z, Hua L, Beng Chin O, Tung AK (2010) Understanding the meaning of a shifted sky: a general framework on extending skyline query. The VLDB J 19(2):181\u2013201","journal-title":"The VLDB J"},{"key":"183_CR22","unstructured":"Zhenjie Z, Yin Y, Ruichu C, Dimitris P, Anthony KHT (2009) Kernel-based skyline cardinality estimation. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 509\u2013522"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00183-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-022-00183-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00183-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T17:10:25Z","timestamp":1652375425000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-022-00183-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["183"],"URL":"https:\/\/doi.org\/10.1007\/s41019-022-00183-7","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,3]]},"assertion":[{"value":"6 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}