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},
    Institution = {EECS Department, University of California, Berkeley},
    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