Location determination, mapping, and data management through crowdsourcing

• US 9,942,720 B2
• Filed: 10/21/2016
• Issued: 04/10/2018
• Est. Priority Date: 04/28/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: Mori, Koichi, Sudarsan, Satheesh, Bennett, Danny, Jiang, Yifei, Pellet, Yannick, Singh, Jasvinder, Sidhu, Shalinder
• Primary Examiner(s): TAYLOR, NATHAN SCOTT
• Application Number:
  US15/299,869
• Publication Number:
  US 20170041761A1
• Time in Patent Office: 536 Days
• Field of Search: 455436
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01S 11/06 using intensity measurements
• CPC Class Codes: G01S 19/05 providing aiding data
• CPC Class Codes: G01S 5/013 Identifying areas in a building
• CPC Class Codes: G01S 5/0244 Accuracy or reliability of position solution or of measurements contributing thereto
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

Mapping through crowdsourcing includes determining, using a processor, segments for a plurality of trajectories, wherein each trajectory includes radio frequency (RF) data from a communication device, determining, using the processor, RF features for the segments, and forming, using the processor, clusters of the segments according to the RF features. One or more routes of a map are generated from the clusters using the processor.

Claims

1. A method, comprising:

receiving, using a processor, data units from a plurality of communication devices over time, wherein each data unit comprises location information;

correlating, using the processor, the data units with regions of a map using the location information;

assigning, to each data unit, a validity score;

for each data unit, decrementing the validity score of the data unit over time according to a region specific invalidity rate for the region correlated with the data unit;

invaliding each data unit responsive to determining that the validity score of the data unit does not exceed a minimum validity score;

determining, using the processor, data densities for regions, wherein a data density specifies a number of data units received from the region over a period of time; and

presenting, using the processor, an indicator of data density of the regions.

2. The method of claim 1, wherein:

the validity score assigned to each data unit is specific to the region correlated with the data unit; and

the region specific invalidity rates are determined based upon the data densities of the respective regions.

3. The method of claim 1, further comprising:

subdividing a selected region into a plurality of smaller regions responsive to determining that the selected region has a data density exceeding a data density threshold.

4. The method of claim 1, further comprising:

merging a plurality of selected regions into a single, larger region responsive to determining that the data density for each of the plurality of selected regions is below a data density threshold, wherein each of the plurality of selected regions is adjacent to at least one other one of the plurality of selected regions.

5. The method of claim 1, further comprising:

updating the region specific data invalidity rates of the regions of the map according to the data density of each respective region over time.

6. The method of claim 1, wherein the data units include radio frequency data, the method further comprising:

determining segments for a plurality of trajectories from the radio frequency data, wherein each segment includes at least one of a Wi-Fi feature or a magnetic field feature located at a particular distance along the segment;

forming clusters of the segments according to radio frequency features identified within the segments; and

generating routes for a map using the clusters.

7. A system, comprising:

a processor programmed to initiate executable operations comprising;

receiving data units from a plurality of communication devices over time, wherein each data unit comprises location information;

correlating the data units with regions of a map using the location information;

assigning, to each data unit, a validity score;

for each data unit, decrementing the validity score of the data unit over time according to a region specific invalidity rate for the region correlated with the data unit;

invalidating each data unit responsive to determining that the validity score of the data unit does not exceed a minimum validity score;

determining data densities for regions, wherein a data density specifies a number of data units received from the region over a period of time; and

presenting an indicator of data density of the regions.

8. The system of claim 7, wherein:

the validity score assigned to each data unit is specific to the region correlated with the data unit; and

the region specific invalidity rates are determined based upon the data densities of the respective regions.

9. The system of claim 7, wherein the processor is further programmed to initiate executable operations comprising:

subdividing a selected region into a plurality of smaller regions responsive to determining that the selected region has a data density exceeding a data density threshold.

10. The system of claim 7, wherein the processor is further programmed to initiate executable operations comprising:

merging a plurality of selected regions into a single, larger region responsive to determining that the data density for each of the plurality of selected regions is below a data density threshold, wherein each of the plurality of selected regions is adjacent to at least one other one of the plurality of selected regions.

11. The system of claim 7, wherein the processor is further programmed to initiate executable operations comprising:

updating the region specific data invalidity rates of the regions of the map according to the data density of each respective region over time.

12. The system of claim 7, wherein the data units include radio frequency data and the processor is further programmed to initiate executable operations comprising:

determining segments for a plurality of trajectories from the radio frequency data, wherein each segment includes at least one of a Wi-Fi feature or a magnetic field feature located at a particular distance along the segment;

forming clusters of the segments according to radio frequency features identified within the segments; and

generating routes for a map using the clusters.

13. A computer program product comprising a computer readable storage medium having program code stored thereon, the program code executable by a processor to cause the processor to:

receive data units from a plurality of communication devices over time, wherein each data unit comprises location information;

correlate the data units with regions of a map using the location information;

assign, to each data unit, a validity score;

for each data unit, decrement the validity score of the data unit over time according to a region specific invalidity rate for the region correlated with the data unit;

invalidate each data unit responsive to determining that the validity score of the data unit does not exceed a minimum validity score;

determine data densities for regions, wherein a data density specifies a number of data units received from the region over a period of time; and

present an indicator of data density of the regions.

14. The computer program product of claim 13, wherein:

the validity score assigned to each data unit is specific to the region correlated with the data unit; and

the region specific invalidity rates are determined based upon the data densities of the respective regions.

15. The computer program product of claim 13, wherein the program code is further executable by the processor to:

subdivide a selected region into a plurality of smaller regions responsive to determining that the selected region has a data density exceeding a data density threshold.

16. The computer program product of claim 13, wherein the program code is further executable by the processor to:

merge a plurality of selected regions into a single, larger region responsive to determining that the data density for each of the plurality of selected regions is below a data density threshold, wherein each of the plurality of selected regions is adjacent to at least one other one of the plurality of selected regions.

17. The computer program product of claim 13, wherein the data units include radio frequency data and the program code is further executable by the processor to:

determine segments for a plurality of trajectories from the radio frequency data, wherein each segment includes at least one of a Wi-Fi feature or a magnetic field feature located at a particular distance along the segment;

form clusters of the segments according to radio frequency features identified within the segments; and

generate routes for a map using the clusters.