Using local optimality criteria for efficient information retrieval with redundant information filters

摘要: We consider information retrieval when the data—for instance, multimedia—is computationally expensive to fetch. Our approach uses “information filters” considerably narrow universe of possibilities before retrieval. are especially interested in redundant filters that save time over more general but costly filters. Efficient requires decisions must be made about necessity, order, and concurrent processing proposed (an “execution plan”). develop simple polynomial-time local criteria for optimal execution plans show most forms concurrency suboptimal with Although problem finding an plan is likely exponential number filters, we experimentally our optimality criteria, used a algorithm, nearly always find global optimum 15 or less, sufficient applications. methods require no special hardware avoid high processor idleness characteristic massive-parallelism solutions this problem. apply ideas important application, captioned data using natural-language understanding, which can bottleneck if not implemented well.