{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T16:45:04Z","timestamp":1778258704567,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T00:00:00Z","timestamp":1109635200000},"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":[[2005,3]]},"abstract":"<jats:p>\n            The skyline of a\n            <jats:italic>d<\/jats:italic>\n            -dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I\/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.\n          <\/jats:p>","DOI":"10.1145\/1061318.1061320","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"41-82","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":714,"title":["Progressive skyline computation in database systems"],"prefix":"10.1145","volume":"30","author":[{"given":"Dimitris","family":"Papadias","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}]},{"given":"Greg","family":"Fu","sequence":"additional","affiliation":[{"name":"JP Morgan Chase, New York, NY"}]},{"given":"Bernhard","family":"Seeger","sequence":"additional","affiliation":[{"name":"Philipps University, Marburg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2005,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304184"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT; Heraklio, Greece, Mar. 14--18)","author":"Balke W.","unstructured":"Balke , W. , Gunzer , U. , and Zheng , J . 2004. Efficient distributed skylining for Web information systems . In Proceedings of the International Conference on Extending Database Technology (EDBT; Heraklio, Greece, Mar. 14--18) . 256--273.]] Balke, W., Gunzer, U., and Zheng, J. 2004. Efficient distributed skylining for Web information systems. In Proceedings of the International Conference on Extending Database Technology (EDBT; Heraklio, Greece, Mar. 14--18). 256--273.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Very Large Data Bases Conference (VLDB; Mumbai, India, Sep. 3--6). 28--39","author":"Berchtold S.","unstructured":"Berchtold , S. , Keim , D. , and Kriegel , H . 1996. The X-tree: An index structure for high-dimensional data . In Proceedings of the Very Large Data Bases Conference (VLDB; Mumbai, India, Sep. 3--6). 28--39 .]] Berchtold, S., Keim, D., and Kriegel, H. 1996. The X-tree: An index structure for high-dimensional data. In Proceedings of the Very Large Data Bases Conference (VLDB; Mumbai, India, Sep. 3--6). 28--39.]]"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWaK; Munich, Germany, Sep. 5--7). 294--306","author":"B\u00f6hm C.","unstructured":"B\u00f6hm , C. and Kriegel , H . 2001. Determining the convex hull in large multidimensional databases . In Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWaK; Munich, Germany, Sep. 5--7). 294--306 .]] B\u00f6hm, C. and Kriegel, H. 2001. Determining the convex hull in large multidimensional databases. In Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWaK; Munich, Germany, Sep. 5--7). 294--306.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE; Heidelberg, Germany, Apr. 2--6). 421--430","author":"Borzsonyi S.","unstructured":"Borzsonyi , S. , Kossmann , D. , and Stocker , K . 2001. The skyline operator . In Proceedings of the IEEE International Conference on Data Engineering (ICDE; Heidelberg, Germany, Apr. 2--6). 421--430 .]] Borzsonyi, S., Kossmann, D., and Stocker, K. 2001. The skyline operator. In Proceedings of the IEEE International Conference on Data Engineering (ICDE; Heidelberg, Germany, Apr. 2--6). 421--430.]]"},{"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\/342009.335433"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE; Bangalore, India, Mar. 5--8). 717--719","author":"Chomicki J.","unstructured":"Chomicki , J. , Godfrey , P. , Gryz , J. , and Liang , D . 2003. Skyline with pre-sorting . In Proceedings of the IEEE International Conference on Data Engineering (ICDE; Bangalore, India, Mar. 5--8). 717--719 .]] Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2003. Skyline with pre-sorting. In Proceedings of the IEEE International Conference on Data Engineering (ICDE; Bangalore, India, Mar. 5--8). 717--719.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Symposium on Spatial and Temporal Databases (SSTD; Redondo Beach, CA, July 12--15)","author":"Ferhatosmanoglu H.","unstructured":"Ferhatosmanoglu , H. , Stanoi , I. , Agrawal , D. , and Abbadi , A . 2001. Constrained nearest neighbor queries . In Proceedings of the International Symposium on Spatial and Temporal Databases (SSTD; Redondo Beach, CA, July 12--15) . 257--278.]] Ferhatosmanoglu, H., Stanoi, I., Agrawal, D., and Abbadi, A. 2001. Constrained nearest neighbor queries. In Proceedings of the International Symposium on Spatial and Temporal Databases (SSTD; Redondo Beach, CA, July 12--15). 257--278.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781635"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM Workshop on Geographic Information Systems (ACM GIS; Gaithersburg, MD, Dec.). 136--143","author":"Henrich A.","year":"1994","unstructured":"Henrich , A. 1994 . A distance scan algorithm for spatial access structures . In Proceedings of the ACM Workshop on Geographic Information Systems (ACM GIS; Gaithersburg, MD, Dec.). 136--143 .]] Henrich, A. 1994. A distance scan algorithm for spatial access structures. In Proceedings of the ACM Workshop on Geographic Information Systems (ACM GIS; Gaithersburg, MD, Dec.). 136--143.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Very Large Data Bases Conference (VLDB; Hong Kong, China, Aug. 20--23)","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 Very Large Data Bases Conference (VLDB; Hong Kong, China, Aug. 20--23) . 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 Very Large Data Bases Conference (VLDB; Hong Kong, China, Aug. 20--23). 275--286.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90071-O"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.4.318"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50205"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Very Large Data Bases Conference (VLDB; Rome, Italy, Sep. 11--14)","author":"Natsev A.","year":"2001","unstructured":"Natsev , A. , Chang , Y. , Smith , J., Li., C. , and Vitter . J. 2001 . Supporting incremental join queries on ranked inputs . In Proceedings of the Very Large Data Bases Conference (VLDB; Rome, Italy, Sep. 11--14) . 281--290.]] Natsev, A., Chang, Y., Smith, J., Li., C., and Vitter. J. 2001. Supporting incremental join queries on ranked inputs. In Proceedings of the Very Large Data Bases Conference (VLDB; Rome, Italy, Sep. 11--14). 281--290.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872814"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of International Symposium on Spatial and Temporal Databases (SSTD; Redondo Beach, CA, July 12--15)","author":"Papadias D.","unstructured":"Papadias , D. , Kalnis , P. , Zhang , J. , and Tao , Y . 2001. Efficient OLAP operations in spatial data warehouses . In Proceedings of International Symposium on Spatial and Temporal Databases (SSTD; Redondo Beach, CA, July 12--15) . 443--459.]] Papadias, D., Kalnis, P., Zhang, J., and Tao, Y. 2001. Efficient OLAP operations in spatial data warehouses. In Proceedings of International Symposium on Spatial and Temporal Databases (SSTD; Redondo Beach, CA, July 12--15). 443--459.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Preparata F. and Shamos M. 1985. Computational Geometry---An Introduction. Springer Berlin Germany.]]   Preparata F. and Shamos M. 1985. Computational Geometry---An Introduction. Springer Berlin Germany.]]","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Very Large Data Bases Conference (VLDB; Cairo, Egypt, Sep. 10--14)","author":"Sakurai Y.","unstructured":"Sakurai , Y. , Yoshikawa , M. , Uemura , S. , and Kojima , H . 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation . In Proceedings of the Very Large Data Bases Conference (VLDB; Cairo, Egypt, Sep. 10--14) . 516--526.]] Sakurai, Y., Yoshikawa, M., Uemura, S., and Kojima, H. 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation. In Proceedings of the Very Large Data Bases Conference (VLDB; Cairo, Egypt, Sep. 10--14). 516--526.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/319806.319816"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Very Large Data Bases Conference (VLDB; Brighton, England, Sep. 1--4). 507--518","author":"Sellis T.","unstructured":"Sellis , T. , Roussopoulos , N. , and Faloutsos , C . 1987. The R&plus;-tree: A dynamic index for multi-dimensional objects . In Proceedings of the Very Large Data Bases Conference (VLDB; Brighton, England, Sep. 1--4). 507--518 .]] Sellis, T., Roussopoulos, N., and Faloutsos, C. 1987. The R&plus;-tree: A dynamic index for multi-dimensional objects. In Proceedings of the Very Large Data Bases Conference (VLDB; Brighton, England, Sep. 1--4). 507--518.]]"},{"key":"e_1_2_1_30_1","volume-title":"Multiple Criteria Optimization","author":"Steuer R.","unstructured":"Steuer , R. 1986. Multiple Criteria Optimization . Wiley , New York, NY .]] Steuer, R. 1986. Multiple Criteria Optimization. Wiley, New York, NY.]]"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Very Large Data Bases Conference (VLDB; Rome, Italy, Sep. 11--14)","author":"Tan K.","unstructured":"Tan , K. , Eng , P. , and Ooi , B . 2001. Efficient progressive skyline computation . In Proceedings of the Very Large Data Bases Conference (VLDB; Rome, Italy, Sep. 11--14) . 301--310.]] Tan, K., Eng, P., and Ooi, B. 2001. Efficient progressive skyline computation. In Proceedings of the Very Large Data Bases Conference (VLDB; Rome, Italy, Sep. 11--14). 301--310.]]"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842247"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1061318.1061320","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1061318.1061320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:36:56Z","timestamp":1750282616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1061318.1061320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1145\/1061318.1061320"],"URL":"https:\/\/doi.org\/10.1145\/1061318.1061320","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]},"assertion":[{"value":"2005-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}