@inproceedings{58be608e88ba42fe88dfaa4f32adc2b2,

title = "Fast Approximate Point Set Matching for Information Retrieval",

abstract = "We investigate randomised algorithms for subset matching with spatial point sets---given two sets of d-dimensional points: a data set T consisting of n points and a pattern P consisting of m points, find the largest match for a subset of the pattern in the data set. This problem is known to be 3-SUM hard and so unlikely to be solvable exactly in subquadratic time. We present an efficient bit-parallel O(nm) time algorithm and an O(n log(m)) time solution based on correlation calculations using fast Fourier transforms. Both methods are shown experimentally to give answers within a few percent of the exact solution and provide a considerable practical speedup over existing deterministic algorithms. ",

author = "Rapha{\"e}l Clifford and Benjamin Sach",

year = "2007",

doi = "10.1007/978-3-540-69507-3_17",

language = "English",

isbn = "9783540695066",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "212--223",

booktitle = "SOFSEM 2007: Theory and Practice of Computer Science",

address = "Germany",

}