batch_partial_match (381B)
1 # Batch partial match 2 3 Input: 4 - a database of n vectors of {0,1}^d 5 - n queries of the same form but with stars (wildcards) 6 Output: for each query you want to know if a vector of the database matches 7 8 Naive algorithms: 9 - try all pairs: O(n^2 d) 10 - preprocess all possible queries: O(2^d n) 11 12 [batch_partial_match_hypothesis] 13 14 Up: [fine_grained_complexity] 15 16 See also: [batch_updates]