Abstract
Two-dimensional sequential data organization is considered, where each dimension corresponds to one of two attributes. A query on the data is a figure on the storage. The elementary figure is a rectangle, and any figure can be described by a set of rectangles.
Prime rectangles are defined as the ones relevant to any figure description, and the problem of finding a minimal description is studied. In particular, the upper bound to the number of prime rectangles is derived, and a cubic algorithm to find all such rectangles is given.
Descriptions composed of all disjoint rectangles are the subject of the second part or this paper.
Keywords
Get full access to this article
View all access options for this article.