Edit Question - KnowledgeHub

Title Body

Problem: Given a large (~100 million) list of unsigned 32-bit integers, an unsigned 32-bit integer input value, and a maximum Hamming Distance , return all list members that are within the specified Hamming Distance of the input value. Actual data structure to hold the list is open, performance requirements dictate an in-memory solution, cost to build the data structure is secondary, low cost to query the data structure is critical. Example: For a maximum Hamming Distance of 1 (values typically will be quite small) And input: 00001000100000000000000001111101 The values: 01001000100000000000000001111101 00001000100000000010000001111101 should match because there is only 1 position in which the bits are different. 11001000100000000010000001111101 should not match because 3 bit positions are different. My thoughts so far: For the degenerate case of a Hamming Distance of 0, just use a sorted list and do a binary search for the specific input value. If the Hamming Distance would only ever be 1, I could flip each bit in the original input and repeat the above 32 times. How can I efficiently (without scanning the entire list) discover list members with a Hamming Distance > 1.

Tags (comma-separated) Cancel