DBScholar

Back to papers

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
4096
Venue
SIGMOD
Year
2008
Pagerank
7.4122197e-05
Overall Rank
3,442 | 76.39%
DOI
10.1145/1376616.1376697

Incoming Non-self Citations Over Time

Authors

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,886 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.5358137e-05
3,040 Leveraging Set Relations in Exact Set Similarity Join 2017 VLDB 7.8262287e-05
3,446 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.4087786e-05
4,052 Local Similarity Search for Unstructured Text 2016 SIGMOD 6.935988e-05
4,992 Scalable Ad-hoc Entity Extraction from Text Collections 2008 VLDB 6.4100657e-05
5,279 Mining Document Collections to Facilitate Accurate Approximate Entity Matching 2009 VLDB 6.2849137e-05
5,412 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.2272563e-05
5,667 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 6.1279762e-05
6,716 SigMatch: Fast and Scalable Multi-Pattern Matching 2010 VLDB 5.7958663e-05
7,252 Query Portals: Dynamically Generating Portals for Entity-Oriented Web Queries 2010 SIGMOD 5.6630343e-05
7,894 A Grammar-based Entity Representation Framework for Data Cleaning 2009 SIGMOD 5.5204248e-05
10,085 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.1559617e-05
Previous Page 1 / 1 Next

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.0010828372
21 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00056760516
107 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033511706
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
200 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025597287
Previous Page 1 / 1 Next

Semantically Similar Papers

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