Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing

Summary: Introduces Parallel LSH, a cache-conscious, multicore/ multinode variant with fast construction, duplicate elimination, insert-optimized storage, and expiration for streaming data. Scales similarity search to >1B tweets at 1–2.5 ms/query, up to 8.3× faster than basic LSH. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10867
Venue: VLDB
Year: 2013
Pagerank: 8.6438351e-05
Overall Rank: 2,390 | 83.61%
DOI: 10.14778/2556549.2556574

Incoming Non-self Citations Over Time

Authors

1. Narayanan Sundaram (Intel)
2. Aizana Turmukhametova (Massachusetts Institute of Technology)
3. Nadathur Satish (Intel)
4. Todd Mostak (Massachusetts Institute of Technology)
5. Piotr Indyk (Massachusetts Institute of Technology)
6. Samuel Madden (Massachusetts Institute of Technology)
7. Pradeep Dubey (Intel)

BibTeX Citation

@article{sundaram_vldb13,
        title = {{Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing}},
        author = {Sundaram, Narayanan and Turmukhametova, Aizana and Satish, Nadathur and Mostak, Todd and Indyk, Piotr and Madden, Samuel and Dubey, Pradeep},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1930--1941},
        doi = {10.14778/2556549.2556574},
        url = {https://doi.org/10.14778/2556549.2556574},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
1,515	ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data	2024	SIGMOD	0.00010521317
1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010407159
2,541	Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science	2018	VLDB	8.4500033e-05
4,927	Neighbor-Sensitive Hashing	2016	VLDB	6.4426453e-05
6,650	Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities	2025	SIGMOD	5.8146324e-05
7,166	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6846045e-05
7,240	Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search	2018	SIGMOD	5.6643589e-05
9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.3251649e-05
9,915	MicroNN: An On-device Disk-resident Updatable Vector Database	2025	SIGMOD	5.1955087e-05
10,036	VStream: A Distributed Streaming Vector Search System	2025	VLDB	5.173224e-05
10,435	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024932174
219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00024293529
221	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00024224879
591	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.0001603683
678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015061068
748	Effective Keyword Search in Relational Databases	2006	SIGMOD	0.00014381224
2,459	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.550768e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD
2	581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
3	3,866	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
4	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
5	10,265	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD
6	8,613	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD
7	6,597	Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories	2010	SIGMOD
8	5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
9	287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB
10	21	Similarity Search in High Dimensions via Hashing	1999	VLDB