Sites to share user-created video clips such as YouTube and Yahoo Video have become greatly popular in recent years. One of the challenges of such sites is, however, to prevent video clips that violate copyrights by illegally copying and editing scenes from other videos. Due to the sheer number of clips uploaded every day, automatic methods to detect (illegally) copied video clips in a large collection are desirable. Toward this problem, in this paper, we present a novel framework, termed as Video Linkage, that is based on the record linkage techniques. Our proposal is based on the observations that: (1) a video clip can be represented as a "group" of key frames, (2) two video clips are deemed to be similar if two groups of key frames are similar as a whole - i.e., the similarity of two video clips can be measured by means of graph-based similarity measures such as maximal cardinality bipartite matching, and (3) if a video clip va is copied to Vb, then v a and vb must be somehow similar, but not all similar video clips are illegally copied ones - i.e., similar videos can be used as a filter for fast detection of copied videos. The validity of our observations and Video Linkage technique is thoroughly evaluated using both real and synthetic data sets - i.e., on average, our proposals achieved 0.94 as precision and 0.93 as recall across 10 genres and 6 editing patterns.