c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
Given a dynamic set $K$ of $k$ strings of total length $n$ whose characters are drawn from an alphabet of size $\sigma$, a keyword dictionary is a data structure built on $K$ that provides locate, prefix search, and update operations on $K$. Under the assumption that $\alpha = w / \lg \sigma$ characters fit into a single machine word $w$, we propose a keyword dictionary that represents $K$ in $n \lg \sigma + \Theta(k \lg n)$ bits of space, supporting all operations in $O(m / \alpha + \lg \alpha)$ expected time on an input string of length $m$ in the word RAM model. This data structure is underlined with an exhaustive practical evaluation, highlighting the practical usefulness of the proposed data structure, especially for prefix searches - one of the most elementary keyword dictionary operations.
Code (1)
Similar Papers 제목 키워드 기반
KnowPrefix-Tuning: A Two-Stage Prefix-Tuning Framework for Knowledge-Grounded Dialogue Generation
Existing knowledge-grounded conversation systems generate responses typically in a retrieve-then-generate manner. They require a large knowledge base and a strong knowledge retrieval component, which is time- and resourc…
Dialogue GenerationResponse GenerationRetrievalTrie-NLG: Trie Context Augmentation to Improve Personalized Query Auto-Completion for Short and Unseen Prefixes
Query auto-completion (QAC) aims to suggest plausible completions for a given query prefix. Traditionally, QAC systems have leveraged tries curated from historical query logs to suggest most popular completions. In this …
Text GenerationCacheWeaver: Cache-Aware Evidence Ordering for Efficient Grounded RAG Inference
Retrieval-Augmented Generation (RAG) improves factual grounding, but it also lengthens prompts and raises prefill cost. Prefix caching in serving engines such as vLLM reduces this cost only when requests share the same t…
A Neural Corpus Indexer for Document Retrieval
Current state-of-the-art document retrieval solutions mainly follow an index-retrieve paradigm, where the index is hard to be directly optimized for the final retrieval target. In this paper, we aim to show that an end-t…
DecoderRetrievalTriviaQAKnow Before You Fetch: Calibrated Retrieval-Budget Allocation for Retrieval-Augmented Generation
Retrieval-augmented generation (RAG) typically retrieves a fixed number of passages for every query. This is wasteful when the reader already knows the answer, and it can be harmful when irrelevant or partially relevant …
Natural Questions