On two-dimensional data organization I¹

Article type: Research Article

Authors: Lodi, E. | Luccio, F. | Mugnai, C. | Pagli, L.

Affiliations: Istituto di Scienze dell’Informazione, Università di Pisa

Note: [1] This work has been supported in part by Consiglio Nazionale delle Ricerche of Italy, under grant No. 75.01035.01.

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: information storage and retrieval, bidimensional memory, figure description, minimal description, prime rectangle

DOI: 10.3233/FI-1978-2114

Journal: Fundamenta Informaticae, vol. 2, no. 1, pp. 211-226, 1978