Loading...
Please wait, while we are loading the content...
Similar Documents
Fast approximate point set matching for information retrieval.
| Content Provider | CiteSeerX |
|---|---|
| Author | Clifford, Raphaël Sach, Benjamin |
| Abstract | 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(nlog 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. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Time Solution Efficient Bit-parallel Subquadratic Time Subset Matching Data Set Exact Solution D-dimensional Point Fast Approximate Point Set Matching Deterministic Algorithm Spatial Point Set Time Algorithm Data Set Consisting Fourier Transforms Correlation Calculation Information Retrieval Considerable Practical Speedup Pattern Consisting |
| Content Type | Text |
