Size-estimation framework with applications to transitive closure and reachability
From MaRDI portal
Publication:1384531
DOI10.1006/jcss.1997.1534zbMath0897.68075OpenAlexW1965996575MaRDI QIDQ1384531
Publication date: 4 August 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1534
Related Items
Binary vectors for fast distance and similarity estimation ⋮ d-k-min-wise independent family of hash functions ⋮ Computing rarity on uncertain data ⋮ Spatially-decaying aggregation over a network ⋮ Analysis and application of adaptive sampling ⋮ Generalized substring selectivity estimation ⋮ Optimal sampling from sliding windows ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ Unnamed Item ⋮ Algorithms and estimators for summarization of unaggregated data streams ⋮ A unified scheme for generalizing cardinality estimators to sum aggregation ⋮ Efficient processing of substring match queries with inverted variable-length gram indexes ⋮ Better size estimation for sparse matrix products ⋮ On approximate range counting and depth ⋮ In-network estimation of frequency moments ⋮ Exponential time improvement for min-wise based algorithms ⋮ Communication lower bounds and optimal algorithms for numerical linear algebra ⋮ A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ How to catch \(L_2\)-heavy-hitters on sliding windows ⋮ Private multiparty sampling and approximation of vector combinations ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Unnamed Item ⋮ Simple multi-party set reconciliation ⋮ On the Complexity of Universal Leader Election ⋮ Unnamed Item ⋮ Distributed agreement in dynamic peer-to-peer networks
Cites Work
- Matrix multiplication via arithmetic progressions
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Parallel Depth-First Search in General Directed Graphs
- High-Probability Parallel Transitive-Closure Algorithms
- On optimizing multiplications of sparse matrices
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
