INTERACTIVE GRAPH SEARCH: ALGORITHMS AND ANALYSES

Abstract

The interactive graph search (IGS) problem aims to locate an initially unknown target node in hierarchy leveraging sequential interactive queries. The main efficiency goal asks for the minimum number of queries to identify the correct target node. In this thesis, we develop cost-effective algorithms for three variants of the IGS problem. First, we study the average-case interactive graph search problem that aims to minimize the expected number of queries when the target nodes follow a given probability distribution. Second, we study a noisy version of the IGS problem. The objective in this problem is to minimize the query complexity while ensuring accuracy. Third, we study the round-constrained interactive graph search problem (RIGS), where we can locate the target by at most R rounds of interaction. Extensive experiments in real-world datasets are carried out to demonstrate the effectiveness and efficiency of our proposed methods.