Branching mobile-device to system-namespace identifier mappings

• US 10,038,968 B2
• Filed: 10/22/2016
• Issued: 07/31/2018
• Est. Priority Date: 07/17/2013
• Status: Active Grant

• Current Assignee: PlaceIQ, Inc.
• Original Assignee: PlaceIQ, Inc.
• Inventors: Milton, Stephen, McCall, Duncan
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US15/331,845
• Publication Number:
  US 20170039242A1
• Time in Patent Office: 647 Days
• Field of Search: None
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06Q 30/0269 based on user profile or attribute
• 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

Provided is a process of merging data from feeds from multiple sources of computing device network activity data having heterogenous device identifier namespaces and device identifier to device mappings that change over time, the process including: accessing three or more sources of network activity log data from three or more different sources of network activity data, wherein: for each of the sources of network activity log data, based the respective network activity log data, updating a multi-namespace mapping that maps the external-namespace device identifiers to internal-namespace device identifiers in an internal namespace of a system configured to profile mobile computing devices based on logged network activity data of the mobile computing devices, wherein: the namespace mapping comprises a plurality of external-namespace-specific mappings each mapping a respective type of device identifier in a respective external namespace used in the network activity log data to one or more internal-namespace device identifiers.

Claims

1. A method of joining data from feeds from multiple sources of computing device network activity data having heterogenous device identifier namespaces and device identifier to device mappings that change over time, the method comprising:

accessing, with one or more processors, three or more sources of network activity log data from three or more different sources of network activity data, wherein;

each source of network activity log data describes network activity by more than 100,000 mobile computing devices,

each source of network activity log data describes activities over a duration of time longer than one hour,

each source of network activity log data provides transaction records of more than one 1 million transactions by at least some of the mobile computing devices, each transaction record including one or more external-namespace device identifiers in an external namespace of a respective mobile computing device participating in the respective network transaction, and

the transaction records associate geolocations reported by the mobile computing devices with timestamps and external-namespace device identifiers of the mobile computing devices;

for each of the sources of network activity log data, based the respective network activity log data, updating, with one or more processors, a multi-namespace mapping that maps the external-namespace device identifiers to internal-namespace device identifiers in an internal namespace of a system configured to profile mobile computing devices based on geolocations in logged network activity data of the mobile computing devices, wherein;

the namespace mapping comprises a plurality of external-namespace-specific mappings each mapping a respective type of device identifier in a respective external namespace used in the network activity log data to one or more internal-namespace device identifiers, and

at least some of the external-namespace device identifiers are mapped in at least some of the external-namespace-specific mappings to a plurality of internal-namespace device identifiers, with a given device external-namespace device identifier being mapped to a given plurality of internal-namespace device identifiers;

after updating the multi-namespace mapping, receiving, with one or more processors, an external-namespace device identifier;

selecting, with one or more processors, one of the external-namespace-specific mappings based on the external namespace of the received external-namespace device identifier;

accessing, with one or more processors, a plurality of internal-namespace device identifiers mapped to the received external-namespace device identifier by the selected external-namespace-specific mapping; and

accessing, with one or more processors, a device profile associated with at least some of the plurality internal-namespace device identifiers.

2. The method of claim 1, wherein updating the multi-namespace mapping comprises, for the given external-namespace device identifier:

determining to add a new internal-namespace device identifier mapping to the given external-namespace device identifier; and

adding the new internal-namespace device identifier as a new branch to a graph of the given plurality of internal-namespace device identifiers.

3. The method of claim 2, wherein the graph of the given plurality of device identifiers in the internal namespace comprises:

three or more internal-namespace device identifiers; and

edges indicating that some of the three or more internal-namespace device identifiers are newer versions of others of the three or more internal-namespace device identifiers.

4. The method of claim 2, wherein the graph is an acrylic graph and wherein nodes of the graph are associated with scores indicative of a likelihood that the corresponding internal-namespace device identifier is correctly assigned to the given external-namespace device identifier.

5. The method of claim 1, wherein each plurality of internal-namespace device identifiers mapped to a single external-namespace device identifier are associated with links between respective pairs of the internal-namespace device identifiers indicating relationships between the plurality of internal-namespace device identifiers.

6. The method of claim 1, wherein at least one of the external-namespace-specific mappings includes an associative array comprising key-value pairs, wherein:

keys of the key-value pairs are outputs of a hash function upon taking as an input an external-namespace identifier;

the keys of the key-value pairs are values in a sequential index of the associative array; and

values of the key-value pairs are internal-namespace device identifiers mapped to the corresponding external-namespace identifier that yields a hash function output of the corresponding key.

7. The method of claim 1, wherein at least one of the external-namespace-specific mappings is a tree in which branches represent different portions of the corresponding external namespace and at least some nodes are mapped to internal-namespace device identifiers corresponding to the portions of the corresponding external namespace.

8. The method of claim 1, wherein:

at least some internal-namespace device identifiers appear in a plurality of different external-namespace-specific mappings; and

at least some of the external-namespace-specific mappings correspond to different mobile operating systems from one another.

9. The method of claim 1, wherein:

updating the multi-namespace mapping comprises updating a subset of the multi-namespace mapping without re-calculating a different subset of the multi-namespace mapping.

10. The method of claim 1, wherein:

internal-namespace device identifiers mapped to external-namespace device identifiers change over time; and

both mappings from the external-namespace device identifiers to older and newer internal-namespace identifiers are maintained in the multi-namespace mapping after the changes.

11. The method of claim 1, wherein the external namespaces comprise:

identifiers for advertising assigned by a first operating system; and

advertising identifiers assigned by a second operating system different from the first operating system.

12. The method of claim 1, wherein:

the external namespaces include more than 6 different external namespaces, each of the different external namespaces including identifiers for devices that are represented in at least one of the other eternal namespace.

13. The method of claim 1, comprising:

determining that the given plurality of internal-namespace device identifiers comprises more than a threshold amount of the device identifiers and, in response, omitting a corresponding mapping from responses to access request for the given external-namespace device identifier.

14. The method of claim 1, comprising:

determining that another given internal-namespace device identifier is mapped in a given pair of external namespaces; and

determining that the given pair of external namespaces correspond to different operating systems and, in response, determining to not use at least one of the corresponding mappings.

15. The method of claim 1, wherein updating the multi-namespace mapping comprises steps for updating a multi-namespace mapping.

16. The method of claim 1, comprising:

profiling one of the mobile computing devices based on geolocations associated in the transaction records with different external-namespace device identifiers and in the multi-namespace mapping with at least one of the same internal-namespace device identifiers; and

storing a resulting profile in memory in association with one or more internal-namespace device identifiers of the one of the mobile computing devices.

17. The method of claim 16, comprising:

sending a computing system configured to select content for delivery to mobile computing devices data indicative of the profile and one or more external-namespace device identifiers associated with the one of the mobile computing devices;

receiving updated data from one of the sources of network activity log data from the computing system configured to select content for delivery to mobile computing devices; and

re-updating the multi-namespace mapping based on the updated data.

18. The method of claim 17, comprising:

receiving the updated data with means for handling real-time data feeds;

processing messages based on the updated data from the means for handling real-time data feeds with a compute cluster having means for concurrently processing the messages with fault tolerance;

updating the profile with means for profiling users; and

storing the updated profile in an in-memory, non-relational database.

19. The method of claim 18, comprising:

receiving an ad request; and

responding to the ad request within less than 200 milliseconds of receiving the ad request by querying the profile in the in-memory, non-relational database and determining a response to the ad request based on query results.

20. A system, comprising:

one or more processors; and

memory storing instructions that when executed by the processors cause the processors to effectuate operations comprising;

accessing three or more sources of network activity log data from three or more different sources of network activity data, wherein;

each source of network activity log data describes network activity by more than 100,000 mobile computing devices,

each source of network activity log data describes activities over a duration of time longer than one hour,

each source of network activity log data provides transaction records of more than one 1 million transactions by at least some of the mobile computing devices, each transaction record including one or more external-namespace device identifiers in an external namespace of a respective mobile computing device participating in the respective network transaction, and

the transaction records associate geolocations reported by the mobile computing devices with timestamps and external-namespace device identifiers of the mobile computing devices;

for each of the sources of network activity log data, based the respective network activity log data, updating a multi-namespace mapping that maps the external-namespace device identifiers to internal-namespace device identifiers in an internal namespace of a system configured to profile mobile computing devices based on geolocations in logged network activity data of the mobile computing devices, wherein;

the namespace mapping comprises a plurality of external-namespace-specific mappings each mapping a respective type of device identifier in a respective external namespace used in the network activity log data to one or more internal-namespace device identifiers, and

at least some of the external-namespace device identifiers are mapped in at least some of the external-namespace-specific mappings to a plurality of internal-namespace device identifiers, with a given device external-namespace device identifier being mapped to a given plurality of internal-namespace device identifiers;

after updating the multi-namespace mapping, receiving an external-namespace device identifier;

selecting one of the external-namespace-specific mappings based on the external namespace of the received external-namespace device identifier;

accessing a plurality of internal-namespace device identifiers mapped to the received external-namespace device identifier by the selected external-namespace-specific mapping; and

accessing a device profile associated with at least some of the plurality internal-namespace device identifiers.