EP0170443A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for searching an association matrix
Assignee: Alcatel Lucent NV
•
Filing: 1985-07-09
•
Granted: —
•
Expires: 2005-07-09
Abstract
Abstract 57 A method is provided for searching an association matrix using associative searching techniques. The method contemplates the use of two types of data structures. Firstly, a data structure for locating a particular instance or component in a matrix. Secondly, an associative matrix representing the relationship of the components or instances to one another. The search method requires searching the first data structure to determine the position of the component in the association matrix. The appropriate portion of the matrix is then addressed and horizontal and vertical masks are established for manipulation of the data in the matrix using an associative array processor. Utilising the masks the association matrix may be traversed both vertically and horizontally to identify the desired relationships. The method uniquely takes advantage of the architecture of an associative array processor to provide for the simultaneous searching of rows or columns in response to a single instruction. Thus, the method significantly reduces the search time making the use of association matrices practical along with the reduced storage requirements of such matrices.
Inventors
- 👤 Ruven Edward Brooks
- 👤 Rosalyn Kam Lin Lum
- 👤 John Michael Cotton
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-08 22:28
CPC Classifications
G; G06; G06F; G06F17/00; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339; G06F16/901; G06F16/9017
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
156 words
A method of searching for relationships between a selected object and other objects in an association matrix of the type that stores relationships between objects, each object being represented by both a row and column of the matrix, each relationship being predefined and associated with one of the axes of the matrix, the existence of a relationship between objects being signified by a 1 at the intersection of the row of one object and the column of another object, the method being implemented on an associative array processor using associative searching techniques and characterised in the steps of identifying the row and column position of a selected object to be searched in the association matrix and searching in parallel each row under the column identified with the selected object or searching each column in a row identified with the selected object to identify one of the predetermined relationships between the selected object and the other objects.
Claim 2
Independent Claim
156 words
A method of searching for relationships between a selected object and other objects in an association matrix of the type that stores relationships between objects, each object being represented by both a row and column of the matrix, each relationship being predefined and associated with one of the axes of the matrix, the existence of a relationship between objects being signified by a 1 at the intersection of the row of one object and the column of another object, the method being implemented on an associative array processor using associative searching techniques and characterised in the steps of identifying the row and column position of a selected object to be searched in the association matrix and searching in parallel each row under the column identified with the selected object or searching each column in a row identified with the selected object to identify one of the predetermined relationships between the selected object and the other objects.
Claim 3
Dependent Claim
53 words
A method as claimed in claim 1, characterised in that each row under the column associated with the selected object is searched in parallel to identify the relationship associated with the columns and each column in a row is searched in parallel to identify the relationship represented by the rows in the matrix.
Claim 4
Dependent Claim
48 words
A method as claimed in claim 1, characterised in that each row in the column identified with the selected object is searched in parallel through the use of a vertical mask which restricts operation of the associative array processor to one or more selected columns of the matrix.
Claim 5
Dependent Claim
55 words
A method as claimed in claim 1 or 2, characterised in that each column in the row identified with the selected object is searched in parallel through the use of a horizontal mask which is set up to restrict the operation of the associative array processor to one or more selected rows of the matrix.
Claim 6
Dependent Claim
39 words
A method as claimed in claim 3, characterised in that a single column of the matrix is searched for positions having bits set to 1 through the use of a vertical mask which enables only the single selected column.
Claim 7
Dependent Claim
41 words
A method as claimed in claim 4, characterised in that a single row of the matrix is searched for positions having any bits set to 1 through the use of a horizontal mask enabling the single selected row of the matrix.
Claim 8
Dependent Claim
71 words
A method as claimed in claim 6, characterised in that the positions of the bits set to 1 in given row are used to identify objects associated with those columns of the association matrix and to thereby identify the relationship associated with the row axes of the matrix as existing between the selected object and the objects associated with each of the columns that have a 1 in the given row.
Claim 9
Dependent Claim
68 words
A method as claimed in claim 5, characterised in that the positions of the bits set to 1 in given column identify the objects associated with those rows of the association matrix and to identify the relationship associated with the column axes of the matrix as existing between the selected object and the objects associated with each of the rows that have a 1 in the given column.
Claim 10
Dependent Claim
30 words
A method as claimed in claim 1, characterised in the step of enabling the rows or columns identified in the search for conducting a second iteration of the search method.
Claim 11
Dependent Claim
41 words
A method as claimed in claim 9, characterised in that set to 1 in a given row are used to form a horizontal mask to enable the rows that are to be searched in a next iteration of the search method.
Claim 12
Dependent Claim
45 words
A method as claimed in claim 9, characterised in the step of using the bits found set to 1 in a given column to form a vertical mask to enable the columns which are to be searched in a next iteration of the search method.
Claim 13
Dependent Claim
27 words
A method as claimed in claim 9, characterised in the steps of searching the association matrix repeatedly to identify a set of hierarchical relationships between the objects.
Claim 14
Independent Claim
157 words
A method of searching for relationships between a selected object and other objects in an association matrix of the type that stores relationships between objects, each object being represented by both a row and a column of the matrix, each said relationship being predefined and associated with one of the axes of the matrix, the existence of a relationship between the objects being signified by a 1 at the intersection of the row of one object and the column of another object, said method being implemented on an associative array processor using associative searching techniques and characterised in the steps of identifying the row and column of the selected object in the association matrix; setting up appropriate masks for the identified row and column in order to manipulate the data in the associated matrix; and traversing the association matrix using said masks to identify relationships between the selected object and the other objects of the association matrix.
Claim 15
Independent Claim
157 words
A method of searching for relationships between a selected object and other objects in an association matrix of the type that stores relationships between objects, each object being represented by both a row and a column of the matrix, each said relationship being predefined and associated with one of the axes of the matrix, the existence of a relationship between the objects being signified by a 1 at the intersection of the row of one object and the column of another object, said method being implemented on an associative array processor using associative searching techniques and characterised in the steps of identifying the row and column of the selected object in the association matrix; setting up appropriate masks for the identified row and column in order to manipulate the data in the associated matrix; and traversing the association matrix using said masks to identify relationships between the selected object and the other objects of the association matrix.
Claim 16
Dependent Claim
18 words
An association matrix arranged to operate in accordance with the method of any one of the preceding claims.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.