  The concept of matching dependencies (mds) is recently pro- posed for
specifying matching rules for object identification. Similar to the functional
dependencies (with conditions), mds can also be applied to various data quality
applications such as violation detection. In this paper, we study the problem
of discovering matching dependencies from a given database instance. First, we
formally define the measures, support and confidence, for evaluating utility of
mds in the given database instance. Then, we study the discovery of mds with
certain utility requirements of support and confidence. Exact algorithms are
developed, together with pruning strategies to improve the time performance.
Since the exact algorithm has to traverse all the data during the computation,
we propose an approximate solution which only use some of the data. A bound of
relative errors introduced by the approximation is also developed. Finally, our
experimental evaluation demonstrates the efficiency of the proposed methods.
