{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:16:47Z","timestamp":1750306607861,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"\u201cRanKloud: Data Partitioning and Resource Allocation Strategies for Scalable Multimedia and Social Media Analysis\u201d"},{"name":"NSF","award":["1116394"],"award-info":[{"award-number":["1116394"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,6,30]]},"abstract":"<jats:p>\n            Efficient processing of skyline queries has been an area of growing interest. Many of the earlier skyline techniques assumed that the skyline query is applied to a single data table. Naturally, these algorithms were not suitable for many applications in which the skyline query may involve attributes belonging to multiple data sources. In other words, if the data used in the skyline query are stored in multiple tables, then\n            <jats:italic>join<\/jats:italic>\n            operations would be required before the skyline can be searched. The task of computing skylines on multiple data sources has been coined as the\n            <jats:italic>skyline-join<\/jats:italic>\n            problem and various\n            <jats:italic>skyline-join<\/jats:italic>\n            algorithms have been proposed. However, the current proposals suffer several drawbacks: they often need to scan the input tables exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. In this article, we aim to address these shortcomings by proposing two novel skyline-join algorithms, namely\n            <jats:italic>skyline-sensitive join<\/jats:italic>\n            (S\n            <jats:sup>2<\/jats:sup>\n            J) and\n            <jats:italic>symmetric skyline-sensitive join<\/jats:italic>\n            (S\n            <jats:sup>3<\/jats:sup>\n            J), to process skyline queries over two data sources. Our approaches compute the results using a novel\n            <jats:italic>layer\/region pruning<\/jats:italic>\n            technique (\n            <jats:italic>LR-pruning<\/jats:italic>\n            ) that prunes the join space in blocks as opposed to individual data points, thereby avoiding excessive pairwise point-to-point dominance checks. Furthermore, the S\n            <jats:sup>3<\/jats:sup>\n            J algorithm utilizes an early stopping condition in order to successfully compute the skyline results by accessing only a subset of the input tables. In addition to S\n            <jats:sup>2<\/jats:sup>\n            J and S\n            <jats:sup>3<\/jats:sup>\n            J, we also propose the S\n            <jats:sup>2<\/jats:sup>\n            J-M and S\n            <jats:sup>3<\/jats:sup>\n            J-M algorithms. These algorithms extend S\n            <jats:sup>2<\/jats:sup>\n            J's and S\n            <jats:sup>3<\/jats:sup>\n            J's two-way skyline-join ability to efficiently process skyline-join queries over more than two data sources. S\n            <jats:sup>2<\/jats:sup>\n            J-M and S\n            <jats:sup>3<\/jats:sup>\n            J-M leverage the extended concept of\n            <jats:italic>LR-pruning<\/jats:italic>\n            , called\n            <jats:italic>M<\/jats:italic>\n            -way\n            <jats:italic>LR-pruning<\/jats:italic>\n            , to compute multi-way skyline-joins in which more than two data sources are integrated during skyline processing. We report extensive experimental results that confirm the advantages of the proposed algorithms over state-of-the-art skyline-join techniques.\n          <\/jats:p>","DOI":"10.1145\/2699483","type":"journal-article","created":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T15:45:37Z","timestamp":1435679137000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Processing of Skyline-Join Queries over Multiple Data Sources"],"prefix":"10.1145","volume":"40","author":[{"given":"Mithila","family":"Nagendra","sequence":"first","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K. Sel\u00e7uk","family":"Candan","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the Extending Database Technology Conference (EDBT'04)","author":"Balke Wolf-Tilo","year":"2004","unstructured":"Wolf-Tilo Balke , Ulrich Guntzer , and Jason Xin Zheng . 2004 . Efficient distributed skylining for Web info systems . In Proceedings of the Extending Database Technology Conference (EDBT'04) . Wolf-Tilo Balke, Ulrich Guntzer, and Jason Xin Zheng. 2004. Efficient distributed skylining for Web info systems. In Proceedings of the Extending Database Technology Conference (EDBT'04)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183674"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-007-0103-1"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602135"},{"volume-title":"Proceedings of the International Conference on Management of Data (COMAD'10)","author":"Bhattacharya Arnab","key":"e_1_2_2_6_1","unstructured":"Arnab Bhattacharya and B. Palvali Teja . 2010. Aggregate skyline join queries: Skylines with aggregate operations over multiple relations . In Proceedings of the International Conference on Management of Data (COMAD'10) . Arnab Bhattacharya and B. Palvali Teja. 2010. Aggregate skyline join queries: Skylines with aggregate operations over multiple relations. In Proceedings of the International Conference on Management of Data (COMAD'10)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260846"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237715"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247665"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0246-6"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSKD.2010.5569700"},{"volume-title":"Proceedings of the Conference on Very Large Databases (VLDB'03)","author":"Ilyas Ihab F.","key":"e_1_2_2_15_1","unstructured":"Ihab F. Ilyas , Walid G. Aref , and Ahmed K. Elmagarmid . 2003. Supporting top-k join queries in relational databases . In Proceedings of the Conference on Very Large Databases (VLDB'03) . 754--765. Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. 2003. Supporting top-k join queries in relational databases. In Proceedings of the Conference on Very Large Databases (VLDB'03). 754--765."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368992"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447841"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767894"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287394"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the Conference on Very Large Databases (VLDB'07)","author":"Lee Ken C. K.","year":"2007","unstructured":"Ken C. K. Lee , Baihua Zheng , Huajing Li , and Wang-Chien Lee . 2007 . Approaching the skyline in Z order . In Proceedings of the Conference on Very Large Databases (VLDB'07) . Ken C. K. Lee, Baihua Zheng, Huajing Li, and Wang-Chien Lee. 2007. Approaching the skyline in Z order. In Proceedings of the Conference on Very Large Databases (VLDB'07)."},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'10)","author":"Levandoski Justin J.","key":"e_1_2_2_23_1","unstructured":"Justin J. Levandoski , Mohamed F. Mokbel , and Mohamed E. Khalefa . 2010. FlexPref: A framework for extensible preference evaluation in database systems . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10) . Justin J. Levandoski, Mohamed F. Mokbel, and Mohamed E. Khalefa. 2010. FlexPref: A framework for extensible preference evaluation in database systems. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005569"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90071-O"},{"volume-title":"A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing","author":"Morton G. M.","key":"e_1_2_2_26_1","unstructured":"G. M. Morton . 1966. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing . IBM , Ottawa, Canada . G. M. Morton. 1966. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. IBM, Ottawa, Canada."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247627"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the Conference on Very Large Databases (VLDB'01)","author":"Natsev Apostol","year":"2001","unstructured":"Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , and Jeffrey Scott Vitter . 2001 . Supporting incremental join queries on ranked inputs . In Proceedings of the Conference on Very Large Databases (VLDB'01) . 281--290. Apostol Natsev, Yuan-Chi Chang, John R. Smith, Chung-Sheng Li, and Jeffrey Scott Vitter. 2001. Supporting incremental join queries on ranked inputs. In Proceedings of the Conference on Very Large Databases (VLDB'01). 281--290."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'10)","author":"Raghavan Venkatesh","key":"e_1_2_2_30_1","unstructured":"Venkatesh Raghavan and Elke A. Rundensteiner . 2010. Progressive result generation for multi-criteria decision support queries . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10) . 733--744. Venkatesh Raghavan and Elke A. Rundensteiner. 2010. Progressive result generation for multi-criteria decision support queries. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10). 733--744."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2011.03.002"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33074-2_24"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536365"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90042-7"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'08)","author":"Sun Dalie","key":"e_1_2_2_35_1","unstructured":"Dalie Sun , Sai Wu , Jianzhong Li , and Anthony K. H. Tung . 2008. Skyline-join in distributed databases . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'08) Workshops. Dalie Sun, Sai Wu, Jianzhong Li, and Anthony K. H. Tung. 2008. Skyline-join in distributed databases. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'08) Workshops."},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the Conference on Very Large Databases (VLDB'01)","author":"Tan Kian-Lee","year":"2001","unstructured":"Kian-Lee Tan , Pin-Kwang Eng , and Beng Chin Ooi . 2001 . Efficient progressive skyline computation . In Proceedings of the Conference on Very Large Databases (VLDB'01) . Kian-Lee Tan, Pin-Kwang Eng, and Beng Chin Ooi. 2001. Efficient progressive skyline computation. In Proceedings of the Conference on Very Large Databases (VLDB'01)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.266"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376642"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989332"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920951"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556686"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699483","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2699483"],"URL":"https:\/\/doi.org\/10.1145\/2699483","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}