Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A space-efficient representation of alias information based on interval trees

IP.com Disclosure Number: IPCOM000198617D
Publication Date: 2010-Aug-10
Document File: 4 page(s) / 217K

Publishing Venue

The IP.com Prior Art Database

Abstract

A common alias set is a set of symbols that is included in the alias sets of multiple symbols. The invention presents a space-efficient representation of common alias sets as intervals in a one-dimensional space, and a space-efficient and time-efficient mechanism for maintaining references to such sets using interval trees.

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 36% of the total text.

Page 1 of 4

A space-efficient representation of alias information based on interval trees

Disclosed is a process providing a capability for a space-efficient and time-efficient representation of common alias sets. A common alias set may be defined as a set of symbols included in alias sets of more than one symbol. The disclosed process comprises a portion representing common alias sets as intervals (I1), another portion organized in an overlapping arrangement in a one-dimensional space, including references to intervals instead of an entire (common) set in another alias set, represented as (I2) and interval trees to maintain references to common alias sets, represented by (I3). Unlike previous solutions1, the disclosed process does not restrict common sets to represent equivalence classes using alias relation, resulting in improved space efficiency . In addition, the disclosed process uses intervals and interval trees to allow time-efficient operations on alias sets.

Figure 1

Figure 1, depicts in an illustrative embodiment, a compilation process incorporating component

portions representative of the disclosed process. Components of Figure 1 with thick borders

implement the disclosed process. Service routines isolate the interval representation (I1) from the rest of the compilation process. A

preprocesso

r

constructs intervals (the common sets) using

information from a

parse

r

. The computation and propagation

phase constructs regular alias sets.

The

service routines

             construct interval trees (represented as I2 and I3) using requests from the computation and propagation sub-component and the optimizer .

Figure 2 illustrates major components of a data structure. A dynamical array S represents a one-dimensional space in which each element can store a reference to a dictionary symbol. An interval

I

is a contiguous part of S , identified by a start index

I

and an end index

I

in S .

s

e

Symbolic references S [

I

],..., S [

I

] constitute a common alias set represented by interval

I

. An

s

e

          is a one dimensional, dynamical array in which each element stores metadata information (the start and end indices, for example) associated with a particular interval. A reference to an interval S [

I

interval list

IL

],..., S [

I

] is an index

L

into

IL

such that

L

stores metadata

s

e

(

Is

,

Ie

)

(

Is

,

Ie

)

information for an interval of interest.

Pe

r-

symbol interval sets

                                      associate intervals (such as descendant/ancestor intervals, and must alias sets) with a symbol. Per-symbol interval sets are typically implemented using a dynamic array, or a standard linked-list. Each element of a

pe

r-symbol interval set is an interval reference. An

                              alias set is a collection of references to dictionary symbols, and intervals. A typical data structure, such as hash table, can be used for a

1

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

Page 2 of 4

collection of references to dictionary symbols. A collection of references to intervals is maintained in an interval...