Title

Mixed Heuristic Search For Sketch Prediction On Chemical Structure Drawing

Keywords

Chemical structure sketch prediction; Graph search; Hamiltonian path; Heuristics

Abstract

Sketching 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.

Publication Date

8-8-2014

Publication Title

SBM: Sketch Based Interfaces and Modeling

Volume

2014-January

Number of Pages

27-34

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/2630407.2630408

Socpus ID

84958763434 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84958763434

This document is currently not available here.

Share

COinS