Using Local Optimality Criteria for Efficient Information Retrieval with Redundant Information Filters
Rowe, Neil C.
MetadataShow full item record
We consider information retrieval when the data, for instance multimedia, is coputationally expensive to fetch. Our approach uses "information filters" to considerably narrow the universe of possiblities before retrieval. We are especially interested in redundant information filters that save time over more general but more costly filters. Efficient retrieval requires that decision must be made about the necessity, order, and concurrent processing of proposed filters (an "execution plan"). We develop simple polynomial-time local criteria for optimal execution plans, and show that most forms of concurrency are suboptimal with information filters. Although the general problem of finding an optimal execution plan is likely exponential in the number of filters, we show experimentally that our local optimality criteria, used in a polynomial-time algorithm, nearly always find the global optimum with 15 filters or less, a sufficient number of filters for most applications. Our methods do not require special hardware and avoid the high processor idleness that is characteristic of massive parallelism solutions to this problem. We apply our ideas to an important application, information retrieval of cpationed data using natural-language understanding, a problem for which the natural-language processing can be the bottleneck if not implemented well.
This paper appeared in ACM Transactions on Information Systems, 14, no. 2 (April 1996), 138-174.
Showing items related by title, author, creator and subject.
Using local optimality criteria for efficient information retrieval with redundant information filters Rowe, Neil C. (Monterey, California. Naval Postgraduate School, 1994-03); NPS-CS-94-004We consider information retrieval when the data, for instance multimedia, is computationally expensive to fetch. Our approach uses information filters to considerably narrow the universe of possibilities before retrieval. ...
Luqi; Goguen, Joseph; Nguyen, Doan; Messeguer, Jose; Zhang, Du; Berzins, Valdis (1996);An important problem in software development is to make better use of software libraries by improving the search and retrieval process, that is, by making it easier to find the few components you may want among the many ...
Rowe, Neil C. (Monterey, California. Naval Postgraduate School, 1993-10); NPS-CS-94-008We describe MARIE-1 and MARIE-2, information retrieval systems for multimedia data. They exploit captions on the data and perform natural-language processing of them and English retrieval requests. Some content analysis ...