Tightly Packed Tries: How to Fit Large Models into Memory, and Make them Load Fast, Too

We present Tightly Packed Tries (TPTs), a compact implementation of read-only, compressed trie structures with fast on-demand paging and short load times. We demonstrate the benefits of TPTs for storing n-gram back-off language models and phrase tables for statistical machine translation. Encoded as TPTs, these databases require less space than flat text file representations of the same data compressed with the gzip utility. At the same time, they can be mapped into memory quickly and be searched directly in time linear in the length of the key, without the need to decompress the entire file. The overhead for local decompression during search is marginal.

• Publication year

  2009

• Venue

  Unknown venue

• Publication date

  2009-06-05

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/1621947.1621952
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Text Compression

  2009cited by this paper
• Manageable Phrase-Based Statistical Machine Translation Models

  2008cited by this paper
• Randomized Language Models via Perfect Hash Functions

  2008cited by this paper
• Compressing Trigram Language Models With Golomb Coding

  2007cited by this paper
• Efficient Handling of N-gram Language Models for Statistical Machine Translation

  2007influential reference
• Large Language Models in Machine Translation

  2007cited by this paper
• Moses: Open Source Toolkit for Statistical Machine Translation

  2007cited by this paper
• Improving Translation Quality by Discarding Most of the Phrasetable

  2007cited by this paper
• Efficient Phrase-Table Representation for Machine Translation with Applications to Online MT and Speech Translation

  2007cited by this paper
• How Many Bits Are Needed To Store Probabilities for Phrase-Based Translation?

  2006cited by this paper
• PORTAGE: A Phrase-Based Machine Translation System

  2005cited by this paper
• The Bloomier filter: an efficient data structure for static support lookup tables

  2004cited by this paper
• SRILM - an extensible language modeling toolkit

  2002cited by this paper
• Entropy-based Pruning of Backoff Language Models

  2000cited by this paper
• Statistical language modeling using the CMU-cambridge toolkit

  1997cited by this paper
• Estimation of probabilities from sparse data for the language model component of a speech recognizer

  1987cited by this paper
• Run-length encodings.

  1966cited by this paper
• Trie memory

  1960cited by this paper
• A method for the construction of minimum-redundancy codes

  1952cited by this paper

• A Survey of Multi-Dimensional Indexes: Past and Future Trends

  2024cites this paper
• Knowledge Infused Decoding

  2022cites this paper
• A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues

  2021cites this paper
• MergedTrie: Efficient textual indexing

  2019cites this paper
• Efficient Processing of Range Queries in Main Memory

  2019cites this paper
• Architecture for Efficient String Dictionaries in E-Learning

  2018cites this paper
• PaIndex: An online index system for vehicle trajectory data exploiting parallelism

  2017cites this paper
• Developing a Holistic Understanding of Systems and Algorithms through Research Papers

  2017cites this paper
• Simulating Chemical Reactions Using a Swarm of Miniature Robots

  2016cites this paper
• Book Review: Syntax-Based Statistical Machine Translation by Philip Williams, Rico Sennrich, Matt Post and Philipp Koehn

  2016cites this paper
• Single‐scan: a fast star‐join query processing algorithm

  2016cites this paper
• A Fast and Compact Language Model Implementation Using Double-Array Structures

  2016cites this paper
• Fast, Small and Exact: Infinite-order Language Modelling with Compressed Suffix Trees

  2016cites this paper
• Debugging the Internet of Things: The Case of Wireless Sensor Networks

  2015cites this paper
• Parallel parsing made practical

  2015cites this paper
• Compact, Efficient and Unlimited Capacity: Language Modeling with Compressed Suffix Trees

  2015cites this paper
• A SYNTAX DIRECTED APPROACH TO EXPLOIT PARALLELISM IN XML-QUERY LANGUAGES

  2015cites this paper
• Dynamic phrase tables for machine translation in an interactive post-editing scenario

  2014cites this paper
• The 11th Conference of the Association for Machine Translation in the Americas Workshop on Interactive and Adaptive Machine Translation

  2014cites this paper
• The PH-tree: a space-efficient storage structure and multi-dimensional index

  2014cites this paper
• Efficient Latent-variable Grammars : Learning and Inference

  2014cites this paper
• EXACT SAMPLING AND OPTIMISATION IN STATISTICAL MACHINE TRANSLATION

  2014cites this paper
• Metoda analize otpornosti i kvalitete lozinki zaštićenih pomoću kriptografskih jednosmjernih funkcija ; Method for analyzing password strength for passwords protected with cryptographic hash functions

  2014cites this paper
• Sticky tries: fast insertions, fast lookups, no deletions for large key universes

  2014cites this paper
• Efficient Language Modeling Algorithms with Applications to Statistical Machine Translation

  2013cites this paper
• An Efficient Language Model Using Double-Array Structures

  2013cites this paper
• The New IDS Corpus Analysis Platform: Challenges and Prospects

  2012cites this paper
• Simple and Efficient Model Filtering in Statistical Machine Translation

  2012cites this paper
• PAPAGENO: A Parallel Parser Generator for Operator Precedence Grammars

  2012cites this paper
• Phrasal Rank-Encoding: Exploiting Phrase Redundancy and Translational Relations for Phrase Table Compression

  2012cites this paper
• Prius: generic hybrid trace compression for wireless sensor networks

  2012cites this paper
• A fast and flexible architecture for very large word n-gram datasets

  2012cites this paper
• Elastic, Reliable, and Robust Storage and Query Processing with Crescando/RB

  2012cites this paper
• An Enhanced Approach for Compress Transaction Databases

  2012cites this paper
• Unary Data Structures for Language Models

  2011cites this paper
• Faster and Smaller N-Gram Language Models

  2011influential citation
• KenLM: Faster and Smaller Language Model Queries

  2011influential citation
• Efficient Minimal Perfect Hash Language Models

  2010cites this paper
• Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval

  2010cites this paper
• PortageLive: delivering machine translation technology via virtualization

  2009influential citation
• Edinburgh Research Explorer Phrasal Rank-Encoding: Exploiting Phrase Redundancy and Translational Relations for Phrase Table Compression

  year unknowncites this paper