Screen Searching Inverted

Over the past several years work has been underway on the second generation parallel structure search architecture. This architecture is a completely new hardware and software implementation which builds on the already proven architectural principles of the first generation system as well as taking advantage of inverted file searching rather than sequential searching to implement the screen search algorithm. 

CAS has developed a state-of-the-art inverted file search capability in support of text searching and numeric file searching that can readily beapplied to structure screen searching. 

Screen searching is done serially rather than using a more traditional inverted file approach. That is, the entire screen file for a particular file segment is read sequentially from disk into memory. All sets of query screens on the current list of queries to be searched are compared against each file structure screen set. If a query screen set matches a file screen set, then the candidate file structure is passed on to iterative search. 

The search engine architecture will substitute inverted file searching for sequential screen searching. This will permit the structure screen set size to be increased because new screens simply become new terms in the inverted dictionary. It will also permit other numeric or textual information associated with a structure to be added to the inverted screen file and processed as part of the inverted screen searching process. 

Screen search identifies the file structures that contain at least the set of screens present in the query structure. Tl e process consists of a standard inverted file search in which the search terms consist of screens generated from the query structure. The. results are a set of candidate file structures that have satisfied the screen logic expression. This candidate set is then passed to the iterative search phase. Thus, screen search provides a rapid reduction of the databa structures to those that are likely to match the query structure so that the computer intensive iterative search need only be performed on this smaller set of file strucfures. 

The purpose of the key search is to quickly screen out structures that cannot match the query. At search time, all keys contained in the query are first identified. Then, each query key is used to retrieve the corresponding key bit string from the inverted... 

Sheridan et al. ° use similar screens, except that they distinguish atoms based on aromaticity, hybridization, connectivity, and charge at neutral pH. They also calculate screens based on the positions of the lone pairs on heteroatoms and of the center of mass of rings. Thus, they have many more screens. To accommodate this, they use an inverted bit map, that is, one in which each row contains the information on which molecules possess a particular screen. This facilitates searching for example, screening 223,000 structures typically requires about 1 min CPU time on a VAX 8650. However, updating an inverted bit map when a new compound is added is much more demanding of computer resources. 

The most common implementation of keys is as bit strings, with the nth bit indicating whether a key is present or absent in the nth entry in the database (Figure 4). This inverted index has the advantage that in order to perform the screening comparisons only the index bit strings need to be read into memory and there is no need to perform an input-output (10) operation for every entry in the database. At search time, the... 

---