Using local optimality criteria for efficient information retrieval with redundant information filters
By: by Neil C. Rowe
Contributors: Naval Postgraduate School (U.S.). Dept. of Computer Science
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1994
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 35
Subjects: INFORMATION RETRIEVAL; OPTIMIZATION; FILTER ANALYSIS; INFORMATION THEORY; MATHEMATICAL FILTERS
Other titles: NPS-CS-94-004.
Description: We 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. Then decisions 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 numbers 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, 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 captioned data using      natural-language understanding, a problem for which the natural-language processing can be      the bottleneck if not implemented well. Filters, Optimization, Queries, Conjunction, Boolean      algebra, Natural lan guage.
Notes: Cover title.

"NPS-CS-94-004."

"March 1994."

AD A279 603.

Includes bibliographical references (p. 28-29).