{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T04:29:49Z","timestamp":1747801789663,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p>\n            Interactive graph search (IGS) over DAGs aims to find a hidden target by asking interactive questions as few as possible. IGS is useful for many applications, e.g., facilitating supervised learning tasks by harnessing labeled data, image categorization, and product classification. However, most of the existing IGS methods only work for either\n            <jats:italic>single target search on DAGs<\/jats:italic>\n            or\n            <jats:italic>multiple targets search on simple trees.<\/jats:italic>\n            To overcome the gap, it motivates us to study a challenging and yet not solved problem of multiple targets search over DAGs. We analyze the new problem in-depth and propose a key concept of uncertain candidates. Based on it, we design an effective gain function to determine the best vertex to be asked questions and shrink the search space of potential targets greatly. Leveraging our uncertain candidates and gain function, we develop a unified k-EIS framework to search both single target and multiple targets. We analyze all algorithm complexities and theoretically show that our solution can significantly improve existing DFS-tree-based methods by asking\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) questions to\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ) questions in worst cases. To further improve IGS for multiple targets, we propose an advanced solution by dividing the whole DAG into\n            <jats:italic>k<\/jats:italic>\n            disjoint subgraphs with single targets and then tackling each subgraph one by one independently. Extensive experiments on real-world datasets validate that our proposed k-EIS framework can save lots of questions to search exact targets against four state-of-the-art IGS competitors.\n          <\/jats:p>","DOI":"10.14778\/3717755.3717768","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T15:51:49Z","timestamp":1747756309000},"page":"1091-1103","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Interactive Graph Search for Multiple Targets on DAGs"],"prefix":"10.14778","volume":"18","author":[{"given":"Zheng","family":"Wu","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University"}]},{"given":"Xuliang","family":"Zhu","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}]}],"member":"320","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. https:\/\/www.mpi-inf.mpg.de\/departments\/databases-and-information-systems\/research\/yago-naga\/yago."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 17th ACM conference on Information and knowledge management. 13\u201322","author":"Roy Senjuti Basu","year":"2008","unstructured":"Senjuti Basu Roy, Haidong Wang, Gautam Das, Ullas Nambiar, and Mukesh Mohania. 2008. Minimum-effort driven dynamic faceted search in structured databases. In Proceedings of the 17th ACM conference on Information and knowledge management. 13\u201322."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539267"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00091"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3199672"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750550"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_9_1","volume-title":"WordNet: An electronic lexical database","author":"Fellbaum Christiane","unstructured":"Christiane Fellbaum. 1998. WordNet: An electronic lexical database. MIT press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213880"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883037"},{"key":"e_1_2_1_12_1","volume-title":"International conference on machine learning. PMLR, 534\u2013542","author":"Ho Chien-Ju","year":"2013","unstructured":"Chien-Ju Ho, Shahin Jabbari, and Jennifer Wortman Vaughan. 2013. Adaptive task assignment for crowdsourced classification. In International conference on machine learning. PMLR, 534\u2013542."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.211"},{"key":"e_1_2_1_14_1","volume-title":"Laks VS Lakshmanan, and Jianliang Xu","author":"Huang Xin","year":"2019","unstructured":"Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2019. Community Search over Big Graphs. Morgan & Claypool Publishers."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604455"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371769"},{"key":"e_1_2_1_18_1","first-page":"735","article-title":"Knowledge-Driven Interactive Graph Search","volume":"59","author":"Li Yingxue","year":"2023","unstructured":"Yingxue Li, Shaohan Chen, and Weiguo Zheng. 2023. Knowledge-Driven Interactive Graph Search. Beijing Da Xue Xue Bao 59, 5 (2023), 735\u2013746.","journal-title":"Beijing Da Xue Xue Bao"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389139"},{"key":"e_1_2_1_20_1","volume-title":"Adapative algorithms for crowd-aided categorization. The VLDB Journal","author":"Li Yuanbing","year":"2022","unstructured":"Yuanbing Li, Xian Wu, Yifei Jin, Jian Li, Guoliang Li, and Jianhua Feng. 2022. Adapative algorithms for crowd-aided categorization. The VLDB Journal (2022), 1\u201327."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336676"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524150"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604456"},{"key":"e_1_2_1_24_1","unstructured":"Farzaneh Mahdisoltani Joanna Biega and Fabian M Suchanek. 2015. Yago3: A knowledge base from multilingual wikipedias. In CIDR."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448944"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1018"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732942"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1952376.1952377"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213878"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626956"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319885"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035931"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536337"},{"key":"e_1_2_1_34_1","volume-title":"Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. Advances in neural information processing systems 22","author":"Whitehill Jacob","year":"2009","unstructured":"Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. 2009. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. Advances in neural information processing systems 22 (2009)."},{"key":"e_1_2_1_35_1","volume-title":"Efficient Example-Guided Interactive Graph Search. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 342\u2013354","author":"Zhao Zhuowei","year":"2024","unstructured":"Zhuowei Zhao, Junhao Gan, Jianzhong Qi, and Zhifeng Bao. 2024. Efficient Example-Guided Interactive Graph Search. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 342\u2013354."},{"key":"e_1_2_1_36_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\/3717755.3717768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T16:16:09Z","timestamp":1747757769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3717755.3717768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.14778\/3717755.3717768"],"URL":"https:\/\/doi.org\/10.14778\/3717755.3717768","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,12]]},"assertion":[{"value":"2025-05-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}