CODEWITHSUNDEEP
node.jsperformancefuse.js
codingmaster398
codingmaster398

Reputation: 257

fuse.js takes 10+ seconds with semi-long queries

I have a JSON database with 27k+ entries, and I'm using fuse.js to search through them. Each entry has about 500 characters of text in it.

When I search for something with 15+ characters, it takes a few seconds, and even more can slow the server to a halt while it processes it.

e.g. 1 results for 'crunchy munchy cheeeese' found in about 3.40 seconds.

var search = new Fuse(db.sites, {
  keys: ['t', 'dc','kw'], // Title, description and keywords
  threshold:0.4,
  minMatchCharLength:3
})
setInterval(() => {
  search.setCollection(db.sites) // Update the documents to the latest ones
}, 120000);

Any help on how to make this faster?

Upvotes: 2

Views: 3696

Answers (2)

Newbie
Newbie

Reputation: 4819

Fuse.js implements the Bitap algorithm which has a predictable complexity for exact match of O(nm). With n being the total corpus length and m being the pattern length. For fuzzy match this complexity grows approximately to O(mnl) with l being the maximum allowed Levenshtein distance.

From this is clear that length of the pattern affects directly and linearly the computation complexity of the search. The only way to mitigate this is to cap the pattern length.

Upvotes: 2

ejfrancis
ejfrancis

Reputation: 3035

I've run into issues w/Fuse being really slow with large datasets. Unfortunately the best solution for me was to just implement a basic fuzzy search myself by converting each searched property value to lowercase and comparing that against the search query which I also lowercased (to avoid case-sensitive issues) and then run it in a separate thread so that it doesn't block the main thread. Fuse doesn't seem to be designed for large datasets.

Upvotes: 0

Related Questions