A Study on Theoretical Modified Interactive Graph Search Algorithm
Xiuqi Zhu · Theoretical and Natural Science · 2025
Interactive search on hierarchical structures, such as trees and Directed Acyclic Graphs (DAGs), is a crucial problem with applications in various domains, including data retrieval, recommendation systems, and biological networks. Existing methods for interactive search exhibit significant limitations in both theoretical and practical aspects, particularly in handling high-degree nodes and minimizing the number of queries. In this paper, we present a novel approach to interactive graph search that reduces the gap between the current performance bounds and the theoretical optimum. We introduce new algorithms, including an improved Golden Search for binary trees and a method for Equivalence Tree Rewrite, that efficiently manage high-degree nodes and enhance the overall retrieval performance. Our theoretical analysis establishes tighter lower bounds for the number of queries, and our experimental results on multiple real-world datasets demonstrate significant improvements over state-of-the-art methods. The proposed approach not only achieves better performance in terms of query reduction but also provides a more robust framework for practical applications in complex hierarchical datasets.