Patent Document ID: 9740798
Application ID: 14213495

Base Claim:
1. A system for inexact search acceleration using reference data, the system coupled to a host computing system, the system comprising: one or more memory circuits storing a plurality of queries and a FM-index of the reference data, each query comprising a sequence of a plurality of characters; and one or more field programmable gate arrays coupled to the one or more memory circuits, the one or more field programmable gate arrays configured to select a query from the plurality of queries; select a first or next substring of the selected query, the first or next substring comprising a subsequence of characters of the selected query; read a first or next section of the FM-index from the one or more memory circuits and calculate a plurality of suffix array intervals for the first or next substring with a corresponding plurality of prepended characters in a first or next position; read a first or next character in the first or next position of the query and select a first or next suffix array interval of the plurality of suffix array intervals for the read first character; determine whether the first or next suffix array interval is valid and whether a beginning of the query has been reached; return a first search result when the first or next suffix array interval is valid and the beginning of the query has been reached; and return a second search result that no match of the query with the reference data was found when the first or next suffix array interval is not valid.

---

Claim 15:
15. The system of claim 1 , wherein the one or more field programmable gate arrays are further configured to select, read, calculate, determine and return search results in parallel using a plurality of partitions of the plurality of queries for parallel searching.