On the public citation graph

Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)

0 signed · 87 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-3-540-73951-7_4openalex-snapshot
Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
inferredcites →https://doi.org/10.1093/bioinformatics/17.5.419openalex-snapshot
Efficient large-scale sequence comparison by locality-sensitive hashing
inferredcites →https://doi.org/10.1109/69.908981openalex-snapshot
Finding interesting associations without support pruning
inferredcites →https://doi.org/10.1109/focs.2008.68openalex-snapshot
A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match
inferredcites →https://doi.org/10.1109/iccv.2003.1238424openalex-snapshot
Fast pose estimation with parameter-sensitive hashing
inferredcites →https://doi.org/10.1137/050646858openalex-snapshot
Lower Bounds on Locality Sensitive Hashing
inferredcites →https://doi.org/10.1145/1109557.1109690openalex-snapshot
Efficient algorithms for substring near neighbor problem
inferredcites →https://doi.org/10.1145/1242572.1242610openalex-snapshot
Google news personalization
inferredcites →https://doi.org/10.1145/1327452.1327494openalex-snapshot
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
inferredcites →https://doi.org/10.1145/276698.276876openalex-snapshot
Approximate nearest neighbors
inferredcites →https://doi.org/10.1145/997817.997857openalex-snapshot
Locality-sensitive hashing scheme based on p-stable distributions
inferredcites →https://doi.org/10.1184/r1/6604301openalex-snapshot
Computational Applications Of Noise Sensitivity
inferredcites →https://doi.org/10.1201/9781420035315.ch39openalex-snapshot
Nearest Neighbors in High-Dimensional Spaces
inferredcites →https://doi.org/10.3115/1219840.1219917openalex-snapshot
Randomized algorithms and NLP
inferredcites →https://doi.org/10.5555/1109557.1109688openalex-snapshot
Entropy based nearest neighbor search in high dimensions
inferredcites →https://doi.org/10.5555/1873601.1873695openalex-snapshot
A locality-sensitive hash for real vectors

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/cpe.6355openalex-snapshot
Toward more efficient locality‐sensitive hashing via constructing novel hash function cluster
inferred← citeshttps://doi.org/10.1007/978-3-030-84245-1_27openalex-snapshot
Lower Bounds on Lattice Sieving and Information Set Decoding
inferred← citeshttps://doi.org/10.1007/978-3-032-13589-6_19openalex-snapshot
Almost Linear Time Consistent Mode Estimation and Quick Shift Clustering
inferred← citeshttps://doi.org/10.1007/978-3-319-76578-5_14openalex-snapshot
Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving
inferred← citeshttps://doi.org/10.1007/978-3-319-90530-3_27openalex-snapshot
A New Algorithm for Finding Closest Pair of Vectors (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/978-981-10-6805-8_1openalex-snapshot
Locality-Sensitive Hashing for Finding Nearest Neighbors in Probability Distributions
inferred← citeshttps://doi.org/10.1007/s00453-020-00727-1openalex-snapshot
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
inferred← citeshttps://doi.org/10.1007/s00493-019-4113-1openalex-snapshot
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
inferred← citeshttps://doi.org/10.1007/s10559-017-9983-xopenalex-snapshot
Index Structures for Fast Similarity Search for Binary Vectors
inferred← citeshttps://doi.org/10.1007/s10559-018-0016-1openalex-snapshot
Index Structures for Fast Similarity Search for Real-Valued Vectors. I
inferred← citeshttps://doi.org/10.1016/j.ins.2020.04.046openalex-snapshot
GLDH: Toward more efficient global low-density locality-sensitive hashing for high dimensions
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.03.011openalex-snapshot
A new coding-based algorithm for finding closest pair of vectors
inferred← citeshttps://doi.org/10.1017/9781108769938openalex-snapshot
Small Summaries for Big Data
inferred← citeshttps://doi.org/10.1109/3dv.2016.41openalex-snapshot
Learning to Navigate the Energy Landscape
inferred← citeshttps://doi.org/10.1109/focs.2017.12openalex-snapshot
Distributed PCP Theorems for Hardness of Approximation in P
inferred← citeshttps://doi.org/10.1109/focs.2017.91openalex-snapshot
Optimal Las Vegas Locality Sensitive Data Structures
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00073openalex-snapshot
Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search
inferred← citeshttps://doi.org/10.1109/malware.2016.7888735openalex-snapshot
Malware provenance: code reuse detection in malicious software at scale
inferred← citeshttps://doi.org/10.1109/tpami.2017.2699960openalex-snapshot
A Survey on Learning to Hash
inferred← citeshttps://doi.org/10.1137/1.9781611973082.67openalex-snapshot
Approximate Nearest Neighbor Search for Low Dimensional Queries
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch1openalex-snapshot
Locality-sensitive Hashing without False Negatives
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch2openalex-snapshot
New directions in nearest neighbor searching with applications to lattice sieving
inferred← citeshttps://doi.org/10.1137/1.9781611974782.19openalex-snapshot
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
inferred← citeshttps://doi.org/10.1137/1.9781611974782.3openalex-snapshot
A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
inferred← citeshttps://doi.org/10.1137/1.9781611974782.4openalex-snapshot
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
inferred← citeshttps://doi.org/10.1137/1.9781611975994.39openalex-snapshot
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
inferred← citeshttps://doi.org/10.1137/15m1017958openalex-snapshot
Sketching and Embedding are Equivalent for Norms
inferred← citeshttps://doi.org/10.1142/9789813272880_0182openalex-snapshot
APPROXIMATE NEAREST NEIGHBOR SEARCH IN HIGH DIMENSIONS
inferred← citeshttps://doi.org/10.1142/s1469026817500195openalex-snapshot
Neural Skyline Filtering for Imbalance Features Classification
inferred← citeshttps://doi.org/10.1145/2745754.2745761openalex-snapshot
Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search
inferred← citeshttps://doi.org/10.1145/2746539.2746595openalex-snapshot
A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
inferred← citeshttps://doi.org/10.1145/2902251.2902285openalex-snapshot
On the Complexity of Inner Product Similarity Join
inferred← citeshttps://doi.org/10.1145/2983323.2983742openalex-snapshot
Scalability and Total Recall with Fast CoveringLSH
inferred← citeshttps://doi.org/10.1145/3055399.3055443openalex-snapshot
Set similarity search beyond MinHash
inferred← citeshttps://doi.org/10.1145/3155300openalex-snapshot
CoveringLSH
inferred← citeshttps://doi.org/10.1145/3174804openalex-snapshot
A Faster Subquadratic Algorithm for Finding Outlier Correlations
inferred← citeshttps://doi.org/10.1145/3178540openalex-snapshot
Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor
inferred← citeshttps://doi.org/10.1145/3188745.3188916openalex-snapshot
Hardness of approximate nearest neighbor search
inferred← citeshttps://doi.org/10.1145/3196959.3196976openalex-snapshot
Distance-Sensitive Hashing
inferred← citeshttps://doi.org/10.1145/3461777openalex-snapshot
Optimal Las Vegas Approximate Near Neighbors in ℓ p
inferred← citeshttps://doi.org/10.1145/3532624openalex-snapshot
A Survey on Deep Hashing Methods
inferred← citeshttps://doi.org/10.1145/3564246.3585168openalex-snapshot
Streaming Euclidean MST to a Constant Factor
inferred← citeshttps://doi.org/10.1145/3618260.3649666openalex-snapshot
Data-Dependent LSH for the Earth Mover’s Distance
inferred← citeshttps://doi.org/10.1155/2016/4075257openalex-snapshot
A Novel Accuracy and Similarity Search Structure Based on Parallel Bloom Filters
inferred← citeshttps://doi.org/10.1287/moor.2021.1221openalex-snapshot
Local Density Estimation in High Dimensions
inferred← citeshttps://doi.org/10.1371/journal.pone.0188702openalex-snapshot
Real-time community detection in full social networks on a laptop
inferred← citeshttps://doi.org/10.14778/3368289.3368303openalex-snapshot
Return of the Lernaean Hydra
inferred← citeshttps://doi.org/10.14778/3397230.3397243openalex-snapshot
iDEC
inferred← citeshttps://doi.org/10.1609/aaai.v31i1.10989openalex-snapshot
S2JSD-LSH: A Locality-Sensitive Hashing Schema for Probability Distributions
inferred← citeshttps://doi.org/10.24033/ast.1189openalex-snapshot
Average distortion embeddings, nonlinear spectral gaps, and a metric John theorem
inferred← citeshttps://doi.org/10.25148/etd.fidc007791openalex-snapshot
A New Study of Applying Complexity Theoretical Tools in Algorithm Design
inferred← citeshttps://doi.org/10.26053/0h-00mq-z7g0openalex-snapshot
Bounds for nearest neighbor algorithms and embeddings
inferred← citeshttps://doi.org/10.4230/lipics.cpm.2023.20openalex-snapshot
Differentially Private High-Dimensional Approximate Range Counting, Revisited
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2018.42openalex-snapshot
Lattice-based Locality Sensitive Hashing is Optimal
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2019.17openalex-snapshot
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2017.7openalex-snapshot
Fast Cross-Polytope Locality-Sensitive Hashing
inferred← citeshttps://doi.org/10.4230/lipics.socg.2015.436openalex-snapshot
Low-Quality Dimension Reduction and High-Dimensional Approximate Nearest Neighbor
inferred← citeshttps://doi.org/10.48550/arxiv.1507.03225openalex-snapshot
CoveringLSH: Locality-sensitive Hashing without False Negatives
inferred← citeshttps://doi.org/10.48550/arxiv.1509.02897openalex-snapshot
Practical and Optimal LSH for Angular Distance
inferred← citeshttps://doi.org/10.48550/arxiv.1511.07527openalex-snapshot
Tradeoffs for nearest neighbors on the sphere
inferred← citeshttps://doi.org/10.48550/arxiv.1601.03958openalex-snapshot
Real-Time Community Detection in Large Social Networks on a Laptop
inferred← citeshttps://doi.org/10.48550/arxiv.1605.02701openalex-snapshot
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
inferred← citeshttps://doi.org/10.48550/arxiv.1612.07405openalex-snapshot
Practical linear-space Approximate Near Neighbors in high dimension
inferred← citeshttps://doi.org/10.48550/arxiv.1705.02828openalex-snapshot
Faster tuple lattice sieving using spherical locality-sensitive filters
inferred← citeshttps://doi.org/10.48550/arxiv.1802.09104openalex-snapshot
A New Algorithm for Finding Closest Pair of Vectors
inferred← citeshttps://doi.org/10.48550/arxiv.1807.07527openalex-snapshot
Optimal Las Vegas Approximate Near Neighbors in $\ell_p$
inferred← citeshttps://doi.org/10.48550/arxiv.1812.01557openalex-snapshot
Optimal Boolean Locality-Sensitive Hashing
inferred← citeshttps://doi.org/10.48550/arxiv.1906.09430openalex-snapshot
Algorithms for Similarity Search and Pseudorandomness
inferred← citeshttps://doi.org/10.48550/arxiv.2006.11459openalex-snapshot
Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search
inferred← citeshttps://doi.org/10.5555/3039686.3039691openalex-snapshot
LSH forest: practical algorithms made theoretical
inferred← citeshttps://doi.org/10.5555/3310435.3310543openalex-snapshot
Optimal las vegas approximate near neighbors in lp
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.