Storing a sparse table

DOI10.1145/359168.359175MaRDI QIDQ3049828zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao, Robert E. Tarjan

Publication date 1979

Published in Communications of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/359168.359175

zbMATH Keywords

sparse matrixsearchingtable compressionstoring

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Cited in

(31)

• A link trie structure of storing multiple attribute relationships for natural language dictionaries
• Improved behaviour of tries by adaptive branching
• A compact representation of hierarchical relations using decimal notations
• A greedy approximation algorithm for constructing shortest common superstrings
• Graphs, hypergraphs and hashing
• Finite automata for compact representation of tuple dictionaries.
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Enumeration for FO Queries over Nowhere Dense Graphs
• Smaller representation of finite state automata
• New trie data structures which support very fast search operations
• A Table Compression Method for Extended Aho-Corasick Automaton
• Searching among intervals and compact routing tables
• Any-k algorithms for enumerating ranked answers to conjunctive queries
• NP-completeness on the length of double-arrays and the sparse matrix problem with at least logarithmic alphabets/widths
• Flash memory efficient LTL model checking
• An implicit data structure for searching a multikey table in logarithmic time
• A practical method for compressing sparse matrices with variant entries
• Information compression and Varshamov-Gilbert bound
• An Efficient Trie Construction for Natural Language Dictionaries
• Optimal non-adaptive cell probe dictionaries and hashing
• Searching among intervals and compact routing tables
• A practical method for implementing string pattern matching machines
• Tables should be sorted (on random access machines)
• A fast and compact technique of implementing transition tables for finite state automata
• An efficient representation for implementing finite state machines based on the double-array
• Perfect hashing
• Analysis of N-trees
• Dyn-FO: A parallel, dynamic complexity class
• A fast retrieval technique for large graph structures
• Order preserving extendible hashing and bucket tries
• Nearly Optimal Static Las Vegas Succinct Dictionary

This page was built for publication: Storing a sparse table

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3049828)