Optimizing source-call ordering in information gathering plans
Subbarao Kambhampati, Senthil Gnanaprakasam · 1999
In this paper we consider the problem of optimizing the order in which source relations are joined in information gathering plans. This problem differs significantly from the traditional database query optimization problem, as sources on the Internet have a variety of access limitations and the execution cost in information gathering is affected both by network traffic and by the connection setup costs. We describe a way of representing the access capabilities of sources, and provide a greedy algorithm for ordering source calls that respects source limitations. Our algorithm also takes both access costs and traffic costs into account, without requring full source statistics. This algorithm is being evaluated in the context of Emerac, our prototype information gathering system. Introduction One way of modeling the task of gathering information on the Internet involves building a virtual global schema for the information that the user is interested in, and describing the ac...