{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:20:51Z","timestamp":1672291251962},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>Consider an internship assignment system, where at the end of each academic year, interested university students search and apply for available positions, based on their preferences (e.g., nature of the job, salary, office location, etc). In a variety of facility, task or position assignment contexts, users have personal preferences expressed by different weights on the attributes of the searched objects. Although individual preference queries can be evaluated by selecting the object in the database with the highest aggregate score, in the case of multiple simultaneous requests, a single object cannot be assigned to more than one users. The challenge is to compute a fair 1--1 matching between the queries and the objects. We model this as a stable-marriage problem and propose an efficient method for its processing. Our algorithm iteratively finds stable query-object pairs and removes them from the problem. At its core lies a novel skyline maintenance technique, which we prove to be I\/O optimal. We conduct an extensive experimental evaluation using real and synthetic data, which demonstrates that our approach outperforms adaptations of previous methods by several orders of magnitude.<\/jats:p>","DOI":"10.14778\/1687627.1687746","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1054-1065","source":"Crossref","is-referenced-by-count":1,"title":["A fair assignment algorithm for multiple preference queries"],"prefix":"10.14778","volume":"2","author":[{"given":"Leong Hou","family":"U","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong"}]},{"given":"Nikos","family":"Mamoulis","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong"}]},{"given":"Kyriakos","family":"Mouratidis","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_115"},{"key":"e_1_2_1_2_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . Network Flows: Theory, Algorithms, and Applications . Prentice Hall , first edition, 1993 . R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, first edition, 1993."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335433"},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill , 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_10_1","first-page":"229","volume-title":"VLDB","author":"Godfrey P.","year":"2005","unstructured":"P. Godfrey , R. Shipley , and J. Gryz . Maximal vector computation in large data sets . In VLDB , pages 229 -- 240 , 2005 . P. Godfrey, R. Shipley, and J. Gryz. Maximal vector computation in large data sets. In VLDB, pages 229--240, 2005."},{"key":"e_1_2_1_11_1","volume-title":"The Stable Marriage Problem, Structure and Algorithms","author":"Gusfield D.","year":"1989","unstructured":"D. Gusfield and R. W. Irving . The Stable Marriage Problem, Structure and Algorithms . MIT Press , 1989 . D. Gusfield and R. W. Irving. The Stable Marriage Problem, Structure and Algorithms. MIT Press, 1989."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1086\/260757"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198520"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908983"},{"key":"e_1_2_1_15_1","first-page":"275","volume-title":"VLDB","author":"Kossmann D.","year":"2002","unstructured":"D. Kossmann , F. Ramsak , and S. Rost . Shooting stars in the sky: An online algorithm for skyline queries . In VLDB , pages 275 -- 286 , 2002 . D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: An online algorithm for skyline queries. In VLDB, pages 275--286, 2002."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142544"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_18_1","first-page":"301","volume-title":"VLDB","author":"Tan K.-L.","year":"2001","unstructured":"K.-L. Tan , P.-K. Eng , and B. C. Ooi . Efficient progressive skyline computation . In VLDB , pages 301 -- 310 , 2001 . K.-L. Tan, P.-K. Eng, and B. C. Ooi. Efficient progressive skyline computation. In VLDB, pages 301--310, 2001."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2005.12.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.213"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.85"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376621"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497576"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453967"},{"key":"e_1_2_1_25_1","first-page":"579","volume-title":"VLDB","author":"Wong R. C.-W.","year":"2007","unstructured":"R. C.-W. Wong , Y. Tao , A. W.-C. Fu , and X. Xiao . On efficient spatial matching . In VLDB , pages 579 -- 590 , 2007 . R. C.-W. Wong, Y. Tao, A. W.-C. Fu, and X. Xiao. On efficient spatial matching. In VLDB, pages 579--590, 2007."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367894"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.08.003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(90)90070-Z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687746","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:34:55Z","timestamp":1672227295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687746"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687746"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687746","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}