{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T06:43:33Z","timestamp":1784357013862,"version":"3.55.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2008,11]]},"abstract":"<jats:p>\n            Skyline queries compute the set of Pareto-optimal tuples in a relation, that is, those tuples that are not\n            <jats:italic>dominated<\/jats:italic>\n            by any other tuple in the same relation. Although several algorithms have been proposed for efficiently evaluating skyline queries, they either necessitate the relation to have been indexed or have to perform the dominance tests on\n            <jats:italic>all<\/jats:italic>\n            the tuples in order to determine the result. In this article we introduce salsa, a novel skyline algorithm that exploits the idea of presorting the input data so as to effectively\n            <jats:italic>limit<\/jats:italic>\n            the number of tuples to be read and compared. This makes salsa also attractive when skyline queries are executed on top of systems that do not understand skyline semantics, or when the skyline logic runs on clients with limited power and\/or bandwidth. We prove that, if one considers symmetric sorting functions, the number of tuples to be read is minimized by sorting data according to a \u201cminimum coordinate,\u201d minC, criterion, and that performance can be further improved if data distribution is known and an asymmetric sorting function is used. Experimental results obtained on synthetic and real datasets show that salsa consistently outperforms state-of-the-art sequential skyline algorithms and that its performance can be accurately predicted.\n          <\/jats:p>","DOI":"10.1145\/1412331.1412343","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":165,"title":["Efficient sort-based skyline evaluation"],"prefix":"10.1145","volume":"33","author":[{"given":"Ilaria","family":"Bartolini","sequence":"first","affiliation":[{"name":"Alma Mater Studiorum\u2014Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paolo","family":"Ciaccia","sequence":"additional","affiliation":[{"name":"Alma Mater Studiorum\u2014Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Patella","sequence":"additional","affiliation":[{"name":"Alma Mater Studiorum\u2014Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304184"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 6th International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science","volume":"2992","author":"Balke W.-T.","unstructured":"Balke , W.-T. , G\u00fcntzer , U. , and Zheng , J. X . 2004. Efficient distributed skylining for web information systems . In Proceedings of the 6th International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science , vol. 2992 , Springer, Berlin, Heidelberg, New York, 256--273. Balke, W.-T., G\u00fcntzer, U., and Zheng, J. X. 2004. Efficient distributed skylining for web information systems. In Proceedings of the 6th International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science, vol. 2992, Springer, Berlin, Heidelberg, New York, 256--273."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 10th International Workshop on Multimedia Information Systems (MIS)","volume":"2992","author":"Bartolini I.","year":"2004","unstructured":"Bartolini , I. , Ciaccia , P. , Oria , V. , and \u00d6zsu , T. 2004 . Integrating the results of multimedia sub-queries using qualitative preferences . In Proceedings of the 10th International Workshop on Multimedia Information Systems (MIS) . College Park, MD. Lecture Notes in Computer Science , vol. 2992 , Springer, Berlin, Heidelberg, New York, 66--75. Bartolini, I., Ciaccia, P., Oria, V., and \u00d6zsu, T. 2004. Integrating the results of multimedia sub-queries using qualitative preferences. In Proceedings of the 10th International Workshop on Multimedia Information Systems (MIS). College Park, MD. Lecture Notes in Computer Science, vol. 2992, Springer, Berlin, Heidelberg, New York, 66--75."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-007-0103-1"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183674"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 17th International Conference on Data Engineering (ICDE)","author":"B\u00f6rzs\u00f6nyi S.","unstructured":"B\u00f6rzs\u00f6nyi , S. , Kossmann , D. , and Stocker , K . 2001. The skyline operator . In Proceedings of the 17th International Conference on Data Engineering (ICDE) . Heidelberg, Germany, IEEE Computer Society, Washington, DC, 421--430. B\u00f6rzs\u00f6nyi, S., Kossmann, D., and Stocker, K. 2001. The skyline operator. In Proceedings of the 17th International Conference on Data Engineering (ICDE). Heidelberg, Germany, IEEE Computer Society, Washington, DC, 421--430."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90156-7"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.131"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958946"},{"key":"e_1_2_2_10_1","volume-title":"Tech. Rep. CS-2002-04","author":"Chomicki J.","year":"2002","unstructured":"Chomicki , J. , Godfrey , P. , Gryz , J. , and Liang , D . 2002 . Skyline with presorting. Tech. Rep. CS-2002-04 , York University , Toronto, ON . Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2002. Skyline with presorting. Tech. Rep. CS-2002-04, York University, Toronto, ON."},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the 19th International Conference on Data Engineering (ICDE)","author":"Chomicki J.","unstructured":"Chomicki , J. , Godfrey , P. , Gryz , J. , and Liang , D . 2003. Skyline with presorting . In Proceedings of the 19th International Conference on Data Engineering (ICDE) . Bangalore, India. IEEE Computer Society, Washington, DC, 717--816. Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2003. Skyline with presorting. In Proceedings of the 19th International Conference on Data Engineering (ICDE). Bangalore, India. IEEE Computer Society, Washington, DC, 717--816."},{"key":"e_1_2_2_12_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_2_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS)","author":"Godfrey P.","unstructured":"Godfrey , P. 2004. Skyline cardinality for relational processing . In Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS) . Lecture Notes in Computer Science , vol. 2942 , Springer , Berlin, Heidelberg , New York, 78--97. Godfrey, P. 2004. Skyline cardinality for relational processing. In Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS). Lecture Notes in Computer Science, vol. 2942, Springer, Berlin, Heidelberg, New York, 78--97."},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB)","author":"Godfrey P.","unstructured":"Godfrey , P. , Shipley , R. , and Gryz , J . 2005. Maximal vector computation in large data sets . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB) . Trondheim, Norway. Morgan Kaufmann, San Francisco, CA, 229--240. Godfrey, P., Shipley, R., and Gryz, J. 2005. Maximal vector computation in large data sets. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). Trondheim, Norway. Morgan Kaufmann, San Francisco, CA, 229--240."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287397"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB)","author":"Kossmann D.","unstructured":"Kossmann , D. , Ramsak , F. , and 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 (VLDB) . Hong Kong, China. Morgan Kaufmann, San Francisco, CA, 275--286. Kossmann, D., Ramsak, F., and 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 (VLDB). Hong Kong, China. Morgan Kaufmann, San Francisco, CA, 275--286."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872814"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX) and the 3rd Workshop on Analytic Algorithmics and Combinatorics (ANALCO)","author":"Paredes R.","unstructured":"Paredes , R. and Navarro , G . 2006. Optimal incremental sorting . In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX) and the 3rd Workshop on Analytic Algorithmics and Combinatorics (ANALCO) . Miami, FL. SIAM Press, Philadelphia, PA, 171--182. Paredes, R. and Navarro, G. 2006. Optimal incremental sorting. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX) and the 3rd Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Miami, FL. SIAM Press, Philadelphia, PA, 171--182."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Preparata F. P. and Shamos M. I. 1985. Computational Geometry\u2014An Introduction. Springer.   Preparata F. P. and Shamos M. I. 1985. Computational Geometry\u2014An Introduction. Springer.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_2_21_1","first-page":"243","article-title":"On the distributions of the product and the quotient of the independent and uniformly distributed random variables","volume":"49","author":"Sakamoto H.","year":"1943","unstructured":"Sakamoto , H. 1943 . On the distributions of the product and the quotient of the independent and uniformly distributed random variables . Tohoku Math. J. 49 , 243 -- 260 . Sakamoto, H. 1943. On the distributions of the product and the quotient of the independent and uniformly distributed random variables. Tohoku Math. J. 49, 243--260.","journal-title":"Tohoku Math. J."},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases (VLDB)","author":"Tan K.-L.","unstructured":"Tan , K.-L. , Eng , P.-K. , and Ooi , B. C . 2001. Efficient progressive skyline computation . In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB) . Rome, Italy, Morgan Kaufmann, San Francisco, CA, 301--310. Tan, K.-L., Eng, P.-K., and Ooi, B. C. 2001. Efficient progressive skyline computation. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). Rome, Italy, Morgan Kaufmann, San Francisco, CA, 301--310."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.149"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412331.1412343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1412331.1412343"],"URL":"https:\/\/doi.org\/10.1145\/1412331.1412343","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2007-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}