Systems and methods for identifying a returning web client
View Patent ↗Methods and systems are provided for identifying unique devices and/or unique users of a web-based system within constraints of an external application. In some embodiments the process comprises receiving request information from a client device at an application server, using such information to form a device fingerprint, and attempting to match the newly-formed fingerprint with exactly one fingerprint stored in a database of previously-formed fingerprints. Some embodiments utilize a two-stage Locality-Sensitive Hash query technique. The client device fingerprint may be converted into a series of LSH values which may be used to find a matching fingerprint. A first stage may query input LSH values against LSH values in a data store, and a second stage may query LSH values temporarily held in volatile memory, thereby minimizing network traffic and reducing a total process time.
1. A non-transitory computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method for uniquely identifying returning client computing devices, the method comprising:
performing a first query with less than all available input Locality Sensitive Hash (LSH) values, the first query performed against a data store comprising a plurality of stored LSH values associated with a plurality of stored device fingerprints each fingerprint comprising a set of features identifying a particular computing device, wherein each input LSH value comprises a segment of an input fingerprint comprising a plurality of features obtained from a request from a client computing device, and wherein performing a first query comprises identifying in the data store a plurality of candidate LSH values, the candidate LSH values associated with candidate device fingerprints, at least including one candidate LSH value matching at least one of the less than all input LSH values;
performing a second query with at least one of the input LSH values not queried in the first query, the second query performed against the candidate LSH values, wherein the performing the second query comprises identifying the candidate LSH values matching at least one of the input LSH values not queried in the first query; and
based on responses to the first query and the second query, identifying a most closely matching device fingerprint.
2. The computer-readable medium of claim 1 , wherein the input fingerprint comprises n features, where n is an integer greater than one, and wherein the set of input LSH values comprises at least n input LSH values.
3. The computer-readable medium claim 2 , wherein each input LSH value comprises a segment of n−1 features of the input fingerprint.
4. The computer-readable medium of claim 3 , wherein n is between 2 and 200.
5. The computer-readable medium of claim 1 , wherein the input fingerprint comprises a character string or a binary string.
6. The computer-readable medium of claim 5 , wherein the each input LSH value comprises a k-character segment of the input fingerprint and wherein the input fingerprint comprises a concatenation of the plurality of features obtained from the client request data.
7. A method for identifying a client computing device from client request data that may comprise transitory data, implemented by a fingerprint server comprising a communication channel with a data storage device, the method comprising:
performing a first query with a plurality of input Locality Sensitive Hash (LSH) values, the first query performed against a data store comprising a plurality of stored LSH values associated with a plurality of stored device fingerprints, each device fingerprint comprising a set of features identifying a particular computing device and each stored LSH value comprising a segment of the associated stored device fingerprint wherein each segment is formed from only a portion of the associated device fingerprint, wherein each input LSH value comprises a segment of an input fingerprint comprising a plurality of features obtained from client request data identifying a client computing device, each segment formed from only a portion of the input fingerprint, and wherein performing the first query comprises investigating the data store to identify candidate LSH values, each candidate LSH value comprising a stored LSH value matching any of the input LSH values and, for each candidate LSH value, identifying candidate device fingerprints, each candidate device fingerprint comprising a stored fingerprint associated with the corresponding candidate LSH value;
performing a second query with at least one of the input LSH values not queried in the first query, the second query performed against the candidate LSH values, wherein the performing the second query comprises identifying the candidate LSH values matching at least one of the input LSH values not queried in the first query;
identifying, based on responses to the first query and the second query, a most closely matched candidate device fingerprint; and
determining that the most closely matched candidate device fingerprint and the input fingerprint correspond to the same client computing device or that the input fingerprint does not correspond to any client computing device in the data store.
8. The method of claim 7 , wherein performing the first query does not identify any candidate fingerprints associated with all of the input LSH values and identifying the most closely matched candidate fingerprint as a candidate device fingerprint having the largest number of matched LSH values.
9. The method of claim 8 , further comprising applying a similarity function to the most closely matched candidate device fingerprint and the input fingerprint to obtain a value representing the degree of similarity between the two fingerprints and, if similarity of the two fingerprints meets a threshold value, determining that the most closely matched candidate device fingerprint and the input fingerprint correspond to the same client computing device, or, if the value does not meet a threshold value, determining that the input fingerprint does not correspond to any client computing device in the data store.
10. The method of claim 9 , further comprising if the threshold value is met,
adding the input LSH values not matching any most closely matched LSH value and not matching any stored LSH value to the data store, wherein a most closely matched LSH value is associated with the most closely matched fingerprint;
associating the stored device fingerprint corresponding to the most closely matched fingerprint with the stored LSH values matching the input LSH value; and
removing the association between the stored device fingerprint corresponding to the most closely matched fingerprint and stored LSH value not matching any input LSH value.
11. The method of claim 10 , further comprising if the threshold value is met, removing from the data store any stored LSH value associated only with the stored fingerprint corresponding to the most closely matched candidate device fingerprint and not matching any input LSH value.
12. The method of claim 9 , further comprising if the threshold value is not met, adding the input LSH values that do not have a matching stored LSH value to the data store, adding the input fingerprint to data store, and associating the added input fingerprint with the stored LSH values matching the input LSH values.
13. The method of claim 7 , wherein the input fingerprint comprises n features, where n is an integer greater than one, and wherein the set of input LSH values comprises at least n input LSH values.
14. The method claim 13 , wherein each input LSH value comprises a segment of n−1 features of the input fingerprint.
15. The method of claim 14 , wherein n is between 2 and 200.
16. The method of claim 7 , wherein the input fingerprint comprises a character string or a binary string.
17. The method of claim 16 , wherein the each input LSH value comprises a k-character segment of the input fingerprint and wherein the input fingerprint comprises a concatenation of the plurality of features obtained from the client request data.
18. The method of claim 17 , wherein k is between 1 and 1000.
19. The method of claim 16 , wherein each input LSH value comprises a k-bit segment of the input fingerprint and wherein the input fingerprint comprises a binary string formed form the plurality of features obtained from the client request data.
20. The method of claim 7 , wherein the input and stored device fingerprints each comprise a user agent string, a list of installed browser plugins, a display size and/or color depth, a list of installed fonts, and/or an IP address of a computing device corresponding to the request from which the request features were obtained.