DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones

By Lingxiao Jiang, Ghassan Misherghi, Zhendong Su, Stéphane Glondu. 2007

1,147 citations recorded by the source corpus.

Detecting code clones has many software engineering applications. Existing approaches either do not scale to large code bases or are not robust against minor code modifications. In this paper, we present an efficient algorithm for identifying similar subtrees and apply it to tree representations of source code. Our algorithm is based on a novel characterization of subtrees with numerical vectors in the Euclidean space Rnmiddot and an efficient algorithm to cluster these vectors w.r.t. the Euclidean distance metric. Subtrees with vectors in one cluster are considered similar. We have implemented our tree similarity algorithm as a clone detection tool called DECKARD and evaluated it on large code bases written in C and Java including the Linux kernel and JDK. Our experiments show that DECKARD is both scalable and accurate. It is also language independent, applicable to any language with a formally specified grammar.

Subfields: Information Systems, Software, Program Analysis & Verification, Signal Processing, Software Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

  1. Miltiadis Allamanis
  2. Charles Sutton
  3. Premkumar T. Devanbu
  4. Tien Nhut Nguyen
  5. Earl T. Barr
  6. Michael Pradel
  7. Baishakhi Ray
  8. Anh Tuan Nguyen

In Software

  1. Miltiadis Allamanis
  2. Charles Sutton
  3. Premkumar T. Devanbu
  4. Tien Nhut Nguyen
  5. Earl T. Barr
  6. Michael Pradel
  7. Anh Tuan Nguyen
  8. Swarat Chaudhuri

In Program Analysis & Verification

  1. Miltiadis Allamanis
  2. Charles Sutton
  3. Premkumar T. Devanbu
  4. Tien Nhut Nguyen
  5. Earl T. Barr
  6. Anh Tuan Nguyen
  7. Dawn Song
  8. Baishakhi Ray

In Signal Processing

  1. Miltiadis Allamanis
  2. Charles Sutton
  3. Premkumar T. Devanbu
  4. Tien Nhut Nguyen
  5. Baishakhi Ray
  6. Earl T. Barr
  7. Anh Tuan Nguyen
  8. Swarat Chaudhuri

In Software Engineering

  1. Dawn Song
  2. Chanchal Kumar Roy
  3. Miltiadis Allamanis
  4. Charles Sutton
  5. James R. Cordy
  6. Hongyu Zhang
  7. Artur Andrzejak
  8. Gang Zhao

Citations in the corpus