APPARATUS AND METHODS FOR REDUCING DATA TRANSMISSION IN WIRELESS CLIENT-SERVER NAVIGATION SYSTEMS

• US 20080249704A1
• Filed: 04/09/2007
• Published: 10/09/2008
• Est. Priority Date: 04/09/2007
• Status: Active Grant

• Current Assignee: ZAMA Innovations LLC
• Original Assignee: IP3 2017, Series 200 of Allied Security Trust I (Allied Security Trust)
• Inventors: Cummings, Ian
• Granted Patent: US 10,605,610 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network

Abstract

Methods and apparatus reduce data transmission in a wireless client-server navigation system. A request for data representative of a map-related feature is received at a central server from a mobile unit. Data describing the feature is obtained in the form of line segments interconnecting points having coordinates such as a shapefile or other format. An operation is performed on the data describing the feature to generate data representative of the feature in a data-reduced format, and the data representative of the feature in the data-reduced format is forwarded to the mobile unit issuing the request. The operation responsible for producing the data-reduced format includes the steps of: receiving data describing a map; partitioning the map into a plurality of tiles; designating a reference point within each tile; representing the feature in the form of offsets from the reference points; and wherein the data-reduced format is based upon the reference points and offsets. Alternatively, the operation may include the steps of approximating the feature with a curve, whereby the data-reduced format includes a description of the curve. In a further alternative embodiment, the operation includes the steps of removing one or more of the points having the coordinates, leaving a plurality of remaining points describing the feature, such that the reduced-data format is represented with line segments interconnecting the remaining points. In all embodiments, the operation may include, alone or in combination with other embodiments, the step of applying a data-compression algorithm to the data representative of the feature in the data-reduced format prior to forwarding the data to the mobile unit issuing the request.

Claims

1. A method of reducing data transmission in a wireless client-server navigation system, comprising the steps of:

receiving, at a central server, a request for data representative of a map-related feature from a mobile unit;

obtaining data describing the feature in the form of line segments interconnecting points having coordinates;

performing an operation on the data describing the feature to generate data representative of the feature in a data-reduced format; and

forwarding the data representative of the feature in the data-reduced format to the mobile unit issuing the request.

2. The method of claim 1, wherein the map-related feature includes a route.

3. The method of claim 1, wherein the map-related feature includes a road, body of water, or other geographic feature.

4. The method of claim 1, wherein the map-related feature includes text.

5. The method of claim 1, wherein the operation is performed when the request is received from the mobile unit.

6. The method of claim 1, wherein:

the operation is performed in advance of the request from the mobile unit; and

the data representative of the feature in the data-reduced format is stored in a memory for later retrieval.

7. The method of claim 1, wherein the coordinates are provided in a shapefile format.

8. The method of claim 1, wherein the operation includes the steps of:

receiving data describing a map;

partitioning the map into a plurality of tiles;

designating a reference point within each tile;

representing the feature in the form of offsets from the reference points; and

wherein the data-reduced format is based upon the reference points and offsets.

9. The method of claim 8, wherein the tiles are substantially equal in size.

10. The method of claim 8, wherein the offsets are represented with Cartesian coordinates.

11. The method of claim 1, wherein the operation further includes the step of applying a data-compression algorithm to the data representative of the feature in the data-reduced format prior to forwarding the data to the mobile unit issuing the request.

12. The method of claim 1, wherein the operation includes the steps of:

approximating the feature with a curve; and

wherein the data-reduced format includes a description of the curve.

13. The method of claim 12, wherein the description of the curve includes the coordinates of points along the curve.

14. The method of claim 12, wherein the description of the curve includes a mathematical function.

15. The method of claim 12, wherein the curve is a Bezier or other spline, a polynomial or fractal curve.

16. The method of claim 12, further including the steps of:

providing a standard regarding the extent to which the curve will affect the approximation of the feature; and

applying the curve only if the standard is met.

17. The method of claim 16, wherein the standard is based upon map scale.

18. The method of claim 16, wherein the standard is based upon a user preference.

19. The method of claim 1, wherein the operation includes the steps of:

removing one or more of the points having the coordinates, leaving a plurality of remaining points describing the feature; and

wherein the reduced-data format is represented with line segments interconnecting the remaining points.

20. The method of claim 19, further including the steps of:

providing a standard regarding the extent to which the removal of a point will affect the approximation of the feature; and

removing the point only if the standard is met.

21. The method of claim 20, wherein the standard is based upon map scale.

22. The method of claim 20, wherein the standard is based upon a user preference.

23. The method of claim 19, wherein the operation further includes the step of applying a data-compression algorithm to the data representative of the feature in the data-reduced format prior to forwarding the data to the mobile unit issuing the request.

24. The method of claim 1, wherein the data representative of the feature in the data-reduced format is derived through the application of a data-compression algorithm to the data describing the feature.

25. The method of claim 24, wherein the data-compression algorithm includes the Lempel-Ziv algorithm or a variant or extension thereof.

26. A wireless client-server navigation system, comprising:

a mobile unit including;

a wireless transmitter for transmitting a request for data representative of a map-related feature,

a receiver for receiving the data representative of the map-related feature, and

a display for displaying the feature on a map; and

a central server including;

an input for receiving data describing map-related features in the form of line segments interconnecting points having coordinates,

a receiver for receiving the request from the mobile unit,

a processor for performing an operation on the data describing the map-related feature associated with the request by the mobile to generate data representative of the feature in a data-reduced format; and

a transmitter for transmitting the data representative of the feature in the data-reduced format to the mobile unit.

27. The system of claim 26, wherein the map-related feature includes a route.

28. The system of claim 26, wherein the map-related feature includes a road, body of water, or other geographic feature.

29. The system of claim 26, wherein the map-related feature includes text.

30. The system of claim 26, wherein the operation is performed by the processor when the request is received from the mobile unit.

31. The system of claim 26, wherein:

the operation is performed by the processor in advance of the request from the mobile unit; and

the system further including a memory for storing the data representative of the feature in the data-reduced format for later retrieval.

32. The system of claim 26, wherein the coordinates are provided in a shapefile format.

33. The system of claim 26, wherein the processor is operative to perform the following functions:

receive data describing a map;

partition the map into a plurality of tiles;

designate a reference point within each tile;

represent the feature in the form of offsets from the reference points.

34. The system of claim 33, wherein the processor is further operative to apply a data-compression algorithm to the data representative of the feature in the data-reduced format.

35. The system of claim 26, wherein the processor is operative to approximate the feature with a curve.

36. The system of claim 35, wherein the processor is further operative to apply a data-compression algorithm to the approximation.

37. The system of claim 26, wherein the processor is operative to remove one or more of the points having the coordinates, leaving a plurality of remaining points describing the feature.

38. The system of claim 37, wherein the processor is further operative to apply a data-compression algorithm to the remaining points describing the feature.

39. The system of claim 26, wherein the processor is operative to apply a data-compression algorithm to generate the data representative of the feature in the data-reduced format.

40. The method of claim 39, wherein the data-compression algorithm applied by the processor includes the Lempel-Ziv algorithm or a variant or extension thereof.