Combinatorics Approach to Probabilistic Geolocation

• US 20140279812A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Syracuse University
• Original Assignee: SRC, Inc.
• Inventors: Adelman, Jonathan David, McKay, William Ryon
• Granted Patent: US 9,336,490 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A method and system for geolocation. The method and system determines the geographic history of a target of interest (i.e., the probability that a sample of interest passed though a defined location) given a combination of spatially attributable input data and weighing distributions.

Claims

1. A probabilistic geolocation method, the method comprising:

acquiring spatially associated data from an obtained sample of interest;

enumerating all possible travel routes the sample of interest may have passed through based on the spatially associated data;

inputting said enumerated possible travel routes into a computer processor;

determining, by said processor, the frequency with which each possible geographic location appears in the travel routes; and

outputting, by said processor, a probability for said each possible geographic location.

2. The method of claim 1, further comprising the step of weighing the determined frequencies to account for a user'"'"'s assumptions.

3. The method of claim 1, wherein the outputted probability is conditional upon all travel routes being legal.

4. The method of claim 3, wherein the step of enumerating further comprises the step of calculating, by said processor, at least one minimal transversal for said sample of interest by treating an incidence matrix of the sample of interest and geographic locations as a hypergraph with the geographic locations as vertices and the spatially associated data detected on the sample of interest as an edge.

5. The method of claim 4, wherein the probability P(x) that the sample of interest passes through a given geographic location X is expressed using the following equation:

6. The method of claim 5, wherein the step of enumerating further comprises the step of utilizing, by said processor, the resulting at least one minimal transversal of the hypergraph as a seed that all legal routes must contain.

7. The method of claim 3, wherein the step of enumerating further comprises the step of utilizing, by said processor, Boolean satisfiability (SAT) problem in conjunctive normal form to model the sample of interest and geographic location information.

8. The method of claim 7, wherein the step of enumerating further comprises enumerating all possible travel routes by a #SAT solver.

9. The method of claim 3, further comprising the step of applying the following modification to the probability for each possible location:

10. The method of claim 1, further comprising the step of identifying said sample of interest, and inputting said identification of said sample of interest into said processor.

11. The method of claim 1, wherein said sample of interest contains spatially associated data selected from the group consisting of a first plant species identification gained from DNA taken from the sample of interest, a first species or genus identification via pollen grain morphology of pollen found on the sample of interest, and a first stable isotope detected on the sample of interest.

12. A probabilistic geolocation system comprising:

an enumeration module programmed to enumerate all possible travel routes a sample of interest may have passed through based on spatially associated data;

a frequency determination module connected to said enumeration module and programmed to determine the frequency with which each possible geographic location appears in the travel routes; and

an output module connected to the frequency module and structured to output to a client device a probability for said each possible location.