Color-Distance Oracles and Snippets

摘要: In the snippets problem we are interested in preprocessing a text T so that given two pattern queries P_1 and P_2, one can quickly locate occurrences of patterns closest to each other. A closely related is constructing color-distance oracle, where goal preprocess set points from some metric space, which every point associated with colors, colors those as close possible other. We introduce efficient data structures for both oracles problem. Moreover, prove conditional lower bounds these problems 3SUM conjecture Combinatorial Boolean Matrix Multiplication conjecture.