Optimally ranked nearest neighbor fuzzy full text search

Patent metadata

Field	Value
Publication number	US-8996501-B2
Application number	US-201113314412-A
Country	US
Kind code	B2
Filing date	Dec 8, 2011
Priority date	Dec 8, 2011
Publication date	Mar 31, 2015
Grant date	Mar 31, 2015

Abstract

A method and system for fuzzy full text search is disclosed. The system includes an inverted index where tokens are organized in a Next Valid Character (NVC) tree. Each path through the tree defines a token. The document sets for the tokens are stored at leaf nodes. After receiving search tokens, the system traverses the NVC tree in a lazy manner by exploring paths through nodes associated with the smallest edit distance. The system provides a result set per edit distance. For example, the system provides a result set of document identifiers associated with documents having the least amount of error first, followed by result sets of document identifiers associated with documents that have progressively more error.

First claim

I claim:

1. A computer-implemented method for performing fuzzy full text search, comprising:
receiving a search term;
initializing a priority queue by storing a first node and an edit distance of zero in the priority queue, wherein the priority queue comprises entries for each node in an inverted token next valid character tree that track the edit distance between the nodes and the search term;
exploring paths of the inverted token next valid character tree from the first node…

Assignees

• Pfeifle Martin
• Here Global Bv

Inventors

• Pfeifle Martin

Classifications

• G06F16/334 Primary

  Physics · mapped topic

• G06F16/2468

  Physics · mapped topic

• G06F17/30675 Primary

  Physics · mapped topic

• G06F17/30542

  Physics · mapped topic