|
Abstract : |
A hyper-rectangle is commonly used as a bounding predicate in tree-based access methods in databases. To reduce the number of I/O's per query, we would like to reduce the volume of this bounding predicate by cutting chunks out of the corners of the bounding hyper-rectangle. Ideally, one would like to remove the largest hyper-rectangular chunk that does not contain any points. In this paper, we formalize the problem and then show that the problem of finding the largest possible chunk is NP-complete. We accomplish this through a reduction from 3-SAT to our problem. The Jagged-Bites Problem The Jagged-Bites problem, defined after we provide some background, is significant to a database access method designer working with nearest neighbor queries because of the way that such queries interact with rectangular bounding predicates (BPs). It was first suggested in [1]. Nearest neighbor queries work by finding points within a given distance of the query point, in essence asking expanding hyper-sphere queries. Figure 1 depicts a rectangular, 2-D BP and the circles of nearest neighbor queries. If the query point is in the middle of a BP, it does not matter how small the BP volume is; this node will be accessed. However, nearest neighbor queries starting from points just outside, |
