Terrible worst case performance, almost halting

[ple1n]

I tested on a dataset with 1442910 words.

#[test]
fn test_worse_case() -> Result<()> {
    let case = "bring more land under cultivation";
    let conf = crate::config::get_config();
    let db_path = PathBuf::from(conf.data_path.clone());
    let db = offdict::<Strprox>::open_db(db_path)?;
    println!("testing");
    db.search(case, 3, false)?;
    Ok(())
}

I ran it with an input this long and it wouldnt finish.

https://github.com/planetoryd/offdict/tree/strprox

I made unrelated changes to your code. https://github.com/planetoryd/strprox/commits/master/

[ple1n]

Also you'd be interested in https://github.com/Validark/DynSDT

[ple1n]

I fixed it with ple1n@3a0321b

not graceful tho

[anusarati]

Hi, thanks for letting me know. I'm a little busy right now but I'll check it out later.

[anusarati]

@planetoryd
I'm checking to see if there's something wrong with my implementation compared to the paper. However, the paper does not have experimental results for queries with more than 10 characters, and it suggests segmenting queries into words in combination with techniques from other papers.

In the meantime, I'd like to merge your commits upstream if you don't mind.

[ple1n]

Is it possible to implement this algorithm with https://crates.io/crates/fst . IDK

[anusarati]

Looks interesting. I'm looking into it.

[ple1n]

Is this a feature, or an inherent problem of this algorithm ? I stop the search when the threshold gets too big, and that's result, which is embarrassing.

Perhaps I am not using it correctly. And I should probably introduce other algorithms to nullify its downsides, like pruning radix trie for exact matches before fuzzy is needed

[ple1n]

with more lenient caps.

[ple1n]

With that kind of performance it's hard to say what the point is. I can get threshold filtered results with FST with levenshtein-distance of one (which is effectively the same as top-k because its top one)

[anusarati]

The algorithm will always return the requested number of strings if there are enough strings in the dataset, whereas using a threshold of one may return less than that. In this case, it seems that it had to increase the threshold to get more strings, and if you used the threshold of 0, it would only return 1 string rather than 4.

A simple way to implement a top-k algorithm using FST is to try getting strings using Levenshtein automata beginning with an edit distance threshold of 0, then incrementally increasing the threshold by 1 if k strings weren't found. However, reconstructing Levenshtein automata and using the intersection operation incurs the overhead of reiterating through states. I haven't measured the performance of that approach and how it compares to my current implementation. I think reiteration can be avoided by using a Levensthein automaton with a threshold equal to the query length, and buffering states whose edit distances are higher than the current dynamic threshold to check later if less than k strings were found, but this may require a different implementation than the one currently in fst.

I have been working on an algorithm using FST but without Levenshtein automata.

[ple1n]

oh thats true. I figured out but forgot about that.

do you have an idea on the impl of cache. some kind of LRU should suffice, but its a lil bit different because of the structure.

[anusarati]

For my current implementation of META, the matching set, threshold, and the associated query prefix can be cached to resume searching through autocomplete_step when the user continues typing if the requested number of strings is the same. This can be done for each prefix of a query, and if the user deletes part of the query and continues typing, the cache for the unchanged prefix of the query can be accessed, and the cache for the prefixes of the previous query longer than that can be deleted or updated. The cache can be implemented using a vector where each index corresponds to a prefix length and each element has a cache entry/entries.

[ple1n]

I would like it return if there are results that are close and cheap, and not like the top-k manner which is expensive in practice. I'm not sure how to do it well.

  while query_prefix_len <= query_chars.len() {
            debug_println!(
                "{}/{}, active matching set, {}, threshold, {}. results {}/{}",
                query_prefix_len,
                query_chars.len(),
                active_matching_set.matchings.len(),
                threshold,
                result.len(),
                requested
            );
            result.clear();
            let mut set_delta = Default::default();
            let proposed_threshold = self.autocomplete_step(
                &mut active_matching_set,
                &query_chars[..query_prefix_len],
                query_prefix_len,
                threshold,
                requested,
                &mut result,
                &mut set_delta,
            );
           if set_delta.matchings.len() > MAX_SET_DELTA || proposed_threshold > MAX_DISTANCE {
                if requested == 1 {
                    return vec![];
                }
                query_prefix_len = 1;
                requested = 1;
                threshold = 1;
                active_matching_set = MatchingSet::<'stored, UUU, SSS>::new(&self.trie);
                continue;
            }
            threshold = proposed_threshold;
            active_matching_set.matchings.extend(set_delta.matchings);
            query_prefix_len += 1;
        }

The code above is naive

[ple1n]

There is usually one result within distance of one, and in worse cases the remaining of top-K requires searching through distance of 3, 4.