Patent US3098490A successfully refreshed from Google Patents.
Patent US747029A successfully refreshed from Google Patents.
Patent US5848416A successfully refreshed from Google Patents.
US5848416A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for storing and retrieving data and a memory arrangement
Assignee: Nokia Oyj
•
Filing: 1995-06-05
•
Granted: 1998-12-08
•
Expires: 2015-06-05
Abstract
Abstract In methods for storing and retrieving data with a memory arrangement and central databases, a trie data structure is utilized in which the nodes are given unique multidimensional search keys in order to save memory space and to easily store and retrieve data, as a result, the efficiency of storage management will be highly improved.
Inventors
- 👤 Matti Tikkanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 05:18
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9027; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
279 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node containing at least one pointer to a stored data unit, the steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered or until the address of the new node and at a lower level is the address of a leaf node, (d) storing a pointer in the leaf node and said data unit at the storage location indicated by the pointer.
Claim 2
Independent Claim
279 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node containing at least one pointer to a stored data unit, the steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered or until the address of the new node and at a lower level is the address of a leaf node, (d) storing a pointer in the leaf node and said data unit at the storage location indicated by the pointer.
Claim 3
Dependent Claim
21 words
A method as claimed in claim 1, wherein: a new leaf node wherein storage is performed is created after step (c).
Claim 4
Dependent Claim
43 words
A method as claimed in claim 1, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has equal depth in the direction of all dimensions and hence will favor partial key retrievals equitably in all directions.
Claim 5
Dependent Claim
45 words
A method as claimed in claim 1, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has greater depth in the direction of a given dimension/given dimensions and hence will favor partial key retrievals in that direction/those directions.
Claim 6
Dependent Claim
56 words
A method as claimed in claim 1, wherein: the search word is formed by setting the bits selected from the search key of each dimension in succession and interpreting the bit string thus obtained as a number indicating in the array of the internal node the element wherefrom the address of a lower node is sought.
Claim 7
Independent Claim
268 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node in which at least one data unit is stored, comprising the steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered or until the address of the new node at a lower level is the address of a leaf node, and (d) storing said data unit in the leaf node.
Claim 8
Independent Claim
268 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node in which at least one data unit is stored, comprising the steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered or until the address of the new node at a lower level is the address of a leaf node, and (d) storing said data unit in the leaf node.
Claim 9
Dependent Claim
21 words
A method as claimed in claim 6, wherein: a new leaf node wherein storage is performed is created after step (c).
Claim 10
Dependent Claim
43 words
A method as claimed in claim 6, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has equal depth in the direction of all dimensions and hence will favor partial key retrievals equitably in all directions.
Claim 11
Dependent Claim
45 words
A method as claimed in claim 6, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has greater depth in the direction of a given dimension/given dimensions and hence will favor partial key retrievals in that direction/those directions.
Claim 12
Dependent Claim
56 words
A method as claimed in claim 6, wherein: the search word is formed by setting the bits selected from the search key of each dimension in succession and interpreting the bit string thus obtained as a number indicating in the array of the internal node the element wherefrom the address of a lower node is sought.
Claim 13
Independent Claim
295 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding on the basis of a search key in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node containing at least one pointer to a stored data unit, comprising the following steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ,) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered, until the address of the new node at a lower level is the address of a leaf node or until all bits of the search key have been selected, and if an empty element was not encountered in step (c), (d) reading from the leaf node the pointer contained therein and reading the data unit at the location indicated by the pointer.
Claim 14
Independent Claim
295 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding on the basis of a search key in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node containing at least one pointer to a stored data unit, comprising the following steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ,) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered, until the address of the new node at a lower level is the address of a leaf node or until all bits of the search key have been selected, and if an empty element was not encountered in step (c), (d) reading from the leaf node the pointer contained therein and reading the data unit at the location indicated by the pointer.
Claim 15
Dependent Claim
43 words
A method as claimed in claim 11, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has equal depth in the direction of all dimensions and hence will favor partial key retrievals equitably in all directions.
Claim 16
Dependent Claim
45 words
A method as claimed in claim 11, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has greater depth in the direction of a given dimension/given dimensions and hence will favour partial key retrieval in that direction/those directions.
Claim 17
Dependent Claim
56 words
A method as claimed in claim 11, wherein: the search word is formed by setting the bits selected from the search key of each dimension in succession and interpreting the bit string thus obtained as a number indicating in the array of the internal node the element wherefrom the address of a lower node is sought.
Claim 18
Independent Claim
284 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding on the basis of a search key in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node in which at least one data unit is stored, comprising the steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered, until the address of the new node at a lower level is the address of a leaf node or until all bits of the search key have been selected, and if an empty element was not encountered in step (c), (d) reading from the leaf node one or more data units contained therein.
Claim 19
Independent Claim
284 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding on the basis of a search key in a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be an internal node comprising a multidimensional array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, or a leaf node in which at least one data unit is stored, comprising the steps of: (a) selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which the address of the next node is sought from the internal node at the root level of the tree-shaped hierarchy, and proceeding to said node, (b) selecting from the unselected bits in the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, (c) repeating step (b) until an empty element has been encountered, until the address of the new node at a lower level is the address of a leaf node or until all bits of the search key have been selected, and if an empty element was not encountered in step (c), (d) reading from the leaf node one or more data units contained therein.
Claim 20
Dependent Claim
43 words
A method as claimed in claim 15, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has equal depth in the direction of all dimensions and hence will favor partial key retrievals equitably in all directions.
Claim 21
Dependent Claim
45 words
A method as claimed in claim 15, wherein: said dimension-specific number (k i ) is selected in such a way that the structure has greater depth in the direction of a given dimension/given dimensions and hence will favor partial key retrievals in that direction/those directions.
Claim 22
Independent Claim
149 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual element may contain a pointer to a data unit or wherein an individual element may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing a pointer in the element and said data unit at the storage location indicated by the pointer.
Claim 23
Independent Claim
149 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual element may contain a pointer to a data unit or wherein an individual element may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing a pointer in the element and said data unit at the storage location indicated by the pointer.
Claim 24
Dependent Claim
40 words
A method as claimed in claim 18, wherein: the search word is formed by setting the bits selected from the search key of each dimension in succession and interpreting the bit string thus obtained as a number indicating said element.
Claim 25
Independent Claim
135 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual element may contain a data unit or wherein an individual element may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing the data unit in said element.
Claim 26
Independent Claim
135 words
A method for storing data identifiable by a search key in memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein storage is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual element may contain a data unit or wherein an individual element may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing the data unit in said element.
Claim 27
Dependent Claim
40 words
A method as claimed in claim 20, wherein: the search word is formed by setting the bits selected from the search key of each dimension in succession and interpreting the bit string thus obtained as a number indicating said element.
Claim 28
Independent Claim
149 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual node may contain a pointer to said data unit or wherein an individual node may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific (k i ) number of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing a pointer in said element and the data unit at the storage location indicated by the pointer.
Claim 29
Independent Claim
149 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual node may contain a pointer to said data unit or wherein an individual node may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific (k i ) number of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing a pointer in said element and the data unit at the storage location indicated by the pointer.
Claim 30
Dependent Claim
40 words
A method as claimed in claim 22, wherein: the search word is formed by setting the bits selected from the search key of each dimension in succession and interpreting the bit string thus obtained as a number indicating said element.
Claim 31
Independent Claim
135 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual element may contain a data unit or wherein an individual element may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing the data unit in said element.
Claim 32
Independent Claim
135 words
A method for retrieving data identifiable by a search key from memory, the data being stored as data units in a dedicated storage space assigned for each data unit, wherein retrieval is performed by proceeding, on the basis of a search key associated with the data unit to be stored, in a directory structure having one node comprising a multidimensional array wherein an individual element may contain a data unit or wherein an individual element may also be empty, comprising the steps of: selecting from the search key related to each dimension a predetermined dimension-specific number (k i ) of bits and forming therefrom a search word on the basis of which an element is sought from the array of the node, and if said element is empty, storing the data unit in said element.
Claim 33
Dependent Claim
202 words
An associative memory arrangement for storing data in electrical form, the data being stored as data units in a dedicated storage space assigned for each data unit in the memory, the memory arrangement comprising a directory structure which is a multidimensional digital trie structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein a node can be an internal node comprising a multidimensional array wherein an individual non-empty element comprises a pointer (31) guiding progress in the directory structure, or a leaf node containing one or more pointers to a data unit stored in the memory, each data unit to be stored in the memory being associated with a multidimensional search key comprising a search key for each dimension, on the basis of which search keys progress is made in the directory structure, the directory structure returning the data unit associated with the multidimensional search key employed in each case, wherein: the size of an individual multidimensional internal node in the directory structure has been fixed by predetermining the number of search key bits k i to be searched in each dimension independently of the other dimensions, the size of the internal node in each dimension being 2 k .sbsp.i.
Claim 34
Dependent Claim
202 words
An associative memory arrangement for storing data in electrical form, the data being stored as data units in a dedicated storage space assigned for each data unit in the memory, the memory arrangement comprising a directory structure which is a multidimensional digital trie structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein a node can be an internal node comprising a multidimensional array wherein an individual non-empty element comprises a pointer (31) guiding progress in the directory structure, or a leaf node containing one or more pointers to a data unit stored in the memory, each data unit to be stored in the memory being associated with a multidimensional search key comprising a search key for each dimension, on the basis of which search keys progress is made in the directory structure, the directory structure returning the data unit associated with the multidimensional search key employed in each case, wherein: the size of an individual multidimensional internal node in the directory structure has been fixed by predetermining the number of search key bits k i to be searched in each dimension independently of the other dimensions, the size of the internal node in each dimension being 2 k .sbsp.i.
Claim 35
Dependent Claim
195 words
An associative memory arrangement for storing data in electrical form, the data being stored as data units in a dedicated storage space assigned for each data unit in the memory, the memory arrangement comprising a directory structure which is a multidimensional digital trie structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein a node can be an internal node comprising a multidimensional array wherein an individual non-empty element comprises a pointer (31) guiding progress in the directory structure, or a leaf node containing at least one data unit, each data unit to be stored in the memory being associated with a multidimensional search key comprising a search key for each dimension, on the basis of which search keys progress is made in the directory structure, the directory structure returning the data unit associated with the multidimensional search key employed in each case, wherein: the size of an individual multidimensional internal node in the directory structure has been fixed by predetermining the number of search key bits k i to be searched in each dimension independently of the other dimensions, the size of the internal node in each dimension being 2 k .sbsp..
Claim 36
Dependent Claim
195 words
An associative memory arrangement for storing data in electrical form, the data being stored as data units in a dedicated storage space assigned for each data unit in the memory, the memory arrangement comprising a directory structure which is a multidimensional digital trie structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein a node can be an internal node comprising a multidimensional array wherein an individual non-empty element comprises a pointer (31) guiding progress in the directory structure, or a leaf node containing at least one data unit, each data unit to be stored in the memory being associated with a multidimensional search key comprising a search key for each dimension, on the basis of which search keys progress is made in the directory structure, the directory structure returning the data unit associated with the multidimensional search key employed in each case, wherein: the size of an individual multidimensional internal node in the directory structure has been fixed by predetermining the number of search key bits k i to be searched in each dimension independently of the other dimensions, the size of the internal node in each dimension being 2 k .sbsp..
References Cited (Backward Citations)
US5058144A
Cited
US5463390A
Cited
US5532694A
Cited
US5257365A
Cited
US5442784A
Cited
US5592667A
Cited
US5521597A
Cited
US5564045A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-07 | 2002-06-08 | 2002-12-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-07 | 2006-06-08 | 2006-12-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-07 | 2010-06-08 | 2010-12-08 | $7700.00 | Window Closed / Lapsed |