License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.26
URN: urn:nbn:de:0030-drops-115222
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11522/
Huang, Ziyun ;
Feng, Qilong ;
Wang, Jianxin ;
Xu, Jinhui
Small Candidate Set for Translational Pattern Search
Abstract
In this paper, we study the following pattern search problem: Given a pair of point sets A and B in fixed dimensional space R^d, with |B| = n, |A| = m and n >= m, the pattern search problem is to find the translations T's of A such that each of the identified translations induces a matching between T(A) and a subset B' of B with cost no more than some given threshold, where the cost is defined as the minimum bipartite matching cost of T(A) and B'. We present a novel algorithm to produce a small set of candidate translations for the pattern search problem. For any B' subseteq B with |B'| = |A|, there exists at least one translation T in the candidate set such that the minimum bipartite matching cost between T(A) and B' is no larger than (1+epsilon) times the minimum bipartite matching cost between A and B' under any translation (i.e., the optimal translational matching cost). We also show that there exists an alternative solution to this problem, which constructs a candidate set of size O(n log^2 n) in O(n log^2 n) time with high probability of success. As a by-product of our construction, we obtain a weak epsilon-net for hypercube ranges, which significantly improves the construction time and the size of the candidate set. Our technique can be applied to a number of applications, including the translational pattern matching problem.
BibTeX - Entry
@InProceedings{huang_et_al:LIPIcs:2019:11522,
author = {Ziyun Huang and Qilong Feng and Jianxin Wang and Jinhui Xu},
title = {{Small Candidate Set for Translational Pattern Search}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {26:1--26:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11522},
URN = {urn:nbn:de:0030-drops-115222},
doi = {10.4230/LIPIcs.ISAAC.2019.26},
annote = {Keywords: Bipartite matching, Alignment, Discretization, Approximate algorithm}
}
|
Keywords: |
|
Bipartite matching, Alignment, Discretization, Approximate algorithm |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
