Combinatorics method for probabilistic geolocation

• US 9,336,490 B2
• Filed: 03/14/2013
• Issued: 05/10/2016
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Syracuse University
• Original Assignee: Syracuse University
• Inventors: McKay, William Ryon, Adelman, Jonathan David
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): Afolabi, Ola Olude
• Application Number:
  US13/829,556
• Publication Number:
  US 20140279812A1
• Time in Patent Office: 1,153 Days
• Field of Search: 706/12, 708/231
• US Class Current: 1/1
• 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, and modifying the probability for each possible location using the equation

$P\left(x\right)=\frac{{\sum }_k^K\left(w\left(k\right)·n_x\right)}{{\sum }_k^K\left(w\left(k\right)·n_t\right)},$
where P(x) is the probability that the sample of interest passes through a given geographic location X, n_t is the total number of possible legal travel routes for the sample of interest, n_x is the number of legal travel routes including location X, k is the travel route'"'"'s cardinality, and w(k) is the assigned weight for cardinality k from the user-defined weighting function.

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, wherein the outputted probability is conditional upon all travel routes being legal; and

applying the following modification to the probability for each possible 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 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.

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

5. The method of claim 4, 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.

6. The method of claim 1, 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.

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

8. 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.

9. 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.