{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T01:17:26Z","timestamp":1788571046016,"version":"build-2803163510"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,2]]},"abstract":"Interactive graph search leverages human intelligence to categorize target labels in a hierarchy, which is useful for image classification, product categorization, and database search. However, many existing interactive graph search studies aim at identifying a single target optimally, and suffer from the limitations of asking too many questions and not being able to handle multiple targets.<\/jats:p>\n \n To address these two limitations, in this paper, we study a new problem of <u>b<\/u>udget constrained <u>i<\/u>nteractive <u>g<\/u>raph <u>s<\/u>earch for <u>m<\/u>ultiple targets called kBM-IGS problem. Specifically, given a set of multiple targets\n T<\/jats:italic>\n in a hierarchy and two parameters\n k<\/jats:italic>\n and\n b<\/jats:italic>\n , the goal is to identify a\n k<\/jats:italic>\n -sized set of selections\n S<\/jats:italic>\n , such that the closeness between selections\n S<\/jats:italic>\n and targets\n T<\/jats:italic>\n is as small as possible, by asking at most a budget of\n b<\/jats:italic>\n questions. We theoretically analyze the updating rules and design a penalty function to capture the closeness between selections and targets. To tackle the kBM-IGS problem, we develop a novel framework to ask questions using the best vertex with the largest expected gain, which provides a balanced trade-off between target probability and benefit gain. Based on the kBM-IGS framework, we first propose an efficient algorithm STBIS to handle the SingleTarget problem, which is a special case of kBM-IGS. Then, we propose a dynamic programming based method kBM-DP to tackle the MultipleTargets problem. To further improve efficiency, we propose two heuristic but efficient algorithms, kBM-Topk and kBM-DP+. Experiments on large real-world datasets with ground-truths verify both the effectiveness and efficiency of our algorithms.\n <\/jats:p>","DOI":"10.14778\/3447689.3447694","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:20:06Z","timestamp":1618244406000},"page":"890-902","source":"Crossref","is-referenced-by-count":10,"title":["Budget constrained interactive search for multiple targets"],"prefix":"10.14778","volume":"14","author":[{"given":"Xuliang","family":"Zhu","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Byron","family":"Choi","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaxin","family":"Jiang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhaonian","family":"Zou","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/mturk.com. http:\/\/mturk.com."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/crowdflower.com. http:\/\/crowdflower.com."},{"key":"e_1_2_1_3_1","unstructured":"http:\/\/image-net.org\/download-API. http:\/\/image-net.org\/download-API."},{"key":"e_1_2_1_4_1","unstructured":"https:\/\/www.mpi-inf.mpg.de\/departments\/databases-and-information-systems\/research\/yago-naga\/yago. https:\/\/www.mpi-inf.mpg.de\/departments\/databases-and-information-systems\/research\/yago-naga\/yago."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142055.1142067"},{"key":"e_1_2_1_6_1","first-page":"25","volume-title":"HCOMP","author":"Bragg J.","year":"2013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007653"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2470654.2466265"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3148148"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"e_1_2_1_11_1","first-page":"10818","volume-title":"AAAI","author":"Gao Y.","year":"2020"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2019.00132"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047487"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986677"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.109"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-018-0074-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389139"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10602-1_48"},{"key":"e_1_2_1_19_1","first-page":"4965","volume-title":"AAAI","author":"Liu Z.","year":"2020"},{"key":"e_1_2_1_20_1","volume-title":"CIDR","author":"Mahdisoltani F.","year":"2015"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448944"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1018"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1952376.1952377"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594510"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213878"},{"key":"e_1_2_1_26_1","volume-title":"Algorithms for knapsack problems","author":"Pisinger D.","year":"1995"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832366"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i05.6435"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319885"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732982"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350263"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465280"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536337"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886664"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447694"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3447689.3447694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:17:26Z","timestamp":1672226246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3447689.3447694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.14778\/3447689.3447694"],"URL":"https:\/\/doi.org\/10.14778\/3447689.3447694","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}