Kris Hildrum and Megan Thomas

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-99-1060

, 1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1060.pdf

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.

---

BibTeX citation:

@techreport{Hildrum:CSD-99-1060,
    Author= {Hildrum, Kris and Thomas, Megan},
    Title= {Jagged Bite Problem NP-Complete Construction},
    Year= {1999},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5805.html},
    Number= {UCB/CSD-99-1060},
    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.},
}

EndNote citation:

%0 Report
%A Hildrum, Kris 
%A Thomas, Megan 
%T Jagged Bite Problem NP-Complete Construction
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1060
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5805.html
%F Hildrum:CSD-99-1060