Method and computer program product for geospatial binning
Inventors
Beskales, George Anwar Dany • Bates-Haus, Nikolaus
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-10877948-B1
Publication Date
2020-12-29
Expiration Date
Abstract
Given a local distance metric for geospatial features, a binning is produced that is guaranteed to label features within a given distance threshold with the same bin, while labeling a minimum number of features separated by a distance that is greater than the threshold with the same bin.
Core Innovation
The invention provides a computer-implemented method for producing a dataset of all distinct pairs of geographic features where a distance between the features in each pair is less than a distance threshold. The method defines a distance function that provides a distance between two features and computes bins of the feature using the distance threshold so that, for any two features within the distance threshold, a set intersection of the bins for the two features contains at least one bin.
Using the binning dataset, the method computes, for each bin, all distinct pairs of features within the bin. For each distinct pair, the method computes a distance between the distinct pair using the distance function and stores the distinct pair in a pairs dataset when the computed distance is less than the distance threshold. The method then removes duplicate pairs from the pairs dataset, thereby producing a dataset of all distinct pairs of features where the distance between the features in each pair is less than the distance threshold.
The invention further includes refinements in which the bins are computed using a bin length parameter and in which the bins are relative spatial bins. The method also categorizes bin sizes using small bins and large bins, and defines bin-size dependent approaches for computing distinct feature pairs across bins and by subdividing large bins into sub-bins.
Claims Coverage
The document includes two independent claims that cover a computer-implemented method and a tangible computer program product for producing a dataset of all distinct pairs of geographic information system features within a distance threshold. Across the independent claims, three inventive features are central, with dependent claims further refining bin computation and bin-size handling.
Binning using threshold with set intersection guarantee
Computing bins of the feature using the distance threshold such that, for any two features within the distance threshold, a set intersection of the bins for the two features contains at least one bin, and storing the computed bins in a binning dataset.
Per-bin distinct pair generation with distance filtering
For each bin in the binning dataset, computing all distinct pairs of features within the bin; for each distinct pair, computing a distance between the distinct pair using the distance function and storing the distinct pair in a pairs dataset when the computed distance is less than the distance threshold.
Duplicate pair removal to produce all distinct pairs
Removing duplicate pairs from the pairs dataset, where a duplicate pair contains the same two features as another pair, thereby producing a dataset of all distinct pairs of features where the distance between the features in each pair is less than the distance threshold.
Non-transitory tangible program product
Non-transitory computer-readable media encoded with instructions for execution by a computer processor to perform the method.
The independent claims are anchored in binning based on a distance threshold with a set-intersection guarantee, generation of all distinct candidate pairs within bins followed by distance filtering, and removal of duplicate pairs to output a dataset of all distinct pairs. The independent method claim is mirrored by a non-transitory computer-readable media claim, and dependent claims further refine the bins using a bin length parameter, relative spatial bins, small bins, large bins, and subdividing large bins into sub-bins.
Stated Advantages
Produces a dataset of all distinct pairs of features where the distance between the features in each pair is less than the distance threshold.
Documented Applications
Produces a dataset of all distinct pairs of geographic information systems (GIS) features where pairwise distances are less than a distance threshold.
Interested in licensing this patent?