Method and Apparatus for Performing Similarity Searching

摘要

A system and method for performing similarity searching is disclosed wherein programmable logic devices such as field programmable gate arrays (FPGAs) can be used to implement Bloom filters for identifying possible matches between a query and data. The Bloom filters can be implemented in a parallel architecture where the different parallel Bloom filters share access to the same memory units. Further, a hash table may be generated to map a set of strings to keys. In other examples, the hash table may be used to map a set of substrings to a position in a larger string.

主权项

1. A system for generating a hash table for use in mapping a set of strings to keys, the system comprising:
a processor configured to provide near perfect hashing on the set of strings to (1) identify a location in a hash table, utilizing an H3 family of hash functions, corresponding to each string, and (2) generate the hash table, the hash table being configured to store, at each identified location therein, a key; and a memory in communication with the processor for storing the hash table, wherein the processor is configured to provide near perfect hashing via hash functions, utilizing the H3 family of hash functions, that are guaranteed to be of full rank.