@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",
}