Method and system for efficient feature matching

Patent metadata

Field	Value
Publication number	US-2016179893-A1
Application number	US-201414579297-A
Country	US
Kind code	A1
Filing date	Dec 22, 2014
Priority date	Dec 22, 2014
Publication date	Jun 23, 2016
Grant date	—

Abstract

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.

First claim

What is claimed is:

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, 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;
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.

2 . The method claimed in claim 1 , further comprising selecting a scalar quantizer, wherein expanding the set includes first quantizing the data points in the set of data points.

3 . The method claimed in claim 1 , further comprising storing the expanded set in memory for future searching.

4 . The method claimed in claim 1 , further comprising storing the binary array in memory for future searching and discarding the expanded set.

5 . The method claimed in claim 1 , wherein the error distance comprises one of L1 distance, L2 distance, editing distance, earth moving distance, KL divergence, and structural similarity matrix.

6 . The method claimed in claim 1 , wherein the determining, expanding and creating operations are performed at least twice for distinct threshold error value to produce corresponding binary arrays, and wherein receiving a query comprises receiving the query and a requested threshold error, and further comprising selecting one of the at least two binary arrays based upon the requested threshold error.

7 . The method claimed in claim 6 , wherein selecting one of the at least two binary arrays is based upon selecting the binary array corresponding to a threshold error value greater than or equal to the requested threshold error.

8 . The method claimed in claim 1 , wherein constructing a binary array comprises:
classifying the data elements of the expanded set into one of two classes; applying a first bloom filter to all data element of the expanded set to create a first binary array; and applying a second bloom filter to data elements of one of the classes but not to data element of the other of the classes, to create a second binary array, wherein the first bloom filter has a higher false positive probability than the second bloom filter.

9 . The method claimed in claim 1 , wherein the determining, expanding and creating operations are performed by a server, wherein the receiving and applying operations are performed by a remote device in communication with the server, and wherein the server transmits the summary representation to the remote device in reply to a request from the remote device.

10 . The method claimed in claim 1 , wherein the set of data points comprise fingerprint data.

11 . The method claimed in claim 1 , wherein the set of data points comprise image or video feature descriptors.

12 . A search system for non-identical feature matching, the search system comprising:
one or more processors; memory storing a set of data points and a threshold error; and processor-executable search instructions that, when executed by the one or more processors cause the one or more processors to:
expand 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, 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,

create a summary representation of the expanded set by constructing a binary array using a plurality of hash functions as a bloom filter;
receive a query; and
apply 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.

13 . The search system claimed in claim 12 , further comprising instructions that, when executed by the one or more processors cause the one or more processors to select a scalar quantizer, wherein expanding the set includes first quantizing the data points in the set of data points.

14 . The search system claimed in claim 12 , further comprising instructions that, when executed by the one or more processors cause the one or more processors to store the expanded set in memory for future searching.

15 . The search system claimed in claim 12 , further comprising instructions that, when executed by the one or more processors cause the one or more processors to store the binary array in memory for future searching and discard the expanded set.

16 . The search system claimed in claim 12 , wherein the error distance comprises one of L1 distance, L2 distance, editing distance, earth moving distance, KL divergence, and structural similarity matrix.

17 . The search system claimed in claim 12 , wherein the determining, expanding and creating operations are performed at least twice for distinct threshold error value to produce corresponding binary arrays, and wherein the query received includes a requested threshold error, and wherein the search system further comprises instructions that, when executed by the one or more processors cause the one or more processors to select one of the at least two binary arrays based upon the requested threshold error.

18 . The search system claimed in claim 17 , wherein selecting one of the at least two binary arrays is based upon selecting the binary array corresponding to a threshold error value greater than or equal to the requested threshold error.

19 . The search system claimed in claim 12 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to construct the binary array by:
classifying the data elements of the expanded set into one of two classes; applying a first bloom filter to all data element of the expanded set to create a first binary array; and applying a second bloom filter to data elements of one of the classes but not to data element of the other of the classes, to create a second binary array, wherein the first bloom filter has a higher false positive probability than the second bloom filter.

20 . A non-transitory processor-readable medium storing processor-executable instructions which, when executed, cause one or more processors to perform the method claimed in claim 1 .

Assignees

• Blackberry Ltd

Inventors

• He Dake

Classifications

• G06F16/90335

  Query processing · CPC title

• G06F16/24558

  Binary matching operations · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/2237 Primary

  Vectors, bitmaps or matrices · CPC title

• G06F16/48

  Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually · CPC title