Generating an OD matrix

• US 8,532,648 B2
• Filed: 02/02/2012
• Issued: 09/10/2013
• Est. Priority Date: 08/05/2011
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Moritz, Simon, Mellegard, Erik, Zahoor, Jawad Mohamed
• Primary Examiner(s): SHEDRICK, CHARLES TERRELL
• Application Number:
  US13/364,693
• Publication Number:
  US 20130035089A1
• Time in Patent Office: 586 Days
• Field of Search: 455/423, 455/456.1, 370/352
• US Class Current: 455/422.1
• CPC Class Codes: G01S 5/0018 Transmission from mobile station to base station
• CPC Class Codes: G08G 1/012 from other sources than vehicle or roadside beacons, e.g. mobile networks
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0145 for active traffic flow control
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Computers, a user equipment, a computer system, computer program products, and a method for a computer system are disclosed. In some embodiments, the method comprises the steps of: receiving user IDs, cell IDs and time stamps associated with the cell IDs and the user IDs; requesting and receiving, from a cell ID database, geographical coordinates corresponding to the cell IDs; finding stations and times for each user ID based on, at least in part, the geographical coordinates and time stamps associated with each user ID; exchanging the stations with a place for each one of the stations; generating at least one OD sub-matrix associated with each user ID based on, at least in part, places and times of arrival and departure associated with these places; and merging the OD matrices into an OD matrix.

Claims

1. A computer for supporting generation of an OD matrix based on, at least in part, network data associated with a plurality of user IDs, comprising:

a receiving unit operable to receive a user ID, cell IDs and time stamps associated with the cell IDs and the user ID;

a requesting unit configured to request, from a cell ID database, geographical coordinates corresponding to a cell ID;

a station identification unit for determining stations based on, at least in part, the geographical coordinates and time stamps;

a mapping unit configured to, for each one of the stations, determine a place associated with the station;

an OD matrix generating configured to generate at least one OD sub-matrix associated with the user ID based on, at least in part, places and times of arrival and departure associated with the places; and

a sending unit for sending the OD sub-matrix to another computer.

2. The computer according to claim 1, further comprising a time adjustment unit for adjusting times of arrival and/or departure from the stations by a linear extrapolation based on, at least in part, data time stamped between the stations.

3. The computer according to claim 1, wherein the station identification unit is configured to:

(i) determine a geographical position associated with each time stamp for a user ID as either a first condition indicating that a user equipment associated with the user ID is moving or a second condition indicating that the user equipment is stationary and (ii) create a station if;

(a) the geographical position is determined to be in the second condition with respect to a first time stamp and is determined to be in the first condition with respect to a second time stamp immediately following the first time stamp and (b) the second condition preceding a change to the first condition has been maintained for a longer time than a time threshold.

4. The computer according to claim 3, wherein the station identification unit is configured to calculate a mean value for the geographical position of the station based on, at least in part, consecutive geographical positions related to the second condition.

5. The computer according to claim 4, wherein the station identification unit is configured to calculate the mean value also based on, at least in part, the time between the time stamps associated with the second condition in such a way that a longer time between two consecutive geographical positions gives a higher influence on the mean value than if the time would have been shorter.

12. A computer system comprising at least one computer according to claim 1.

13. The computer system according to claim 12, utilizing Hadoop map/reduce for generating the OD matrix and comprising a master computer connected to the at least one computer, which is a slave computer.

24. The computer according to claim 1, wherein the requesting unit is configured to request the geographical coordinates from the cell ID database by transmitting to the cell ID database a cell ID lookup request message that comprises said cell ID.

25. The computer according to claim 24, wherein the cell ID database is configured such that, in response to receiving the cell ID lookup request message comprising said cell ID, the cell ID database transforms said cell ID included in said message to a tuple comprising a latitude value and longitude value.

26. The computer according to claim 1, wherein, for each one of the stations, said place associated with said station comprises a word or phrase by which said station is known or referred to.

6. A computer for supporting generation of an OD matrix based on, at least in part, network data associated with a plurality of user IDs, comprising:

a receiving unit for receiving a user ID, cell IDs and time stamps associated with the cell IDs and the user ID;

a requesting unit for requesting, from a cell ID database, geographical coordinates corresponding to a cell ID;

a station identification unit for determining stations based on, at least in part, the geographical coordinates and time stamps;

a clustering unit for clustering the determined stations into at least two clusters;

a calculation unit configured to calculate, for each one of the clusters, a position of a new station based on, at least in part, the stations belonging to the same cluster;

a mapping unit for exchanging the new stations with a place for each one of the new stations;

an OD matrix generating unit for generating at least one OD sub-matrix associated with the user ID based on, at least in part, places and times of arrival and departure associated with the places; and

a sending unit for sending the OD sub-matrix to another computer.

7. The computer according to claim 6, further comprising a time adjustment unit for adjusting times of arrival and/or departure from the stations by a linear extrapolation based on, at least in part, data time stamped between the stations.

27. The computer of claim 6, wherein the calculation unit is configured to calculate said position of said new station based on the stations belonging to said same cluster by determining the mean position of the positions of all stations included in the said cluster.

8. A computer for supporting generation of an OD matrix based on, at least in part, network data associated with a plurality of user IDs, comprising:

a receiving unit for receiving a user ID, associated geographical coordinates and time stamps associated with the geographical coordinates and the user ID;

a station identification unit for finding stations based on, at least in part, the geographical coordinates and time stamps;

a mapping unit for exchanging the stations with a place for each one of the stations;

an OD matrix generating unit for generating at least one OD sub-matrix associated with the user ID based on, at least in part, places and times of arrival and departure associated with the places; and

a sending unit for sending the OD sub-matrix to another computer.

9. The computer according to claim 8, further comprising a time adjustment unit for adjusting times of arrival and/or departure from the stations by a linear extrapolation based on, at least in part, data time stamped between the stations.

10. A computer for supporting generation of an OD matrix based on, at least in part, network data associated with a plurality of user IDs, comprising:

a receiving unit for receiving a user ID, associated geographical coordinates and time stamps associated with the geographical coordinates and the user ID;

a station identification unit for finding stations and times based on, at least in part, the geographical coordinates and time stamps;

a clustering unit for clustering the stations into at least two clusters;

a calculation unit for calculating, for each one of the clusters, a position of a new station based on, at least in part, the stations belonging to the same cluster;

a mapping unit for exchanging the new stations with a place for each one of the new stations;

an OD matrix generating unit for generating at least one OD sub-matrix associated with the user ID based on, at least in part, places and times of arrival and departure associated with the places; and

a sending unit for sending the OD sub-matrix to another computer.

11. The computer according to claim 10, further comprising a time adjustment unit for adjusting times of arrival and/or departure from the stations by a linear extrapolation based on, at least in part, data time stamped between the stations.

14. A method performed by a computer system for generating an OD matrix based on, at least in part, network data associated with a plurality of user IDs, comprising the steps of:

receiving user IDs, cell IDs and time stamps associated with the cell IDs and the user IDs;

requesting and receiving, from a cell ID database, geographical coordinates corresponding to the cell IDs;

finding stations and times for each user ID based on, at least in part, the geographical coordinates and time stamps associated with each user ID;

exchanging the stations with a place for each one of the stations;

generating at least one OD sub-matrix for each user ID based on, at least in part, places and times of arrival and departure associated with the places; and

merging the OD sub-matrices into the OD matrix.

15. The method according to claim 14, further comprising the step of storing the OD matrix in a non-volatile memory.

16. The method according to claim 14, further comprising the step of adjusting times of arrival and/or departure from the stations by a linear extrapolation based on, at least in part, data time stamped between the stations.

17. The method according to claim 14, further comprising the steps of:

clustering the stations into at least two clusters, and

calculating, for each one of the clusters, a position of a new station based on, at least in part, the stations belonging to the same cluster, and instead of exchanging the stations exchanges the new stations with the respective place.

18. A user equipment for supporting generation of an OD matrix based at least partly on network data associated with a plurality of user IDs, comprising:

a unit for receiving or retrieving geographical coordinates and associated time stamps;

a station identification unit for finding stations and times;

a mapping unit for exchanging the stations with a place for each one of the stations;

an OD matrix generating unit for generating at least one OD sub-matrix based on, at least in part, places and times of arrival and departure associated with these places, and

a sending unit for sending the OD sub-matrix to a computer system.

19. The user equipment according to claim 18, wherein the unit for receiving or retrieving geographical coordinates and associated time stamps also is configured to receive or retrieve a user ID associated with the user equipment or a user of the user equipment, and

wherein the sending unit is adapted to send the user ID along with the OD sub-matrix.

20. The user equipment according to claim 18, further comprising a time adjustment unit for adjusting times of arrival and/or departure from the stations by a linear extrapolation based on, at least in part, data time stamped between the stations.

21. The user equipment according to claim 18, comprising

a clustering unit for clustering the stations into at least two clusters, and

a calculation unit for calculating, for each one of the clusters, a position of a new station based on, at least in part, the stations belonging to the same cluster, and wherein the mapping unit instead of exchanging the stations exchanges the new stations with the respective place.

22. A computer program product for generating an OD matrix based on, at least in part, network data associated with a plurality of user IDs, the computer program product comprising a non-transitory computer-readable medium storing a computer program for execution by a processor, the computer program comprising:

code units for requesting, from a cell ID database, geographical coordinates corresponding to the cell IDs;

code units for determining, for each of a plurality of user IDs, stations based on, at least in part, geographical coordinates and time stamps associated with each user ID;

code units for exchanging the stations with a place for each one of the stations;

code units for generating at least one OD sub-matrix associated with each user ID based on, at least in part, places and times of arrival and departure associated with the places; and

code units for merging the OD sub-matrices into the OD matrix.

23. A computer program product for supporting generation of an OD matrix based on, at least in part, network data associated with a plurality of user IDs, the computer program product comprising a non-transitory computer-readable medium storing a computer program for execution by a processor, the computer program comprising:

code units for receiving or retrieving geographical coordinates and associated time stamps;

code units for finding stations;

code units for exchanging the stations with a place for each one of the stations,

code units for generating at least one OD sub-matrix based on, at least in part, places and times of arrival and departure associated with the places, and

code units for sending the OD sub-matrix to a computer system.