{'fraction_non_alphanumeric': 0.03690036900369004, 'fraction_numerical': 0.012300123001230012, 'mean_word_length': 4.575342465753424, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximate line nearest neighbor in high dimensions

We consider the problem of approximate nearest neighbors in high dimensions, when the queries are lines. In this problem, given n points in Rd, we want to construct a data structure to support efficiently the following queries: given a line L, report the point p closest to L. This problem generalizes the more familiar nearest neighbor problem. From a practical perspective, lines, and low-dimensional flats in general, may model data under linear variation, such as physical objects under different lighting. 
 
For approximation 1 + e, we achieve a query time of d3n0.5+t, for arbitrary small t > 0, with a space of d2nO(1/e2+1/t2). To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time.