validark / dynsdt

Dynamic Score-Decomposed Tries which more efficiently solve the prefix autocomplete problem

DynSDT Implementations

Dynamic Score-Decomposed Tries which solve the scored prefix completion problem. The C# version is the primary version at the moment. The preliminary TypeScript version in the main repo was created just to match the pseudocode from the paper to help verify the correctness of the pseudocode. The Zig version is still in-development.

Paper: validark.github.io/DynSDT, entitled Heap-like Dynamic Score-Decomposed Tries for Top-k Autocomplete

Live Demo: validark.github.io/DynSDT/demo

Email autocomplete proof-of-concept: validark.github.io/DynSDT/web-autocomplete

• This uses another TypeScript implementation I made which supports aliasing so multiple names/emails can autocomplete to the same person. The source code is available here.

Paper & Demo website code: /tree/paper

Give me a star if you appreciate this work!

Keywords: Query Autocomplete, QAC, type-ahead, ranked autosuggest, top-k autocomplete, trie decomposition, Dynamic Score-Decomposed Trie, trie autocomplete, Completion Trie.

dynsdt's Issues

Decrease array allocation size for the promotion algorithm

TODO

Demo

• Make transition from Completion Trie to decomposed trie animate the vertical linked lists into the parent nodes
• Dark mode
• Shift the Completion Trie and subsequent diagrams upwards slightly by default?

Paper

• Fix font inconsistency across platforms
  • Currently, Figures 1-3 use the "serif" font-family, which becomes the default serif font on whatever the target platform is. For consistency, a dynamically loaded font should be used or the text should be converted to paths.
    • At present, I'd prefer a dynamically loaded font
  • Change the Big-Theta from Georgia to a dynamically loaded font
  • Consider moving all diagrams to monospace or the KaTeX_Main font?
• Where $\large n$ and $\large bp[i]$ are identical, we should remove $\large n$ in favor of $\large bp[i]$
• Add an "Experimental Analysis" section
  • The main problem I have with this is that performance characteristics may vary by implementation. Maybe I will support an analysis for each of them, but without scripts only one will be shown?
  • Decide: Should I have a performance comparison with an implementation of the Completion Trie? Just horizontally sorted or should I include the totally unsorted Completion Trie as well?
  • Diagrams I am thinking to include:
    • How $\large k$ correlates with runtime
      • This will only use those prefix queries which are in the top-10 or top-100 of number of total completions in the entire dataset
    • How number of completions to a query (for all possible prefix string queries) correlates with runtime (when $\large k$ is set to 10)
• Submit to some academic platforms

Code

• Add implementations!

  • I am open to Pull Requests from others for more implementations!

  • This was the original version!
    • Add tests
    • Upload graphs (and code that generates them) for experimental analysis
    • #3
      • Previously, the maximum size was allocated

        DynSDT/c#/PruningRadixTrie/PruningRadixTrie.cs

        Line 906 in 4997b24

        var newPeers = new (Node node, int LCP)[termLength + 1 - prevLCP]; // maximum possible capacity

  • The initial implementation only exists to closely match the pseudocode in the paper, and the pseudocode was actually based on the C# version. The problem with the direct port is that the C# version wraps nodes in tuples, which are values, not actual objects with lifetimes. However, in TS/JS, there is no such concept, just objects. Hence, the TS version should have the LCP values moved into the node that it actually describes, to cut the number of JS objects in half.
  • Should be pretty easy to port from TypeScript, especially given my extensive experience developing https://roblox-ts.com/. Could probably be largely auto-generated.
  • Should be pretty similar to C#, right?
  • All your codebase are belong to us!
    • Maybe do some nice compression of the data structure?
  • I don't actually "know python" yet, but the constructs I need to write this library should be pretty trivial.
  • fast!
  • Make a table that displays the supported features for each version. More than likely, the initial implementation for many languages may not have numeric compression initially.