Patent ID: 6282533
Filing Date: 2001-08-28
Classification: G06F,Y10S

Abstract:
A method for performing a d-dimensional join between a first set and a second set of hyper-rectangles, at least one of said first set and said second set being stored in secondary memory, comprising the steps of:dividing the d-dimensional join into k d-dimensional join strips and a (d-1)-and-a-half dimensional join;classifying hyper-rectangles within said strips as large if they are contained in more than a single strip and small if they are contained within said single strip;partitioning each large hyper-rectangle into one center piece and two end pieces;recursively computing intersections between a first type from said first set and a second type from said second set, wherein each of said first type and said second type is one selected from a group consisting of said end pieces and said small hyper-rectangles;computing intersections between center pieces from said first set and second set and with said small hyper-rectangles from said first set and said second set by partitioning said (d-1)-and-a-half dimensional join along d-1 dimensions and by processing through said steps of dividing, classifying, partitioning and recursively computing intersections for each of said d-2 dimensions; andreporting to the secondary memory all computed intersections.