Given a database D of three dimensional (3D) graphs and a query graph Q, the problem of substructure search is defined as finding the graphs in D that contain Q. This is an important search operation in scientific databases. This paper extends the search operation to find those graphs D in D that ``approximately'' contain Q in the presence of rotation, translation, distortion, and node insert/delete in the substructures of D and Q. Our approach is an extension of a computer vision technique, called geometric hashing, for robotics applications. Experimental results obtained by running our algorithms on a database of chemical compounds demonstrate the good performance of the proposed approach.

Download the full length paper (gzip compressed)

GO BACK