Ett Bloom filter är en rymdeffektiv datastruktur som besvarar frågor om medlemskap med en viss chans till ett falskt positivt. Vi introducerar problemet med att utforma generaliseringar av Bloom filter utformade för att svara på frågor i formuläret, "Är x nära ett element av S?" där närhet mäts under ett lämpligt mått. En sådan datastruktur skulle ha flera naturliga tillämpningar i nätverks- och databastillämpningar. Vi visar hur lämpliga datastrukturer kan utformas med hjälp av lokalkänsliga hashfunktioner som byggsten, och vi analyserar specifikt prestandan hos ett naturligt system under hammingmåttet.
Kirscsh och Mitzenmacher REF föreslår en generalisering av Bloom filtret för att svara på frågor i formuläret "Är x nära ett element i filtret?" där närhet eller likhet definieras enligt hammningsmetoden.
Distance-Sensitive Bloom Filters
{'venue': 'In Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX', 'journal': None, 'mag_field_of_study': ['Computer Science']}