Zhixiang Chen, Xiannong Meng, and Richard Fowler
In this paper we study the problem of designing intelligent search engines with machine learning techniques. An intelligent search engine should be able to interact with the user and learn to refine its search process and find the desired documents for the user with as few queries as possible. In spite of the growing populairty of existing search engines, little is known about the following fundamental problem: How many queries are needed to search for a collection of documents represented by a disjunction (or a conjunction) of attributes? Algorithmic solutions to the above question not only have theoretical significance but may also be used in implementing search engines. We consider that web documents can be represented by vectors of boolean attributes. We design several algorithms for searching any collection of documents represented by a disjunction (or a conjunction) of relevant attributes with the help of membership queries (or equivalencequeries).