PERFORMANCE ANALYSIS OF 3 TEXT-JOIN ALGORITHMS

When a multidatabase system contains textual database systems (i.e., i nformation retrieval systems), queries against the global schema of th e multidatabase system may contain a new type of joins-joins between a ttributes of textual type. Three algorithms for processing such a type of joins are presented and their I/O costs are analyzed in this paper . Since such a type of joins often involves document collections of ve ry large size, it is very important to find efficient algorithms to pr ocess them. The three algorithms differ on whether the documents thems elves or the inverted files on the documents are used to process the j oin. Our analysis and the simulation results indicate that the relativ e performance of these algorithms depends on the input document collec tions, system characteristics, and the input query. For each algorithm , the type of input document collections with which the algorithm is l ikely to perform well is identified. An integrated algorithm that auto matically selects the best algorithm to use is also proposed.