Stanford InfoLab Publication Server

Filtering with approximate predicates

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.




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
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