Lower bounds for set intersection queries

DOI10.1007/BF01293666MaRDI QIDQ1899448zbMATH OpenOpenAlexFDO

Authors Paul F. Dietz, K. Mehlhorn, Rajeev Raman, Christian Uhrig

Publication date 9 October 1995

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01293666

zbMATH Keywords

memory restrictionset intersection reporting

Mathematics Subject Classification ID

Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 437544
• scientific article; zbMATH DE number 1114037
• scientific article; zbMATH DE number 910893
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Bounded queries to arbitrary sets
• Intersection queries in sets of disks
• Intersection queries in sets of disks
• Beyond set disjointness
• New upper bounds for generalized intersection searching problems

Cites work

• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 742985 (Why is no real title available?)
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Lower Bounds on the Complexity of Polytope Range Searching
• On the Complexity of Maintaining Partial Sums
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• The power of geometric duality

Cited in

(6)

• scientific article; zbMATH DE number 1114037 (Why is no real title available?)
• Dynamic set intersection
• A Theory of Local Set Queries
• Dynamic and internal longest common substring
• Maximal intersection queries in randomized input models
• Intersection queries in sets of disks

This page was built for publication: Lower bounds for set intersection queries

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