Binary difference operations for navigational bit streams

• US 9,575,993 B2
• Filed: 12/30/2014
• Issued: 02/21/2017
• Est. Priority Date: 12/30/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Pfeifle, Martin
• Primary Examiner(s): MILLER, VIVA L
• Application Number:
  US14/586,272
• Publication Number:
  US 20160188630A1
• Time in Patent Office: 784 Days
• Field of Search: 717/169
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3859 Differential updating map data
• CPC Class Codes: G06F 16/116 Details of conversion of file system types or formats
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H03M 7/3091 Data deduplication
• CPC Class Codes: H03M 7/3093 using fixed length segments

Abstract

A computing device may identify a series of bits representative of a first binary large object (BLOB) for navigation data including road segments and road attributes. The computing device duplicates each bit of the series of bits a predetermined number of times to form a first bit string. The first bit string is larger than the series of bits by a factor of the predetermined number. The computing device performs a binary difference of the first bit string to a second bit string representative of a second BLOB. A result of the binary difference is stored in a navigation patch file.

Claims

1. A method comprising:

identifying, using a processor, a series of bits representative of a first binary large object (BLOB) for navigation data including road segments and road attributes;

calculating, using the processor, a modulus function based on a predetermined number for the BLOB, wherein a result of the modulus function is nonzero and indicates the series of bits are misaligned;

duplicating, using the processor, each bit of the series of bits the predetermined number of times to form a first bit string, wherein the first bit string is larger than the series of bits by a factor of the predetermined number;

performing a binary difference of the first bit string of the first BLOB to a second bit string representative of a second BLOB for navigation data including road segments and road attributes, wherein the binary difference at least compares a bit of the first bit string to a corresponding bit of the second bit string;

storing a result of the binary difference of the first bit string and the second bit string in a navigation patch file;

applying the navigation patch file to a third BLOB of a navigation database;

duplicating each bit of a series of the third BLOB in a format of the navigation database by the predetermined number of times to form a third bit string;

modifying the third bit string based on the navigation patch file; and

removing bits of the third bit string to return the navigation patch file to the format of the navigation database.

2. The method of claim 1, wherein the predetermined number is 8.

3. The method of claim 1, wherein a 1 bit in the series of bits corresponds to 11111111 in the first bit string and a 0 bit in the series of bits corresponds to 00000000 in the first bit string.

4. The method of claim 1, further comprising:

identifying, using the processor, a second series of bits representative of the second BLOB for navigation data include road segments and road attributes; and

duplicating, using the processor, each bit of the second series of bits by the predetermined number of times to form the second bit string, wherein the second bit string is larger than the second series of bits by a factor of the predetermined number.

5. The method of claim 1, wherein the binary difference compares a hexadecimal representation of the first bit string to a hexadecimal representation of the second bit string.

6. The method of claim 1, further comprising:

identifying a nonstandard number of bits in the first BLOB, wherein the duplicating each bit of the series of bits is in response to the nonstandard number of bits.

7. The method of claim 1, wherein the BLOB is part of a complete navigation file.

8. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

determine a first series of bits represents an object of a binary large object (BLOB) for existing navigation data include road segments and road attributes;

calculate a modulus function based on a predetermined number for the BLOB, wherein a result of the modulus function is nonzero and indicates the first series of bits are misaligned;

identify a second series of bits for a new version of the object of the BLOB;

inflate the first series of bits by the predetermined number of times to form a first bit string, wherein the first bit string is larger than the first series of bits by a factor of the predetermined number;

inflate the second series of bits by the predetermined number of times to form a second bit string, wherein the second bit string is larger than the second series of bits by a factor of the predetermined number;

calculate a binary difference of the second bit string and the first bit string;

store location values for a result of the binary difference in a navigation patch file;

apply the navigation patch file to a corresponding BLOB of a navigation database;

duplicate bits of a series in the corresponding BLOB in a format of the navigation database by the predetermined number of times to form a third bit string;

modifying the third bit string based on the navigation patch file; and

removing bits of the third bit string to return the navigation patch file to the format of the navigation database.

9. The apparatus of claim 8, wherein the location values indicate byte sequence numbers in which a difference was calculated between the second bit string and the first bit string.

10. The apparatus of claim 8, wherein the predetermined number is a base number indicative of a standard character value.

11. The apparatus of claim 10, wherein the base number is 8 or 16.

12. The apparatus of claim 8, wherein the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:

send the navigation patch file based on a time schedule or a request corresponding to a navigation device.

13. The apparatus of claim 8, wherein the object includes a nonstandard number of bits that is not divisible by 8.

14. A non-transitory computer readable medium including instructions that when executed are operable to:

identify, using a processor, a series of bits representative of an object of a first binary large object (BLOB) for navigation data including road segments and road attributes;

calculate, using the processor, a modulus function based on a predetermined number for the BLOB, wherein a result of the modulus function is nonzero and indicates the series of bits are misaligned;

duplicate, using the processor, each bit of the series of bits the predetermined number of times to form a first bit string, wherein the first bit string is larger than the series of bits by a factor of the predetermined number;

perform a binary difference of the first bit string of the first BLOB to a second bit string representative of a second BLOB for navigation data including road segments and road attributes, wherein the binary difference at least compares a bit of the first bit string to a corresponding bit of the second bit string;

store a result of the binary difference of the first bit string and the second bit string in a navigation patch file;

apply the navigation patch file to a third BLOB of a navigation database;

duplicate each bit of a series of the third BLOB in a format of the navigation database by the predetermined number of times to form a third bit string;

modify the third bit string based on the navigation patch file; and

remove bits of the third bit string to return the navigation patch file to the format of the navigation database.

15. The non-transitory computer readable medium of claim 14, wherein the object includes a number of bits that is not divisible by 8.

16. The non-transitory computer readable medium of claim 14, wherein the navigation data includes road segment attributes.