Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories

Summary: TLSH, a TCAM-based ternary Locality Sensitive Hashing method for approximate NNS in Euclidean space, achieves near-linear storage and O(1) query time with a single TCAM access. Hashes to {0,1,*} using wildcards; validated on 1M-point data with high accuracy and 1.5M qps on a 1 Gb/s switch. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8050d02a4f5fa5f0
Venue: SIGMOD
Year: 2010
Pagerank: 5.7218669e-05
Overall Rank: 6,646 | 55.32%
DOI: 10.1145/1807167.1807209

Incoming Non-self Citations Over Time

Authors

1. Rajendra Shinde (Stanford University)
2. Ashish Goel (Stanford University)
3. Debojyoti Dutta (Cisco)
4. Pankaj Gupta (Twitter)

BibTeX Citation

@inproceedings{shinde_sigmod10,
        title = {{Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories}},
        author = {Shinde, Rajendra and Goel, Ashish and Dutta, Debojyoti and Gupta, Pankaj},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807209},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807209},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002230467
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
3,702	Identifying Representative Trends in Massive Time Series Data Sets Using Sketches	2000	VLDB	7.0842822e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
2	576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
3	3,236	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
4	1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
5	280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB
6	298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
7	5,796	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
8	2,362	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB
9	562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
10	20	Similarity Search in High Dimensions via Hashing	1999	VLDB