2.1 The synchronous search strategy

The main idea of synchronous search strategy is to obtain results through two steps, first getting separate results sets from the Molecular Structure Database and the Compound Property Database and then finding their intersection. The word “synchronous” means that when a server receives a query message from a browser, it handles the message by visiting the two independent databases simultaneously. However, this simple serial design for the two steps of the synchronous strategy does not perform efficiently because the speed gap between the two heterogeneous databases causes a long wait for the slower search. Thus, for the synchronous search strategy, the key to improving search efficiency is to use parallel operations to shorten the waiting time. On this point, the design for the synchronous search strategy is proposed.

The synchronous search strategy utilizes queues to organize the search results from the two individual databases. Meanwhile, the List, a container class provided by language C#, is employed to preserve the combination search results; its element’s data type is HashTable.

The synchronous search strategy process is described as follows and in Figure 1.

First, users submit a combined query through the browser to the server. The server accepts and processes the query into two SQL queries. They each request only the ID number of the satisfactory compounds. The server utilizes the two SQL queries to visit the corresponding databases simultaneously and obtains the search results, storing them in assigned queues (Figure 1a).

During the search process illustrated above, a special thread is assigned to the current combined search as a monitor. Its main duty is to check the status of the two independent searches and pick up the slower one to take to the dequeue operation. As shown in Figure 1b, the special thread checks that queue A has completed its search task and all satisfactory results have been inserted into queue A. At this point, the front element of queue B goes to the dequeue operation and compares it with the elements from queue A. If the element dequeued from queue B exists in queue A, its ID will be pushed into the temporary result list (ID list) shown in Figure 1c; otherwise, it will be thrown out. When the first match operation is completed, the server loops to reexecute the operation described above until the search of Database B is accomplished and meanwhile queue B is empty. Finally, the process utilizes the ID List to revisit the databases to obtain the complete information for the queried compounds and preserve it in the Result List in Figure 1c.

In a synchronous search process, the database is visited three times: The two single searches plus a third visit to obtain the complete information of the elements in the ID List. Only when the combined search results set is empty does a synchronous search visit a database twice. As an obvious advantage, the relatively fixed frequency of database visits guarantees the efficiency of the combined search to a certain degree. However, its weakness cannot be ignored. In a synchronous search process, both of the individual searches need to scan the whole database no matter how many results the user requests. Additionally, the intersection process of a synchronous search is a time consuming operation compared with an asynchronous search. The specific discussion of this is described in Section 3.

2.2 Asynchronous search strategy

As opposed to the synchronous search strategy, the asynchronous search strategy is concerned with the search sequence. It visits one database first and then utilizes the results as the search limit with which to scan the other database. Taking full advantage of the current results to do the next search significantly narrows the scope of the scan. Meanwhile, as the structure search is a time consuming process, the combined search efficiency will be ameliorated if the waiting time for the structure results can be utilized. Because of this, the structure search is chosen to be operated first in the design. Once the structure search gets a specific quantity of results, the property search will be activated and the structure results will then be used to complete the combined search. The word “asynchronous” here indicates that the visits to the two separated databases are sequenced rather than parallel.

In an asynchronous search process, a queue is used to preserve the molecular structure search results. A List, the same as in the synchronous strategy, is used to organize the final combined search results set; its element is HashTable.

The design of the asynchronous search strategy is shown in Figure 2.

First, the server accepts the query from the user, extracting the structure search section and then putting it into a piece of SQL string. Then the SQL string is used to scan the Molecular Structure Database for the asked for results. The results, which only contain the ID information of the compounds, are maintained in queue C as illustrated in Figure 2.

Then the front element of the obtained queue C is dequeued and combined with the property limitation submitted from the browser to be spelled out in a new SQL query. Next, the server connects to the Compound Basic Property Database with the specified SQL query to get the asked for result and adds it to the Result List noted in Figure 2. Once the operation is completed, the server continues to get the new front element of queue C and connects to the database again. The operation is repeated as above until no elements are left in queue C. However, this is a very time-consuming action if one operation cycle only handles a single element because it needs to connect to the database too many times. Therefore, it is essential to convert the single element work into batches. In this paper, we set the once dequeue element number to be 2000, which reduces connection times and eventually significantly improves the efficient of the combination search as discussed below.

Compared with the synchronous search strategy, the connection time of an asynchronous search is not fixed. Here we set the result numbers to be obtained from the single structure search to be N, the number of dequeued elements in queue C to be σ, and the number of times to connect to the databases to be n. From these we get the formula: $n=\lfloor \frac{N}{\sigma }\rfloor +\lceil \frac{N\%\sigma }{\sigma }\rceil$M1 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[n = \left\lfloor {\frac{N}{\sigma }} \right\rfloor + \left\lceil {\frac{{N\% \sigma }}{\sigma }} \right\rceil \] \end{document} . According to this formula, the larger we set σ, the smaller the n.

However, it is impossible to set σ to an infinite size. Therefore, we set parameter σ to 2000 in consideration of the system’s capability. In different situations, n should be set to different values. This service will only visit the database once when n = 1; if N ≤ σ, then n will equal 2; but if N > σ, then n cannot be specifically defined. In most cases, however, N > σ and n > 3, therefore compared with the synchronous search schema, the frequency of asynchronous search visits to the databases is much greater. On the other hand, an asynchronous search scans the whole database only once, a smaller number than that in a synchronous search operation.

3.1 Experiment design and environment

To cover all retrieval circumstances, we selected a test sample containing 45 queries to check, 4 of which are listed in Table 1. Each query consists of a structure limit section and a property limit section. Based on this, the experiment was designed to use each query to get 3 temporal data records. The amount of time taken to obtain results sets with 20, 50, and 100 records was recorded for further analysis. The query design is in accordance with the following principles:

Table 1

The partial combination queries for the comparison experiment.

NO.	Structure Limit	Search Type	Property Limit	Result Number
1		substructure	Molar Mass [0,200] Formal Charge [0,0] Solubility(logS) S:mol/L [-1,1]	100/50/20
2		substructure	Molar Mass [0,200] Formal Charge [0,0]	100/50/20
3		substructure	Molar Mass [300,500] Formal Charge [0,0] Number of Hydrogen Bond Ligand [1,20]	100/50/20
4		substructure	Molar Mass [100,300] Formal Charge [0,0] Solubility(logS) S:mol/L [-1,1]	100/50/20

First, control the scale of the structure search results. The experiment was designed to employ different substructure queries to cover a variety of structure search results. Twenty-five types of substructure were chosen while the scale of the search results varied from 250 thousand to 20 records.

Second, control the scale of the property search results. A single property search of ChemDB supplied 14 kinds of limits to choose. The design assembled some of the limits and picked up 15 property query records as a test sample. The number of search results ranged from 219,172 to 1,522 records.

Third, the experiments should balance the results scale of the structure search with that of the property search. The 45 test records contained 3 types of queries, a big structure set with a small property set, a small structure set with a big property set, and structure and property sets of equal size; this includes all possible kinds of query circumstances.

Last, the experiment sample should include several controlled test sets in order to explore the factors influencing search efficiency. Because the similar structure search and substructure search differ in their target sets and search measures, it is meaningless to compare their search efficiency. Therefore, our experiment only records the results of the substructure search for analysis.

The whole experiment is based on the environment as follows. The Molecular Structure Database is constructed on the Oracle 11g R2(x64) Edition, and the Basic Property Database is built on the Microsoft SQL Server 2005 Edition. Both DBMSes referred to in the experiment are constructed on a computer with Intel(R) Xeon(R) CPU 5140 and based on the Microsoft Windows Server 2003 R2(x64) operating system. Also, the server computer provides service with the Inter(R) Core(TM) I5–3470 CPU, and the system operation edition is Windows 7 Service Pack 1(x86).

3.2 Results and discussion

The experiment tested 45 combined queries using two combined search strategies and obtained the test results shown in Figure 3. In conclusion, the asynchronous search performed better than the synchronous search in many cases.

Moreover, we recorded the number of single search results and plotted them with the time-cost data in Figure 4. The time data shown in Figure 4 records the time cost of a query asking for 100 result records.

According to an analysis of the results, we can conclude that the following factors influenced search efficiency.

First, the scale of structure search results, that is, the time-cost of the structure search has a great effect on the time-cost of the combined search process for both synchronous and asynchronous searches. According to the results displayed in Figure 4, from query No.1 to No. 4, the number of structure search results decreased greatly and the combined search efficiency increased correspondingly. Compared with the structure search, the variety of property search results quantities has little influence on the combined search efficiency. The main reason for this is that the structure search itself is a time consuming operation.

Second, limiting the number of return results greatly influenced synchronous search efficiency. In contrast, it basically has no influence on the synchronous search process. According to the data shown in Figure 3, it is obvious that increasing the returning records limit makes the time-cost of the synchronous search vary greatly but does not affect the asynchronous search. The time-cost is determined by the search strategy itself. As discussed in Section 2, the frequency of database connections in an asynchronous search process is not defined. When the number of returned records increases, there is a great probability that connection frequency also increases. However, in a synchronous search process, the connection frequency is basically fixed (discussed in Section 2.1), which means that it performs steadily even though the limit on the amount of results changes. In other words, the synchronous search will be superior when the query needs to obtain all satisfactory search results. The experiments have also corroborated this point.

Furthermore, the efficiency of the intersection operation is another factor affecting search performance. According to the introduction of Section 2, under complete results search conditions, the time complexity of a synchronous search is O(MN), where M stands for the number of property search results and N refers to the number of structure search results. As for an asynchronous search, it only consumes O(N) time complexity to complete a search process. In this regard, the asynchronous search performs better.

In summary, the scale of the structure results greatly influences both synchronous and asynchronous searches while the efficiency of the asynchronous search is influenced by the number of requested results.