Method for storing a parcelwise divided digital data base as well as of addressing a data parcel in a mass memory, and apparatus for carrying out the method

• US 4,888,698 A
• Filed: 10/19/1987
• Issued: 12/19/1989
• Est. Priority Date: 10/23/1986
• Status: Expired due to Term

• Current Assignee: Mannesmann VDO AG (Continental AG)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Janse, Cornelis P., Lahaije, Paul D. M. E., Driessen, Leonardus M. H. E.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): TRANS, VINCENT N
• Application Number:
  US07/110,303
• Time in Patent Office: 792 Days
• Field of Search: 364/443, 364/449, 364/200, 364/900, 364/518, 364/521, 340/995, 340/996, 73/178 R
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: G11B 2220/20 Disc-shaped record carriers
• CPC Class Codes: G11B 2220/213 Read-only discs
• CPC Class Codes: G11B 2220/2545 CDs
• CPC Class Codes: G11B 2220/255 CD-I, i.e. CD-interactive
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A database is stored in a mass memory. For this purpose, it is first divided into main cells and then into base cells according to a predetermined regular division pattern. Each base cell is then checked to see whether its data content is sufficient to occupy substantially completely a storage parcel having a predetermined capacity. If this is the case, the base cell is thus accommodated in a storage parcel; if this is not the case, adjacent base cells are grouped until a storage parcel is occupied substantially completely. The operation of addressing a storage parcel is effected by the use of a main cell table in which address pointers are stored, each of which points to a base cell table. In the base cell table, an index is given for each base cell and this index indicates in which storage parcel the relevant base cell is accommodated. Each of these indices indicates a location in a data paracel list at which an address indicator is present, which indicates the location at which the relevant parcel is stored in the mass memory.

Claims

1. A method for storing a digital data base in a memory whose capacity is divided into a number of storage parcels each having a predetermined storage capacity, said method comprising the following steps:

dividing the data base into a number of main cells according to a predetermined regular division pattern;

dividing each main cell into a further number of data parcels , so that each data parcel covers a respective part of the main cel, which part has a data content occupying substantially completely the storage capacity of a storage parcel;

setting up an identifier table comprising;

(a) a first identifier identifying said predetermined pattern;

(b) a second identifier identifying said division into a data parcel; and

(c) for each main cell a data parcel list which comprises for each data parcel of that main cell an address pointer indicating at which memory location the respective data parcel is stored; and

loading into said memory the data content of each data parcel at the address indicated by its address pointer and loading said identifier table;

wherein main cells which comprise more than one data parcel are divided according to a further predetermined regular division pattern into such a nuber of base cells that the data content of each base cell is storable in a storage parcel, said parcels being formed by combining each time one or more adjacent base cellls of a same main cell, so that each base cell only belongs to one and the same data parcel,

the method further comprising the following steps for setting up said identifier table;

(a) compiling a main cell table comprising said first identifier and further for each main cell divided into base cells a further address pointer indicating a memory location at which a base cell table for that main cell is stored;

(b) forming each main cell divided into base cells said second identifier by forming a number of indices, each index indicating a respective data parcel of its appertaining main cell;

(c) assigning to each base cell the index of the respective data parcel in which it is accommodated; and

(d) compiling for each main cell divided into base cells a base cell table comprising a base cell identifier and a list of

the base cells with their assigned index;

each base cell table being loaded at its respective address indicated by its respective further address pointer.

2. A method of addressing a data parcel in a memory, in which a database is stored parcelwise whilst using a method as claimed in claim 1, the data parcel to be addressed being identified by a virtual address constituted by a data word belonging to the data content of that data parcel, the method comprising the following steps:

a. fetching the main cell table from the memory;

b. determining in what main cell the virtual address supplied is located by use of the first identifier and selecting that main cell;

c. determining by using the further address pointer of the selected main cell the address at which the base cell table associated with the selected main cell is stored in the memory;

d. fetching the selected base cell table stored at the determined address;

e. determining in which base cell the virtual address supplied is located by use of the base cell identifier from the selected base cell table and selecting this base cell;

f. fetching from the base cell table the index assigned to the selected base cell;

g. selecting the data parcel indicated by the fetched index from the parcel list associated with the selected main cell;

h. determining from the address pointer of the selected parcel a storage address for addressing a data parcel in the memory; and

i. fetching the data content of the selected parcel.

3. An apparatus for retrieving data, the apparatus comprising:

(a) a memory whose capacity is divided into a plurality of storage parcels each having a predetermined storage capacity, the memory being for containing a data base which comprises an identifier table comprising;

(i) a main cell table comprising;

(A) a first identifier which identifies a first predetermined regular division pattern which divides the data base into a first number of main cells; and

(B) at least one first address pointer corresponding to at least one respective main cell identified by the first identifier;

(ii) for each main cell occupying more than one storage parcel, a respective base cell table pointed to by such a first address pointer, and corresponding to a second division of any main cells which comprise more than one data parcel, each data parcel being a part of a respective main cell, which part has a data content occupying substantially completely the storage capacity of a respective one of the storage parcels, the second division resulting from

a division of any such main cells into a first set of base cells according to a second predetermined regular division pattern the base cell table comprising;

(A) a base cell identifier; and

(B) a list of base cells with respective indices, each index indicating a respective data parcel of the respective main cell, so that at least two adjacent base cells in said first set and within a same main cell share an index, effectively resulting in at least one combined base cell, each combined base cell corresponding to only one data parcel; and

(iii) a respective data parcel list corresponding to each main cell which occupies more than one storage parcel, each data parcel list including a respective second address pointer for each respective data parcel in the corresponding main cell, the respective second address pointer indicating a memory location where the respective data parcel is located, the second address pointer being locatable using an index from an appropriate base cell table;

(b) memory means for storing a supplied virtual address and a fetched copy of the main cell table;

(c) first selection means for selecting a selected main cell, in which the supplied virtual address is located, using the first identifier from the fetched copy of the main cell table;

(d) first address generation means for generating from the first address pointer the address for the base cell table associated with the selected main cell;

(d) second selection means for selecting a selected base cell from the base cell table using the supplied virtual address and the base cell identifier;

(e) third selection means for selecting on the basis of the index associated with the selected base cell a data parcel from the data parcel list; and

(f) second address generation means for generating on the basis of the respective second address pointer of the selected data parcel the address at which a corresponding storage parcel is stored.

4. A vehicle navigation system comprising the apparatus of claim 3 wherein the data base comprises a road map.

5. A method for storing a digital data base in a memory whose capacity is divided into a plurality of storage parcels each having a predetermined storage capacity, the method comprising the following steps:

(a) first dividing the data base into a plurality of main cells according to a first predetermined regular division pattern;

(b) second dividing any main cells which comprise more than one data parcel, each data parcel being a part of the respective main cell, which part has a data content occupying substantially completely the storage capacity of a respective one of the storage parcels, said second dividing comprising;

(i) dividing main cells which comprise more than one data parcel into a first set of base cells according to a second predetermined regular division pattern; and

(ii) combining one or more adjacent base cells within a same main cell to reduce a number of base cells within that same main cell, said combining resulting in a second set of base cells, which second set includes at least one combined base cell, so that any combined base cell resulting from said combining corresponds to only one data parcel; and

(c) setting up an identifier table comprising;

(i) a main cell table comprising

(A) a first identifier identifying said plurality of main cells according to said first pattern; and

(B) for each main cell which is divided into base cells, a respective first address pointer indicating a memory location of a corresponding base cell table;

(ii) at least one base cell table pointed to by such a first address pointer and comprising a base cell identifier identifying the base cells in said first set according to said second pattern and a list of the base cells in said first set with respective indices, each index indicating a respective data parcel of the respective main cell, so that at least two base cells in said first set and within a same main cell share an index; and

(iii) for each main cell which is divided into base cells, a respective data parcel list which comprises a respective second address pointer for each respective data parcel in that main cell, the respective second address pointer indicating a memory location where the respective data parcel is stored.

6. A memory loaded with a database comprising an optical memory, wherein the database is loaded into the memory by use of the method as claimed in claim 5.

7. The method of claim 5 wherein the indices from the base cell table indicate respective second address pointers in the data parcel list.

14. The method of claim 5 or 8 wherein each data parcel occupies at least 75% of storage capacity of the respective one of the storage parcels.

15. The method of claim 5 or 8 wherein

the database is a road map;

the first pattern divides the database into main cells which cover equal surface areas; and

the second pattern divides the database into base cells which cover equal surface areas such that a number of base cells in said first set is an even power of two.

16. A method as claimed in claim 15, wherein:

the main cells and the base cells are each formed by respective square segments of the road-map, and

the first identifier and the base cell identifier indicate respectively respective lengths of the respective squares from which the respective main cells and the respective base cells are formed.

17. The method of claim 15 wherein the first and base cell identifiers comprise respective first and second functions for locating entries within the main and base cell tables, respectively, which entries are arranged according to a Peano-N key.

18. The method of claim 16 wherein the first and base cell identifiers comprise respective first and second functions for locating entries within the main and base cell tables, respectively, which entries are arranged according to a Peano-N key.

8. A method for retrieving data from a data base stored in a memory whose capacity is divided into a plurality of storage parcels each having a predetermined storage capacity, the method comprising the following steps:

(a) first fetching a main cell table from memory, the main cell table comprising;

(i) a first identifier which identifies a plurality of main cells according to a first predetermined regular division pattern, which first pattern divides the data base into the main cells; and

(ii) at least one first address pointer corresponding to at least one respective main cell identified according to the first identifier;

(b) first selecting a main cell and one first address pointer using the first identifier and a virtual address identifying a data parcel within the main cell, which data parcel is a part of the main cell which part has a data content occupying substantially completely the storage capacity of a respective one of the storage parcels;

(c) second fetching a base cell table pointed to by the one first address pointer, said base cell table comprising;

(i) a base cell identifier identifying a plurality of base cells according to a second predetermined regular division pattern, which second pattern divides the main cell into a first set of base cells; and

(ii) a list of the base cells in the first set with respective indices, each index indicating a respective data parcel of the respective main cell, so that at least two adjacent base cells in said first set share an index, effectively resulting in at least one combined base cell, each combined base cell corresponding to only one data parcel;

(d) second selecting a base cell from the first set and a respective index using the base cell identifier and the virtual address;

(e) third fetching a data parcel list comprising a respective second address pointer for each respective data parcel in the main cell, which second address pointer is locatable using the indices from the base cell table; and

(f) third selecting a second address pointer from the data parcel list using the respective index.

9. The method of claim 8 wherein

(a) the base cell table and the data parcel list are stored at a predetermined offset from one another, and

(b) said second and third fetching steps are performed in a single retrieving step.

10. A method as claimed in claim 8, in which the database is a road-map, and wherein the virtual address is formed using the geographic coordinates associated with the geographic location to be indicated.

11. A method as claimed in claim 8, 9, or 10, in which the data base is a road-map, wherein:

a further virtual address is formed by adding a predetermined value to the virtual address, and

the method further comprises fetching a storage parcel containing the further virtual address.

12. A method as claimed in claim 8, wherein each parcel list is stored in the memory at an address which has a given offset from the storage address of the associated base cell table.

13. A method as claimed in claim 8, wherein the capacity of a storage parcel has a byte length lying between 2K bytes and 32K bytes.