Location tracking optimizations

• US 8,155,880 B2
• Filed: 05/09/2008
• Issued: 04/10/2012
• Est. Priority Date: 05/09/2008
• Status: Expired due to Fees

• Current Assignee: JMP Consulting Limited (J M P Consultants Limited)
• Original Assignee: Locomatix, Inc. (X Holdings Corp.)
• Inventors: Chen, Yun, Ramasamy, Karthikeyan, Patel, Jignesh M
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US12/151,799
• Publication Number:
  US 20090282122A1
• Time in Patent Office: 1,432 Days
• Field of Search: 701/200, 701/400, 370/351, 370/338, 370/356, 455/456.3, 455/414.2, 455/404.2, 455/403, 379/114.01
• US Class Current: 701/400
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A computer-implemented method includes probing a first band along a centerline dimension for a distribution of Location Based Notifications (LBNs), the distribution including a majority of LBNs clustered along and overlapping with the centerline.

Claims

1. A computer-implemented method comprising:

receiving signals from a plurality of mobile devices via a communication interface;

transforming the signals into location information for the devices;

storing the location information for the devices in a machine memory implementing a spatial index;

probing a first band of the spatial index along a centerline dimension for a distribution of Location Based Notifications (LBNs), the distribution comprising a majority of LBNs clustered along and overlapping with the centerline.

2. The method of claim 1, wherein for a majority of LBNs in the distribution, a spatial extent of the LBNs perpendicular to the center line does not exceed a constant ε

.

3. The method of claim 1, further comprising:

the distribution of LBNs sorted according to a coordinate along the centerline dimension.

4. The method of claim 1, further comprising:

further probing a second distribution of LBNs that do not fall into the first distribution.

5. The method of claim 4, further comprising:

determining a maximum LBN extent for the second distribution.

6. The method of claim 1, further comprising:

determining a maximum LBN extent along the dimension.

7. The method of claim 1, further comprising:

comparing the LBNs with more specific geometry for an entity.

8. The method of claim 1, further comprising:

probing a second band along a second centerline dimension orthogonal to the first, for a second distribution of Location Based Notifications (LBNs) comprising a majority of LBNs clustered along and overlapping with the second centerline.

9. The method of claim 1, further comprising:

probing a third band comprising a distribution of Location Based Notifications (LBNs) in an overlapping region of the first and second bands.

10. The method of claim 1, further comprising:

the centerline dimension along an angle to the x or y dimensions of a Cartesian grid.

11. A location tracking system, comprising:

at least one computer system comprising non-transitory machine memory configured with logic to probe a first band of a spatial index stored in the machine memory along a centerline dimension for a distribution of Location Based Notifications (LBNs), the distribution comprising a majority of LBNs clustered along and overlapping with the centerline.

12. The system of claim 11, wherein for a majority of LBNs in the distribution, a spatial extent of the LBNs perpendicular to the center line does not exceed a constant ε

.

13. The system of claim 11, further comprising logic to sort the distribution of LBNs according to a coordinate along the centerline dimension.

14. The system of claim 11, further comprising logic to probe a second distribution of LBNs that do not tall into the first distribution.

15. The system of claim 14, further comprising logic to determine a maximum LBN extent for the second distribution.

16. The system of claim 11, further comprising logic to determine a maximum LBN extent along the dimension.

17. The system of claim 11, further comprising logic to compare the LBNs with more specific geometry for an entity.

18. The system of claim 11, further comprising logic to probe a second band along a second centerline dimension orthogonal to the first, for a second distribution of Location Based Notifications (LBNs) comprising a majority of LBNs clustered along and overlapping with the second centerline.

19. The system of claim 11, further comprising logic to probe a third band comprising a distribution of. Location Based Notifications (LBNs) in an overlapping region of the first and second bands.

20. The system of claim 11, wherein the centerline dimension is along an angle to the x or y dimensions of a Cartesian grid.