Palantir Technologies Inc.
FUZZY SEARCHING AND APPLICATIONS THEREFOR

Abstract:

A method, system and computer program product is disclosed for fuzzy searching. The method, which may be performed by one or more processors, may comprise providing a first prefix tree data structure representing a first data set comprising a first plurality of strings, and providing a second prefix tree data structure representing a second data set comprising a second plurality of strings. The first and second prefix tree data structures may each comprise nodes representing each character and edges connecting prefix nodes to one or more suffix nodes to represent each subsequent character in the string. A search may be performed to identify all matches between the first and second plurality of strings and also approximate matches between the first and second plurality of strings within a maximum distance k, wherein the search comprises traversing the first prefix tree data structure using a depth-first search algorithm to identify matches and approximate matches in the second prefix tree data structure.