Reproduce “Streaming Facility Location in High Dimension via Geometric Hashing” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang
A framework combining geometric importance sampling with consistent geometric hashing addresses the Euclidean Uniform Facility Location problem in high-dimensional dynamic geometric streams. This method achieves an O(1)-approximation for two-pass and random-order one-pass streams, and an O(d/log d)-approximation for arbitrary-order one-pass streams, utilizing poly(d log ) space to improve upon existing quadtree-based solutions.
Key insights
- The ` ( log )` approximation barrier in high-dimensional geometric streaming can be fundamentally circumvented by moving away from quadtree-based methods.
- Effective importance sampling in streaming can be achieved by implicitly leveraging a new type of consistent geometric hashing to approximate ` _p` values without explicit computation.
- Careful design of consistent hashing functions with tunable ` ` (gap) and ` ` (consistency) parameters allows for a trade-off between the approximation ratio and computational efficiency for high-dimensional problems.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.