Surpassing the information theoretic bound with fusion trees
From MaRDI portal
Publication:1317486
DOI10.1016/0022-0000(93)90040-4zbMath0795.68049OpenAlexW2074286662WikidataQ61051143 ScholiaQ61051143MaRDI QIDQ1317486
Michael L. Fredman, Dan E. Willard
Publication date: 24 March 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(93)90040-4
Searching and sorting (68P10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Data structures (68P05)
Related Items (93)
An algorithm for handling many relational calculus queries efficiently. ⋮ Trans-dichotomous algorithms for minimum spanning trees and shortest paths ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ I/O-efficient 2-d orthogonal range skyline and attrition priority queues ⋮ Dynamic layers of maxima with applications to dominating queries ⋮ Optimal Skeleton Huffman Trees Revisited ⋮ Dynamic nested brackets ⋮ A constant update time finger search tree ⋮ Predecessor queries in dynamic integer sets ⋮ Computing minimal and maximal suffixes of a substring ⋮ Dynamic Set Intersection ⋮ Oblivious RAM with \textit{worst-case} logarithmic overhead ⋮ Dynamic range majority data structures ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Sorting and searching revisted ⋮ Neighbours on a grid ⋮ Lower bounds for dynamic algorithms ⋮ Adjacency queries in dynamic sparse graphs ⋮ Near-optimal online multiselection in internal and external memory ⋮ Worst-Case Optimal Adaptive Prefix Coding ⋮ When can we sort in \(o(n\log n)\) time? ⋮ Improved parallel integer sorting without concurrent writing ⋮ A fast algorithm for adaptive prefix coding ⋮ Smoothing the Gap Between NP and ER ⋮ Fingerprints in compressed strings ⋮ The range 1 query (R1Q) problem ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Construct a perfect word hash function in time independent of the size of integers ⋮ On the succinct representation of equivalence classes ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Parallel construction of succinct trees ⋮ Palindrome pattern matching ⋮ A correction to Andersson's fusion tree construction ⋮ Internal shortest absent word queries in constant time and linear space ⋮ Trans-dichotomous algorithms without multiplication — some upper and lower bounds ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ Binary completely reachable automata ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Improved bounds for finger search on a RAM ⋮ Oblivious RAM with worst-case logarithmic overhead ⋮ Unnamed Item ⋮ Worst-case efficient single and multiple string matching on packed texts in the word-RAM model ⋮ The saga of minimum spanning trees ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ A subquadratic algorithm for 3XOR ⋮ Generic top-down discrimination for sorting and partitioning in linear time ⋮ Rank and select operations on a word ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem ⋮ Simple and efficient fully-functional succinct trees ⋮ Compressed subsequence matching and packed tree coloring ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ On Cartesian trees and range minimum queries ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Subquadratic algorithms for 3SUM ⋮ On the difficulty of range searching. ⋮ Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching ⋮ QUANTUM SEARCH ALGORITHM CAN BE IMPROVED ⋮ PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS ⋮ Unnamed Item ⋮ Integer priority queues with decrease key in constant time and the single source shortest paths problem ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Dynamic interpolation search revisited ⋮ Minimal indices for predecessor search ⋮ Nested Counters in Bit-Parallel String Matching ⋮ Ranked document selection ⋮ Unnamed Item ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ On data structures and asymmetric communication complexity ⋮ Sorting in linear time? ⋮ Fusion trees can be implemented with \(AC^0\) instructions only ⋮ Small-space LCE data structure with constant-time queries ⋮ LZ-End Parsing in Linear Time ⋮ A Survey on Priority Queues ⋮ Data structures for categorical path counting queries ⋮ Space-efficient Huffman codes revisited ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Unnamed Item ⋮ Improved fast integer sorting in linear space ⋮ Lower bounds for dynamic algebraic problems ⋮ Finding median in read-only memory on integer input ⋮ \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm ⋮ Succinct Color Searching in One Dimension ⋮ On-the-Fly Array Initialization in Less Space ⋮ Optimal bounds for the predecessor problem and related problems ⋮ Computing the maximum exponent in a stream
Cites Work
This page was built for publication: Surpassing the information theoretic bound with fusion trees
