EP0170442A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method for searching sparse databases using an associative technique
Assignee: Alcatel Lucent NV
•
Filing: 1985-07-09
•
Granted: —
•
Expires: 2005-07-09
Abstract
Abstract 57 A method is provided for searching sparse databases using associative searching techniques wherein portions of the database are simultaneously searched by comparing a selected value to be searched for with values stored within the portions. Each portion of the database is further refined into sub-portions said sub-portions being simultaneously searched by comparing the values stored therein with the selected value. Searching performance is improved in both the area of search speed and the ease with which the stored values may be updated. The method uniquely takes advantage of the architecture of an associative array processor to provide the simultaneous searching.
Inventors
- 👤 John Michael Cotton
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 06:09
CPC Classifications
G; G06; G06F; G06F17/00; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339; G06F16/901; G06F16/9024
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
79 words
A method of searching for a selected value in a sparsely occupied database in which similar values are stored, using an associative array processor, the method using associative matching techniques characterised in the steps of selecting a portion of the database to be searched, concurrently searching records contained in said portion of the database, and identifying in the records the selected value or a pointer to another portion of the database within which the selected value should be located.
Claim 2
Independent Claim
79 words
A method of searching for a selected value in a sparsely occupied database in which similar values are stored, using an associative array processor, the method using associative matching techniques characterised in the steps of selecting a portion of the database to be searched, concurrently searching records contained in said portion of the database, and identifying in the records the selected value or a pointer to another portion of the database within which the selected value should be located.
Claim 3
Dependent Claim
33 words
A method as claimed in claim 1, characterised in the step of concurrently searching includes a step of comparing the selected value with one or more values contained in each of the records.
Claim 4
Dependent Claim
46 words
A method as claimed in claim 2, characterised in that the step of comparing the selected value with one or more values stored in each record comprises the step of comparing the selected value with a maximum and a minimum value stored in each searched record.
Claim 5
Dependent Claim
97 words
A method as claimed in claim 3, characterised in that the step of comparing the maximum and minimum values of each record with the selected value comprises the steps of concurrently comparing the selected value with one of said maximum and minimum values of all records, using the results of said comparisons to identify selected ones of said records for further search, and comparing the selected value with the other of said maximum and minimum values of all selected records, whereby the selected value is identified or a pointer to another portion of the database is identified.
Claim 6
Independent Claim
155 words
A method of organising a sparsely occupied database for storing a range of values in an associative array processor, the method characterised in the steps of partitioning the range of values to be stored into blocks, identifying for each block a set of upper and lower boundary values for the block, storing the sets as records in a table stored in the database, further partitioning the range of values contained within each of the blocks into sub-blocks, identifying the sets of values for the upper and lower boundaries of each of the sub-blocks, entering the sets of upper and lower boundary values of the sub-blocks of each prior block as records in a set of subsequent tables stored in the database, there being a subsequent table for each prior block, identifying the addresses of the subsequent tables, and entering the addresses of the subsequent tables into the corresponding records contained in the next higher table.
Claim 7
Independent Claim
155 words
A method of organising a sparsely occupied database for storing a range of values in an associative array processor, the method characterised in the steps of partitioning the range of values to be stored into blocks, identifying for each block a set of upper and lower boundary values for the block, storing the sets as records in a table stored in the database, further partitioning the range of values contained within each of the blocks into sub-blocks, identifying the sets of values for the upper and lower boundaries of each of the sub-blocks, entering the sets of upper and lower boundary values of the sub-blocks of each prior block as records in a set of subsequent tables stored in the database, there being a subsequent table for each prior block, identifying the addresses of the subsequent tables, and entering the addresses of the subsequent tables into the corresponding records contained in the next higher table.
Claim 8
Dependent Claim
32 words
A method as claimed in claim 5, characterised in that additional sub-blocks are created along with additional sets of subsequent tables until there is sufficient storage for the values to be stored.
Claim 9
Dependent Claim
84 words
A method of searching for a selected value in a database organised as claimed in claim 5, characterised in the steps of comparing the selected value with all of the upper and lower boundary values stored in the records of the table, identifying the record wherein the upper boundary value is larger than and the lower boundary value is smaller than the selected value, identifying the address associated with the record, and addressing a subsequent table containing finer partitions of the previously identified block.
Claim 10
Dependent Claim
21 words
A method as claimed in claim 5, characterised in that the records in the table are - placed in random sequence.
Claim 11
Dependent Claim
51 words
A method as claimed in claim 7, characterised in that additional values are stored in their proper sub-blocks by performing the searching process using the new values as the selected value and identifying the finest sub-block which does not contain the new value and adding the new value into that sub-block.
Claim 12
Dependent Claim
118 words
A method as claimed in claim 9, characterised in the additional steps of determining that the new value will not fit in the space available in the finest sub-block, creating a new sub-block having a new range of values equal to a portion of the range of values of the old sub-block, shifting the new values from the old sub-block to the new sub-block leaving the remaining values in the old sub-block, changing the range of values in the records of the next higher table to reflect their reduced. range, and add new records to the next higher table for the new range of values including the address for the sub-block, whereby space becomes available for new values.
Claim 13
Dependent Claim
20 words
A data base arranged to operate in accordance with the method as claimed in 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.