Method and apparatus for storing and retrieving data and a memory arrangement

• US 5,848,416 A
• Filed: 12/06/1996
• Issued: 12/08/1998
• Est. Priority Date: 06/06/1994
• Status: Expired due to Fees

• Current Assignee: Nokia Telecommunications Oy (Nokia Corporation)
• Original Assignee: Nokia Telecommunications Oy (Nokia Corporation)
• Inventors: Tikkanen, Matti
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Ho, Ruay Lian
• Application Number:
  US08/750,777
• Time in Patent Office: 732 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100, 707/101, 707/102, 707/103, 707/104, 707/200, 707/531, 707/540, 341/51, 341/79, 341/65, 341/67, 341/87, 341/95, 341/106, 345/422, 395/13, 395/200.32, 395/709, 364/251.6, 364/282.1, 364/260.6, 364/708.1, 364/951.3, 364/964.28, 364/966.2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

1. 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.

2. A method as claimed in claim 1, wherein:

a new leaf node wherein storage is performed is created after step (c).

3. 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.

4. 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.

5. 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.

6. 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.

7. A method as claimed in claim 6, wherein:

a new leaf node wherein storage is performed is created after step (c).

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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..