Browse Prior Art Database

GENERALIZED ADDRESSING SCHEMES FOR DATA GRAPHS

IP.com Disclosure Number: IPCOM000148465D
Original Publication Date: 1973-May-08
Included in the Prior Art Database: 2007-Mar-30
Document File: 32 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Rosenberg, A.L.: AUTHOR [+2]

Abstract

. Research -c-- GENERALIZED ADDRESSING SCHEMES FOR DATA GRAPHS A. L. Rosenberg -a- Dcpar:r; cF May 8,1973 Alee q' ,, 23 : .'. .. : ...... ,, I RC 4342 WE#! liIAti'2 it ilY; ,, ;bit iC2P Od5M , . .. ,.. Yorktown Heights,New York San Jose,California GENERALIZED ADDRESSING SCHEIrnS FOR DATA GRAPHS ? Arnold L. Rosenberg Mathematical Sciences Department IBM Thomas J. Watson Research Center Yorktown Heights, New York 10598 ABSTRACT Addressable data graphs enjoy structural properties which are at once mathematically attractive and practically useful. This paper is devoted to studying generaliztions of addressability, with a twofold goal. The first aim of the paper is to gain understanding of what features of addressing schemes account for the attractive properties of addressable data graphs. The second purpose of the paper is to seek a variant ofthe property of addressability, which retains the practical concomitants of the original property, but which is enjoyed by a broader class of data graphs. Two such variants are discovered, quasi-addressability and weak- addressability. Although "most" data graphs do not enjoy any form of addressability, every data graph can be sli~htlymodified to render it quasi or weakly addressable--in sharp contrast to the stringent demands of addressability. However, the added breadth of these new address- abilities is obtained at the expense of the invariance and selectivity which accompany the original property.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 32

--- -

--- -

- - - ---
-----
-- - . - Research

- - --

- -

- -c--

GENERALIZED ADDRESSING SCHEMES FOR DATA GRAPHS
A. L.
Rosenberg

-a-

Dcpar:r; - cF --

May 8,1973 Alee

q'

,,

23 : .'. .. : ...... ,, I

RC 4342 WE#! liIAti'2 it ilY; ,, ;bit iC2P Od5M

, . .. ,..

Yorktown Heights,New York San Jose,California

[This page contains 1 picture or other non-text object]

Page 2 of 32

GENERALIZED ADDRESSING SCHEIrnS FOR DATA GRAPHS

? Arnold L. Rosenberg

* Mathematical Sciences Department

IBM Thomas J. Watson Research Center
Yorktown Heights, New York 10598

ABSTRACT
Addressable data graphs enjoy structural properties which are at once
mathematically attractive and practically useful. This paper is devoted
to studying generaliztions of addressability, with a twofold goal. The
first aim of the paper is to gain understanding of what features of
addressing schemes account for the attractive properties of addressable
data graphs. The second purpose of the paper is to seek a variant of
the property of addressability, which retains the practical concomitants
of the original property, but which is enjoyed by a broader class of data
graphs. Two such variants are discovered, quasi-addressability and weak-
addressability. Although "most" data graphs do not enjoy any form of
addressability, every data graph can be sli~htly
modified to render it
quasi or weakly addressable--in sharp contrast to the stringent demands
of addressability. However, the added breadth of these new address-
abilities is obtained at the expense of the invariance and selectivity
which accompany the original property.

RC 4342 (No. 19424)

May 8,1973
Mathematics

*This research was supported in part by ONR Contract N00014-69-C-0023

[This page contains 1 picture or other non-text object]

Page 3 of 32

[This page contains 1 picture or other non-text object]

Page 4 of 32

1. INTRODUCTION
Addressing schemes for data graphs were introduced in 131 as one device

(among many) for characterizing algebraically the family of data structures
which admit realization in a random access memory via relative addressing. (1)
Addressable data graphs (those which admit addressing schemes) were shown
(in [3,4]) to enjoy a rqther rich mathematical structure. The purpose of
this note is twofold. First, we wish to study generalizations of addressing
schemes so as to gain insight into those features of addressing schemes
which account for the structural properties of addressable data graphs
uncovered in [3,4]. The second goal of the current work derives from the
demonstration in I51 that the "addresses" assigned to a data graph by an
addressing scheme can be exploited to practical ends when allocating storage
for the data graph. Our aim is to discover types of addressing schemes which

L yield an exploitable structure similar to addresses, but which are applicable
to broader classes of data graphs than the addressable data graphs....