David Koes edited subsection_Shape_Indexing_and_Similarity__.tex  over 8 years ago

Commit id: 401ad34c767b21a3068e04635dad6855510a31d4

deletions | additions      

       

\subsection*{Shape Indexing and Similarity}  As with VAMS\cite{Koes_2014}, VAMS\cite{VAMS},  we use a matching and packing\cite{Koes_2014} bulk-loading algorithm to initialize an efficient data structure for volumetric shape constraint searches. Briefly, shapes are stored in a GSS-tree\cite{keim1999} where each leaf of the tree is a single molecular shape and each internal node includes a maximum included volume (MIV) and minimum surrounding volume (MSV). The MIV of a node is the intersection of all the molecular shapes beneath the node in the tree while the MSV is the union. The MIV and MSV are used to determine if all the shapes beneath a node are capable of matching the specified shape constraints: the MIV must not overlap with the excluded shape constraint while the included shape constraint must be fully contained within the MSV.  If a node high in the tree fails to match the specified shape constraints, a large fraction of the molecular shapes can be eliminated as a result of a single comparison.