Shivakumar, N. and Garcia-Molina, H. and Chekuri, C. (1998) Filtering with approximate predicates. In: 24rd International Conference on Very Large Data Bases (VLDB 1998), August 24-27, 1998, New York, NY.
BibTeX | DublinCore | EndNote | HTML |
| PDF 316Kb |
Abstract
Approximate predicates can be used to reduce the number of comparisons made by expensive, complex predicates. For example, to check if a point is within a region (expensive predicate) we can first check if the point is within a bounding rectangle (approximate In general, approximate predicates may have false positive and false negative errors. In this paper we study the problem of selecting and structuring approximate predicates in order to reduce the cost of processing a user query, while keeping errors within user-specified bounds. We model different types of approximate predicates and their dependencies, we derive expressions for the errors of compound predicates, and we develop query optimization strategies. We also study the complexity of our optimization strategies under various scenarios, and we present an experimental case study that illustrates the potential gains achieved by optimizing queries with approximate predicates
Item Type: | Conference or Workshop Item (Paper) | |
---|---|---|
Uncontrolled Keywords: | Expensive predicates, SCAM, multi-media databases, extensible databases, approximate predicates | |
Subjects: | Computer Science > Digital Libraries | |
Projects: | Digital Libraries | |
Related URLs: | Project Homepage | http://www-diglib.stanford.edu/diglib/pub/ |
ID Code: | 351 | |
Deposited By: | Import Account | |
Deposited On: | 25 Feb 2000 16:00 | |
Last Modified: | 29 Dec 2008 09:40 |
Download statistics
Repository Staff Only: item control page