Name
Abstract | ||
|---|---|---|
We investigate randomised algorithms for subset matching with spatial point sets--given two sets of d-dimensional points: a data set Tconsisting of npoints and a pattern Pconsisting of mpoints, 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(nlogm) 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-69507-3_17 | SOFSEM (1) |
Keywords | Field | DocType |
d-dimensional point,deterministic algorithm,correlation calculation,exact solution,subquadratic time,spatial point set,fast approximate point set,time algorithm,information retrieval,considerable practical speedup,time solution,fast fourier transform | Exact solutions in general relativity,Discrete mathematics,Combinatorics,Computer science,Fast Fourier transform,Point set,Speedup | Conference |
Volume | ISSN | Citations |
4362 | 0302-9743 | 1 |
PageRank | References | Authors |
0.41 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Benjamin Sach | 2 | 93 | 11.40 |