Binary difference operations for navigational bit streams

• US 10,642,824 B2
• Filed: 01/11/2017
• Issued: 05/05/2020
• Est. Priority Date: 12/30/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Pfeifle, Martin
• Primary Examiner(s): Miller, Viva
• Application Number:
  US15/403,664
• Publication Number:
  US 20170124144A1
• Time in Patent Office: 1,210 Days
• 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:

receiving an update package for a navigation database including road segments and road attributes;

matching the update package to a specified portion of the navigation database;

duplicating each bit of a series of bits from the specified portion of the navigation database for a predetermined number of times to form a plurality of repeating sequences of bits that are concatenated to form a duplicated series of bits;

updating the duplicated series of bits according to the update package to form an updated series of bits comprising an updated plurality of repeating sequences of bits; and

reducing the updated series of bits by reducing each repeating sequence of bits of the updated plurality of repeating sequences of bits to a single corresponding bit.

2. The method of claim 1, wherein reducing the series of bits comprises:

applying a dot product of a vector and the updated series of bits.

3. The method of claim 1, wherein the updated series of bits is reduced by the predetermined number of times.

4. The method of claim 1, wherein the update package is received according to a schedule.

5. The method of claim 1, wherein duplicating the series of bits comprises:

performing vector multiplication between the series of bits and a multiplication vector.

6. The method of claim 5, wherein the vector multiplication is repeated for each bit in the series of bits.

7. The method of claim 1, further comprising:

selecting an update location in the navigation database for the specified portion of the navigation database; and

inserting the reduced series of bits at the update location.

8. The method of claim 7, further comprising:

performing a test on the update location of the navigation database.

9. The method of claim 8, wherein the test includes an integrity check, a parity check, or a routing algorithm.

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

11. The method of claim 1, wherein the base number is 8 or 16.

12. The method of claim 1, wherein the series of bits from the specified portion of the navigation database includes a nonstandard number of bits that is not divisible by 8.

13. An apparatus comprising:

a communication interface configured to receive an update package for a navigation database including road segments and road attributes; and

a controller configured to duplicate each bit of a series of bits from the specified portion of the navigation database for a predetermined number of times to form a plurality of repeating sequences of bits that are concatenated to form a duplicated series of bits, update the duplicated series of bits according to the update package to form an updated series of bits comprising an updated plurality of repeating sequences of bits, and reduce the updated series of bits by reducing each repeating sequence of bits of the updated plurality of repeating sequences of bits to a single corresponding bit.

14. The apparatus of claim 13, wherein the controller is configured to reduce the updated series of bits.

15. The apparatus of claim 14, wherein the series of bits is reduced by applying a dot product of a vector and the updated series of bits.

16. The apparatus of claim 13, wherein the series of bits are duplicated by performing vector multiplication between the series of bits and a multiplication vector.

17. The apparatus of claim 16, wherein the vector multiplication is repeated for each bit in the series of bits.

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

19. The apparatus of claim 13, wherein the series of bits from the specified portion of the navigation database includes a nonstandard number of bits that is not divisible by 8.

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

receive an update package for a navigation database;

match the update package to a specified portion of the navigation database;

duplicate each bit of a series of bits from the specified portion of the navigation database for a predetermined number of times to form a plurality of repeating sequences of bits that are concatenated to form a duplicated series of bits;

update the duplicated series of bits according to the update package to form an updated series of bits comprising an updated plurality of repeating sequences of bits; and

reduce the updated series of bits by reducing each repeating sequence of bits of the updated plurality of repeating sequences of bits to a single corresponding bit.