The Complexity of Some Simple Retrieval Problems

No abstract is available for this paper.

• Publication year

  1975

• Venue

  JACM

• Publication date

  1975-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/321892.321899
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The art of computer programming

  1983cited by this paper
• An analysis of optimal retrieval systems with updates

  1975cited by this paper
• Efficient Storage and Retrieval by Content and Address of Static Files

  1974cited by this paper
• Minimum Times and Memories Needed to Compute the Values of a Function

  1974cited by this paper
• Enumerative source encoding

  1973cited by this paper
• BOUNDS ON INFORMATION RETRIEVAL EFFICIENCY IN STATIC FILE STRUCTURES.

  1971cited by this paper
• Information Theory and Reliable Communication

  1969cited by this paper
• Information Theory and Reliable Communication

  1968cited by this paper
• Journal of the Association for Computing Machinery

  1961cited by this paper
• Teaching combinatorial tricks to a computer

  1960cited by this paper

• Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case

  2025cites this paper
• Stronger Cell Probe Lower Bounds via Local PRGs

  2025cites this paper
• The Hardest Explicit Construction

  2021cites this paper
• Recent Progress on Matrix Rigidity - A Survey

  2020cites this paper
• The Effect of Local Decodability Constraints on Variable-Length Compression

  2018cites this paper
• Flexible Indexing of Repetitive Collections

  2017cites this paper
• Unveiling Dynamics and Complexity

  2017influential citation
• Towards the Efficient Generation of Gray Codes in the Bitprobe Model

  2016cites this paper
• Practical combinations of repetition-aware data structures

  2016cites this paper
• Compressing sparse sequences under local decodability constraints

  2015cites this paper
• A Survey of Data Structures in the Bitprobe Model

  2013cites this paper
• Design of Practical Succinct Data Structures for Large Data Collections

  2013cites this paper
• Space-Time Tradeo s for Graph

  2010cites this paper
• Hashing, contention, and cell-probe proofs

  2009cites this paper
• No sorting? Better searching! [optimal array organization]

  2008cites this paper
• Abelian Hidden Subgroup Problem

  2008cites this paper
• Data Structuring Problems in the Bit Probe Model

  2007cites this paper
• Ììì Ðð Èöóó Óñôððüüøý Óó Ëù Blockin

  2007cites this paper
• Integer Representation and Counting in the Bit Probe Model

  2007cites this paper
• No Sorting? Better Searching!

  2004cites this paper
• The Cell Probe Complexity of Succinct Data Structures ∗

  2003cites this paper
• The cell probe complexity of succinct data structures

  2003cites this paper
• Are bitvectors optimal?

  2000cites this paper
• Membership in Constant Time and Almost-Minimum Space

  1999cites this paper
• Space-Time Tradeo s for Graph

  1999cites this paper
• Space-time Tradeoos for Graph Properties

  1999cites this paper
• Space-time Tradeoos for Graph Properties Space-time Tradeoos for Graph Properties

  1999cites this paper
• Cell probe complexity-a survey

  1999cites this paper
• Space Time Tradeoffs for Graph Properties

  1999cites this paper
• Space/time trade-offs for associative memory

  1996cites this paper
• Membership in Constant Time and Minimum Space

  1994cites this paper
• Lower bounds for union-split-find related problems on random access machines

  1994cites this paper
• The Bit Probe Complexity Measure Revisited

  1992influential citation
• Coding for recording and recall of information

  1984cites this paper
• Memory versus error trade-offs in binary-valued retrieval problems

  1984influential citation
• Communications via updates of shared memory

  1982cites this paper
• Should Tables Be Sorted?

  1981cites this paper
• Storage space versus validity of answers in probabilistic question-answering systems

  1980cites this paper
• Kraft storage and access for list implementations(Extended Abstract)

  1980cites this paper
• On the Least Redundancy Problem of the Queries of Order Two in Combinatorial Filing Scheme

  1979cites this paper
• Elasticity conditions for storage versus error exchange in question-Answering systems

  1979cites this paper
• Should Tables Be Sorted? Should Tables Be Sorted? *

  1979cites this paper
• Should tables be sorted?

  1978cites this paper
• Distinguishable codeword sets for shared memory

  1975cites this paper
• An analysis of optimal retrieval systems with updates

  1975cites this paper
• Space-time Tradeoos for Graph Properties Space-time Tradeoos for Graph Properties

  year unknowncites this paper
• Space-Time Tradeoffs for Graph Properties by Yevgeniy Dodis

  year unknowncites this paper