  The database community has long recognized the importance of graphical query
interface to the usability of data management systems. Yet, relatively less has
been done. We present Orion, a visual interface for querying
ultra-heterogeneous graphs. It iteratively assists users in query graph
construction by making suggestions via machine learning methods. In its active
mode, Orion automatically suggests top-k edges to be added to a query graph. In
its passive mode, the user adds a new edge manually, and Orion suggests a
ranked list of labels for the edge. Orion's edge ranking algorithm, Random
Decision Paths (RDP), makes use of a query log to rank candidate edges by how
likely they will match the user's query intent. Extensive user studies using
Freebase demonstrated that Orion users have a 70% success rate in constructing
complex query graphs, a significant improvement over the 58% success rate by
the users of a baseline system that resembles existing visual query builders.
Furthermore, using active mode only, the RDP algorithm was compared with
several methods adapting other machine learning algorithms such as random
forests and naive Bayes classifier, as well as class association rules and
recommendation systems based on singular value decomposition. On average, RDP
required 40 suggestions to correctly reach a target query graph (using only its
active mode of suggestion) while other methods required 1.5--4 times as many
suggestions.
