Kang, BoHu, HaoLaViola, Joseph J.Metin Sezgin2016-02-252016-02-252014978-1-4503-3018-341812-3503https://doi.org/10.1145/2630407.2630408Sketching is a natural way to input chemical structures that can be used to query information from a large chemical structure database. Based on a user's incomplete sketch of a chemical structure, sketch prediction becomes a challenging problem not only due to arbitrary drawings orders among users but also similarities among chemical structure layouts. In this paper, we present a graph-based approach to handle the sketch prediction problem. We use multisets as the data representation of hand-drawn chemical structures and create an undirected graph to handle data in all multisets. This approach transforms the sketch prediction problem into a search problem to find a hamiltonian path in the corresponding sub-graph with polynomial time complexity. We introduce mixed heuristics to guide the search procedure. Through an initial experiment on a hand-drawn chemical structure dataset, we demonstrate that in comparison with a baseline method, the proposed approach improves the prediction accuracy and efficiently predicts chemical structures from only partially sketched drawings.I.7.5 [Document management and text processing]Document captureGraphics recognition and interpretationI.2.8 [Artificial intelligence]Search methodologiesSearch with partial observationsChemical Structure Sketch PredictionGraph SearchHeuristicsHamiltonian Path10.1145/2630407.263040827-34