Lower bounds for set intersection queries

DOI10.1007/BF01293666zbMATH Open0833.68037OpenAlexW3137191959MaRDI QIDQ1899448FDOQ1899448

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

Recommendations

• scientific article; zbMATH DE number 437544
• scientific article; zbMATH DE number 1114037
• Publication:4886068
• 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

zbMATH Keywords

memory restrictionset intersection reporting

Mathematics Subject Classification ID

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

Cites Work

• The Complexity of Maintaining an Array and Computing Its Partial Sums
• The power of geometric duality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower Bounds on the Complexity of Polytope Range Searching
• On the Complexity of Maintaining Partial Sums
• Title not available (Why is that?)
• A Lower Bound on the Complexity of Orthogonal Range Queries

Cited In (6)

• 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
• Title not available (Why is that?)

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)