Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Mirror mirror... what am I typing next?

Mirror mirror... what am I typing next?

... a practical introduction into auto suggest.

A good search engine implementation shows relevant results to the user, but also helps getting there, as fast as possible. Often this is done using search as you type or suggest functionality, offering possible results while a user is typing.

This talk will cover the underlying data structures and algorithms to explain implementations behind a fast search as you type functionality using radix trees, finite state automatons and dive into advanced topics like ranking and boosting using concrete Java code for explanations and live demos.

Alexander Reelsen

May 24, 2023

More Decks by Alexander Reelsen

Other Decks in Technology


  1. Walk through dataset For each term: check if starts with

    input Collect until enough matches found Most naive implementation?
  2. List<String> suggest = new ArrayList<>(); @Test public void testSimpleSuggestions() {

    suggest.addAll(List.of("wakeboard", "washing machine", "washington wizards basketball", "water glass", "wax crayon", "werewolf mask", "wool socks")); suggest.sort(String.CASE_INSENSITIVE_ORDER); List<String> results = suggest("wa", 10); assertThat(results).containsExactly("wakeboard", "washing machine", "washington wizards basketball", "water glass", "wax crayon"); results = suggest("was", 1); assertThat(results).containsExactly("washing machine"); }
  3. private List<String> suggest(String input, int count) { return suggest.stream() .filter(s

    -> s.startsWith(input)) .limit(count) .toList(); } Scales with size of dataset Speed changes based on sorting Custom sorting possible Live updates! Naive implementation
  4. Find matches by walking the tree Fast Easy to figure

    out if no matches left Updateable No weighting? Do you spot the obvious optimization? Radix tree
  5. @Test public void testRadixTree() { ConcurrentRadixTree<Integer> radixTree = new ConcurrentRadixTree<>(new

    DefaultCharArrayNodeFactory()); radixTree.put("toast", 123); radixTree.put("test", 10); Iterable<KeyValuePair<Integer>> iterable = radixTree.getKeyValuePairsForClosestKeys("t"); // wrong order, requires resorting of all results... assertThat(iterable).map(KeyValuePair::getKey).containsExactly("test", "toast"); // this is inefficient Comparator<KeyValuePair<Integer>> cmp = (o1, o2) -> o2.getValue().compareTo(o1.getValue()); SortedSet<KeyValuePair<Integer>> response = new TreeSet<>(cmp); iterable.forEach(response::add); } Java implementation
  6. Check out the concurrent-trees library, unfortunately unmaintained Contains RadixTree ,

    ReversedRadixTree , InvertedRadixTree , SuffixTree implementations Lock free reads, concurrent writes, atomic updates Concurrent radix tree
  7. @Test public void testSampleDataset() { ConcurrentRadixTree<Integer> radixTree = new ConcurrentRadixTree<>(new

    DefaultCharArrayNodeFactory()); radixTree.put("wakeboard", 0); radixTree.put("washing machine", 0); radixTree.put("washington wizards basketball", 0); radixTree.put("water glass", 0); radixTree.put("wax crayon", 0); radixTree.put("werewolf mask", 0); radixTree.put("wool socks", 0); System.out.println(PrettyPrinter.prettyPrint(radixTree)); } PrettyPrinter
  8. ◦ └── ◦ w ├── ◦ a │ ├── ◦

    keboard (0) │ ├── ◦ shing │ │ ├── ◦ machine (0) │ │ └── ◦ ton wizards basketball (0) │ ├── ◦ ter glass (0) │ └── ◦ x crayon (0) ├── ◦ erewolf mask (0) └── ◦ ool socks (0) PrettyPrinter
  9. RadixTree, but with scoring! ... and early termination Idea comes

    from Wolf Garbe, see this blog post Java implementation: JPruningRadixTrie Pruning Radix Trie!
  10. @Test public void testPruningRadixTree() { PruningRadixTrie prt = new PruningRadixTrie();

    AtomicInteger counter = new AtomicInteger(1); for (String input : List.of("wakeboard", "washing machine", "washington wizards basketball", "water glass", "wax crayon", "werewolf mask", "wool socks")) { prt.addTerm(input, counter.getAndIncrement()); } List<TermAndFrequency> results = prt.getTopkTermsForPrefix("wa", 2); assertThat(results).map(t -> t.term() + "/" + t.termFrequencyCount()) .containsExactly( "wax crayon/6", "water glass/5" ); }
  11. De-facto standard for open source full text search Clones in

    many different programming languages Just turned 21! Lucene!
  12. String data = """ wakeboard\t1 washing machine\t2 washington wizards basketball\t3

    water glass\t4 wax crayon\t5 werewolf mask\t6 wool socks\t7 """;
  13. @Test public void testLuceneWFST() throws Exception { Directory directory =

    new NIOFSDirectory(Paths.get("/tmp/")); FileDictionary fileDictionary = new FileDictionary(new StringReader(data)); WFSTCompletionLookup lookup = new WFSTCompletionLookup(directory, "wfst", true); lookup.build(fileDictionary); List<Lookup.LookupResult> results = lookup.lookup("wa", null, false, 10); assertThat(results).hasSize(5); assertThat(results).map(Lookup.LookupResult::toString) .containsExactly("wax crayon/5", "water glass/4", "washington wizards basketball/3", "washing machine/2", "wakeboard/1"); } WeightedFST
  14. Extremely fast Build-once No updates Can be serialized to disk,

    loaded with small deserialization overhead 6 million terms require 42 MB of disk space FTS power: FuzzySuggester , phonetic suggestions, infix suggestions, synonyms FSTs
  15. @Test public void testFuzzySuggester() throws Exception { Directory directory =

    new NIOFSDirectory(Paths.get("/tmp/")); FuzzySuggester analyzingSuggester = new FuzzySuggester(directory, "suggest", new StandardAnalyzer()); FileDictionary fileDictionary = new FileDictionary(new StringReader(data)); analyzingSuggester.build(fileDictionary); List<Lookup.LookupResult> results = analyzingSuggester.lookup("wasch", false, 5); assertThat(results).hasSize(2); assertThat(results).map(Lookup.LookupResult::toString) .containsExactly("washing machine/1", "washington wizards basketball/1"); } FuzzySuggester
  16. @Test public void testPhoneticSuggest() throws Exception { Map<String, String> args

    = new HashMap<>(); args.put("encoder", "ColognePhonetic"); CustomAnalyzer analyzer = CustomAnalyzer.builder() .addTokenFilter(PhoneticFilterFactory.class, args) .withTokenizer("standard") .build(); Directory directory = new NIOFSDirectory(Paths.get("/tmp/")); AnalyzingSuggester suggester = new AnalyzingSuggester(directory, "lucene-tmp", analyzer); FileDictionary dictionary = new FileDictionary(new StringReader(input)); suggester.build(dictionary); List<Lookup.LookupResult> results = suggester.lookup("vaschink", false, 5); assertThat(results).map(Lookup.LookupResult::toString) .containsExactly("washington wizards basketball/3", "washing machine/2"); }
  17. @Test public void testInfixSuggester() throws Exception { Directory directory =

    new NIOFSDirectory(Paths.get("/tmp/")); AnalyzingInfixSuggester suggester = new AnalyzingInfixSuggester(directory, new StandardAnalyzer()); FileDictionary dictionary = new FileDictionary(new StringReader(input)); suggester.build(dictionary); List<Lookup.LookupResult> results = suggester.lookup("wiz", false, 5); assertThat(results).map(Lookup.LookupResult::toString) .containsExactly("washington wizards basketball/3"); results = suggester.lookup("ma", false, 5); assertThat(results).map(Lookup.LookupResult::toString) .containsExactly("werewolf mask/6", "washing machine/2"); } InfixSuggester
  18. What is weight? Popularity? Recency? Score current category higher Is

    this the same for every user? Include previous queries or purchases Multidimensional Ranking
  19. Elasticsearch search-as-you-type field type with rank_feature fields Returns full documents

    Vespa: Regular query, then rescoring against ML model Support for XGBoost, ONNX, LightGBM, Tensorflow Implementations
  20. Offline creation Incremental updates optional Synchronization with search engine No

    deserialization overhead Scalable readers Rescoring Are suggestions really worth all this work? Whiteboard implementation
  21. Auto-suggest is powerful Fix your search first before playing with

    auto-suggest Never point suggestions into no results ML/LTR: Zero-shot models (soon: model marketplaces?) Search moves to the edge! Change of search changes requirements: voice search chat gpt like search LLMs/Generative search up and coming (i.e. Vectara) Summary