METHOD AND SYSTEM FOR EFFICIENT FEATURE MATCHING

摘要

A method of non-identical feature matching in a search system, the search system having a set of data points. The method includes determining a threshold error and expanding the set to create an expanded set by including all data points as data elements of the expanded set and, for every data point in the set, finding all data elements within an error distance of that data point and adding those found data elements to the expanded set, wherein the error distance is a function of the threshold error. The method includes creating a summary representation of the expanded set by constructing a binary array using a plurality of hash functions as a bloom filter. The method may further include receiving a query and applying the plurality of hash functions to the query to determine, from the binary array, whether the query matches one of the data elements in the expanded set and, if so, outputting a match.

主权项

1. A method of non-identical feature matching in a search system, the search system having a set of data points, the method comprising:
determining a threshold error; expanding the set to create an expanded set by,
initializing the expanded set to include all data points from the set as data elements of the expanded set, andfor every data point in the set, finding all data elements within an error distance of that data point and adding those found data elements to the expanded set, wherein the error distance is a function of the threshold error; creating a summary representation of the expanded set by constructing a binary array using a plurality of hash functions as a bloom filter; receiving a query; and applying the plurality of hash functions to the query to determine, from the binary array, whether the query matches one of the data elements in the expanded set and, if so, outputting a match.