  For approximate nearest neighbor search, graph-based algorithms have shown to
offer the best trade-off between accuracy and search time. We propose the
Dynamic Exploration Graph (DEG) which significantly outperforms existing
algorithms in terms of search and exploration efficiency by combining two new
ideas: First, a single undirected even regular graph is incrementally built by
partially replacing existing edges to integrate new vertices and to update old
neighborhoods at the same time. Secondly, an edge optimization algorithm is
used to continuously improve the quality of the graph. Combining this ongoing
refinement with the graph construction process leads to a well-organized graph
structure at all times, resulting in: (1) increased search efficiency, (2)
predictable index size, (3) guaranteed connectivity and therefore reachability
of all vertices, and (4) a dynamic graph structure. In addition we investigate
how well existing graph-based search systems can handle indexed queries where
the seed vertex of a search is the query itself. Such exploration tasks,
despite their good starting point, are not necessarily easy. High efficiency in
approximate nearest neighbor search (ANNS) does not automatically imply good
performance in exploratory search. Extensive experiments show that our new
Dynamic Exploration Graph outperforms existing algorithms significantly for
indexed and unindexed queries.
