An Efficient Filter for Approximate Membership Checking

Summary: Proposes a filter-verification framework for approximate substring membership against a large dictionary, enabling efficient named-entity and biomedical concept extraction. Introduces a novel in-memory filter that prunes non-matches early, guarantees no false negatives, and outperforms prior methods in filtering power and runtime. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hfff34be678695036
Venue: SIGMOD
Year: 2008
Pagerank: 7.2531528e-05
Overall Rank: 3,501 | 76.47%
DOI: 10.1145/1376616.1376697

Incoming Non-self Citations Over Time

Authors

1. Kaushik Chakrabarti (Microsoft)
2. Surajit Chaudhuri (Microsoft)
3. Venkatesh Ganti (Microsoft)
4. Dong Xin (Microsoft)

BibTeX Citation

@inproceedings{chakrabarti_sigmod08,
        title = {{An Efficient Filter for Approximate Membership Checking}},
        author = {Chakrabarti, Kaushik and Chaudhuri, Surajit and Ganti, Venkatesh and Xin, Dong},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376697},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376697},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8519256e-05
3,512	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.2439455e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7803631e-05
4,736	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.4451961e-05
5,403	Mining Document Collections to Facilitate Accurate Approximate Entity Matching	2009	VLDB	6.1459021e-05
5,549	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.088104e-05
5,795	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.9926463e-05
6,848	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB	5.6658226e-05
7,389	Query Portals: Dynamically Generating Portals for Entity-Oriented Web Queries	2010	SIGMOD	5.5380047e-05
8,059	A Grammar-based Entity Representation Framework for Data Cleaning	2009	SIGMOD	5.3965759e-05
10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0418674e-05

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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,813	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB
2	4,493	Approximate String Joins with Abbreviations	2018	VLDB
3	5,549	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD
4	10,296	ChainedFilter: Combining Membership Filters by Chain Rule	2023	SIGMOD
5	10,299	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
6	6,605	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD
7	8,294	Approximate Substring Matching over Uncertain Strings	2011	VLDB
8	3,512	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD
9	10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
10	7,842	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD