{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:20:48Z","timestamp":1755998448880,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T00:00:00Z","timestamp":1335830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004085","name":"Ministry of Education, Science and Technology","doi-asserted-by":"publisher","award":["R31-30007"],"award-info":[{"award-number":["R31-30007"]}],"id":[{"id":"10.13039\/501100004085","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2012CB316200"],"award-info":[{"award-number":["2012CB316200"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,5]]},"abstract":"<jats:p>\n            An\n            <jats:italic>(edge) hidden graph<\/jats:italic>\n            is a graph whose edges are notexplicitly given. Detecting the presence of an edge requires an expensive edge probing query. We consider the\n            <jats:italic>k Most Connected Vertex<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            -MCV) problem on hidden bipartite graphs. Given a bipartite graph\n            <jats:italic>G<\/jats:italic>\n            with independent vertex sets\n            <jats:italic>B<\/jats:italic>\n            and\n            <jats:italic>W<\/jats:italic>\n            , the goal is to find the\n            <jats:italic>k<\/jats:italic>\n            vertices in\n            <jats:italic>B<\/jats:italic>\n            with the largest degrees using the minimum number of queries. This problem can be regarded as a top-\n            <jats:italic>k<\/jats:italic>\n            extension of semi-join, and is encountered in several applications in practice.\n          <\/jats:p>\n          <jats:p>\n            If\n            <jats:italic>B<\/jats:italic>\n            and\n            <jats:italic>W<\/jats:italic>\n            have\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>m<\/jats:italic>\n            vertices, respectively, the number of queries needed to solve the problem is\n            <jats:italic>nm<\/jats:italic>\n            in the worst case. This, however, is a pessimistic estimate on how many queries are necessary on practical data. In fact, on some inputs, the problem may be settled with only\n            <jats:italic>km<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            queries, which is significantly lower than\n            <jats:italic>nm<\/jats:italic>\n            for\n            <jats:italic>k<\/jats:italic>\n            \u226a\n            <jats:italic>n<\/jats:italic>\n            . The huge difference between\n            <jats:italic>km<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>nm<\/jats:italic>\n            makes it interesting to design an adaptive algorithm that is guaranteed to achieve the best possible performance on every input\n            <jats:italic>G<\/jats:italic>\n            . For\n            <jats:italic>k<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            \/2, we give an algorithm that is instance optimal among a broad class of solutions. This means that, for any\n            <jats:italic>G<\/jats:italic>\n            , our algorithm can perform more queries than the optimal solution (which is unknown) by only a constant factor, which can be shown at most 2.\n          <\/jats:p>\n          <jats:p>\n            As a second step, we study an \u03b5-approximate version of the\n            <jats:italic>k<\/jats:italic>\n            -MCV problem, where \u03b5 is a parameter satisfying 0 &lt; \u03b5 &lt; 1. The goal is to return\n            <jats:italic>k<\/jats:italic>\n            black vertices\n            <jats:italic>b<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>\n              b\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            such that the degree of\n            <jats:italic>\n              b\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>i<\/jats:italic>\n            \u2264\n            <jats:italic>k<\/jats:italic>\n            ) can be smaller than\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            by a factor of at most \u03b5, where\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            , \u2026,\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            (in nonascending order) are the degrees of the\n            <jats:italic>k<\/jats:italic>\n            most connected black vertices. We give an efficient randomized algorithm that successfully finds the correct answer with high probability. In particular, for a fixed \u03b5 and a fixed success probability, our algorithm performs\n            <jats:italic>o(nm)<\/jats:italic>\n            queries in expectation for\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            = \u03c9(log\n            <jats:italic>n<\/jats:italic>\n            ). In other words, whenever\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            is greater than log\n            <jats:italic>n<\/jats:italic>\n            by more than a constant, our algorithm beats the \u03a9(\n            <jats:italic>nm<\/jats:italic>\n            ) lower bound for solving the\n            <jats:italic>k<\/jats:italic>\n            -MCV problem exactly. All the proposed algorithms, despite the complication of their underlying theory, are simple enough for easy implementation in practice. Extensive experiments have confirmed that their performance in reality agrees with our theoretical findings very well.\n          <\/jats:p>","DOI":"10.1145\/2188349.2188354","type":"journal-article","created":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T15:51:28Z","timestamp":1338565888000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Exact and approximate algorithms for the most connected vertex problem"],"prefix":"10.1145","volume":"37","author":[{"given":"Cheng","family":"Sheng","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Sha Tin, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong and Korea Advanced Institute of Science and Technology, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748030"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702420139"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199358655"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001737"},{"volume-title":"Proceedings of the Canadian Conference on Computational Geometry (CCCG).","author":"Barbay J.","key":"e_1_2_1_9_1","unstructured":"Barbay , J. and Chen , E. Y . 2008. Convex hull of the union of convex objects in the plane: An adaptive analysis . In Proceedings of the Canadian Conference on Computational Geometry (CCCG). Barbay, J. and Chen, E. Y. 2008. Convex hull of the union of convex objects in the plane: An adaptive analysis. In Proceedings of the Canadian Conference on Computational Geometry (CCCG)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00422-5"},{"volume-title":"Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS). 93--102","author":"Bogdanov A.","key":"e_1_2_1_11_1","unstructured":"Bogdanov , A. , Obata , K. , and Trevisan , L . 2002. A lower bound for testing 3-colorability in bounded-degree graphs . In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS). 93--102 . Bogdanov, A., Obata, K., and Trevisan, L. 2002. A lower bound for testing 3-colorability in bounded-degree graphs. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS). 93--102."},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","key":"e_1_2_1_12_1","unstructured":"Borodin , A. and El-Yaniv , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press . Borodin, A. and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142530"},{"key":"e_1_2_1_14_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press."},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 496--505","author":"Demaine E. D.","key":"e_1_2_1_15_1","unstructured":"Demaine , E. D. , Harmon , D. , Iacono , J. , Kane , D. , and P\u0103tra\u015fcu , M . 2009. The geometry of binary search trees . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 496--505 . Demaine, E. D., Harmon, D., Iacono, J., Kane, D., and P\u0103tra\u015fcu, M. 2009. The geometry of binary search trees. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 496--505."},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752","author":"Demaine E. D.","key":"e_1_2_1_16_1","unstructured":"Demaine , E. D. , L\u00f3pez-Ortiz , A. , and Munro , J. I . 2000. Adaptive set intersections, unions, and differences . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752 . Demaine, E. D., L\u00f3pez-Ortiz, A., and Munro, J. I. 2000. Adaptive set intersections, unions, and differences. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_18_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_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.66"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 754--765","author":"Ilyas I. F.","key":"e_1_2_1_22_1","unstructured":"Ilyas , I. F. , Aref , W. G. , and Elmagarmid , A. K . 2003. Supporting top-k join queries in relational databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 754--765 . Ilyas, I. F., Aref, W. G., and Elmagarmid, A. K. 2003. Supporting top-k join queries in relational databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 754--765."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.599926"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798348365"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287405"},{"key":"e_1_2_1_27_1","article-title":"Some properties of pascal distribution for finite population","volume":"57","author":"Matuszewski T. I.","year":"1962","unstructured":"Matuszewski , T. I. 1962 . Some properties of pascal distribution for finite population . J. Amer. Statist. Assoc. 57 , 297, 172--174. Matuszewski, T. I. 1962. Some properties of pascal distribution for finite population. J. Amer. Statist. Assoc. 57, 297, 172--174.","journal-title":"J. Amer. Statist. Assoc."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 281--290","author":"Natsev A.","key":"e_1_2_1_28_1","unstructured":"Natsev , A. , Chang , Y.-C. , Smith , J. R. , Li , C.-S. , and Vitter , J. S . 2001. Supporting incremental join queries on ranked inputs . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 281--290 . Natsev, A., Chang, Y.-C., Smith, J. R., Li, C.-S., and Vitter, J. S. 2001. Supporting incremental join queries on ranked inputs. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 281--290."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376924"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367586"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386119"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807263"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0117-y"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.65"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2188349.2188354","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2188349.2188354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:11Z","timestamp":1750236551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2188349.2188354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["10.1145\/2188349.2188354"],"URL":"https:\/\/doi.org\/10.1145\/2188349.2188354","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,5]]},"assertion":[{"value":"2011-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}