Skip to main content
Meta Stack Exchange

Return to Revisions

1 of 4
Bob
Bob
  • 817
  • 4
  • 15

Finding Exact-Match Answers

There are two types of plagiarism that can be found on Stack Overflow: exact-match instances, and non-exact-match instances. Of the two types, exact-match plagiarism is relatively trivial to detect: it merely requires a simple equality comparison between two "strings" (or whatever text-field datatype is being used to store answers in a particular database).

When detecting exact-match instances of plagiarism on Stack Overflow, the "hard part" comes in efficiently surfacing these cases from the database, i.e. the Stack Exchange Data Explorer (SEDE).

A Naive Approach

Here is a naive query that can be run against SEDE to find exact-match answers,

SELECT  u.Id AS [User Link],
        p1.Score,
        FORMAT(p1.CreationDate, 'yyyy-MM-dd') AS [Date],
        p1.Id AS [Post Link],
        p2.Id AS [Post Link]
FROM Posts p1 INNER JOIN Posts p2 ON p1.Body = p2.Body -- SUBSTRING(p1.Body, 0, 100) = SUBSTRING(p2.Body, 0, 100)
              INNER JOIN Users u ON p1.OwnerUserId = u.Id
WHERE p1.PostTypeId = 2 AND p2.PostTypeId = 2 -- 2 is the post type for answers
  AND DATEDIFF(month, u.CreationDate, GETDATE()) <= ##MaxMonthAge:int?12##
  AND p1.Id <> p2.Id
  AND p1.OwnerUserId <> p2.OwnerUserId
  AND p1.CreationDate BETWEEN ##StartDate:string?2013-01-01## AND ##EndDate:string?2015-12-31##
  AND p2.CreationDate < p1.CreationDate
  AND p2.CreationDate <= ##EndDate:string?2015-12-31##
  AND ##MinLength:int?100## <= LEN(p1.Body)
ORDER BY  u.Id,
          p1.Score DESC,
          [Date]

The key part of this query is the self-join of the Posts table on itself, using the equality of two post bodies as the condition for the join,

FROM Posts p1 INNER JOIN Posts p2 ON p1.Body = p2.Body

Note that in this query, user u represents a potential plagiariser, p1 represents a potentially plagiarised answer, and p2 represents the (possible) original source. Thus, the following conditionals filter the set of self-joined post bodies down to those where

  1. The post bodies are an exact match.
  2. The posts are answers.
  3. The answer IDs aren't the same (don't include the join of an answer with itself).
  4. The answer owners are different.
  5. p1 was created after p2, i.e. p2.CreationDate < p1.CreationDate.

Expressed in SQL, these are

WHERE p1.PostTypeId = 2 AND p2.PostTypeId = 2 -- 2 is the post type for answers
  -- ...
  AND p1.Id <> p2.Id
  AND p1.OwnerUserId <> p2.OwnerUserId
  -- ...
  AND p2.CreationDate < p1.CreationDate

When running such a query against a data set as large as SEDE, I found it helpful to also add the following conditionals to limit the result set, making the query run faster, but at the cost of potentially missing some instances of plagiarism,

  1. For a user u, only return results if that user's account is less than X months old. The idea behind this is that "new" user accounts are more likely to engage in plagiarism than accounts belonging to more established users...though in some cases, I have found high-rep users with accounts that are years old, who have engaged in a disappointingly large number of instances of plagiarism.
  2. Limit potential positive p1 to answers made within a certain time frame.
  3. Limit potential source p2 to answers created before a certain date.
  4. Limit potential matches to the ones where the post bodies are at least X characters long, with the idea being that short answers are more likely to be false positives.

Expressed in SQL, these conditionals are

AND DATEDIFF(month, u.CreationDate, GETDATE()) <= ##MaxMonthAge:int?12##
-- ...
AND p1.CreationDate BETWEEN ##StartDate:string?2013-01-01## AND ##EndDate:string?2015-12-31##
-- ...
AND p2.CreationDate <= ##EndDate:string?2015-12-31##
AND ##MinLength:int?100## <= LEN(p1.Body)

Try It Out

You can test out the above query on SEDE. I have given the query some default parameters that will currently return results (about 140 of them, to be exact), though if moderators start removing true positives, then the result set may eventually be reduced to zero.

Feel free to play around with the parameters, or even make modifications to the query itself.

Finding Exact-Match Answers by Location

As another technique to make querying a large data set such as SEDE more practical, it can be helpful to limit the number of answers that are compared by narrowing them down to users who are more likely to plagiarise than your average Stack Overflow user. One such criteria that can be effectively employed is a user's location:

SELECT p.Id, p.OwnerUserId, p.Body, p.CreationDate, p.Score
INTO #Answers
FROM Users u INNER JOIN Posts p ON u.Id = p.OwnerUserId
WHERE p.PostTypeId = 2 -- answers
  AND u.Location LIKE '%FILL IN LOCATION HERE%'
 
SELECT -- TOP ##Limit:int?100##
  ROW_NUMBER() OVER (ORDER BY a.OwnerUserId, a.Score DESC, a.CreationDate) AS Rank,
  a.OwnerUserId AS [User Link],
  FORMAT(u.Reputation, '#,###') AS Reputation,
  a.Id AS [Post Link],
  p.Id AS [Post Link],
  a.Score,
  DATEDIFF(day, a.CreationDate, GETDATE()) AS [Days]
FROM Posts p INNER JOIN #Answers a ON p.Body = a.Body
             INNER JOIN Users u ON a.OwnerUserId = u.Id
WHERE p.PostTypeId = 2 -- answers
  AND p.Id <> a.Id
  AND p.OwnerUserId <> a. OwnerUserId
  AND p.CreationDate < a.CreationDate
ORDER BY a.OwnerUserId, a.Score DESC, a.CreationDate

This query first creates a temporary table #Answers, populating it with answers (and meta-data) for users from a certain location (forgive me if "temporary table" is not the right term, my Transact-SQL is a little rusty). After creating the #Answers table, a second query (similar to the one presented in the previous section above) is used to find exact-match answers that are potentially an original source.

Note that the Location being used in this query is what users choose to make public in their profiles. If a user does not populate this field in their profile, then they will never be included in the query results.

Finding Serial Plagiarisers

Using the tools and techniques that I have presented above (or using your own methods), you may come across a legitimate instance of plagiarism. I have often found it to be the case that when a user plagiarises once, they are likely to plagiarise many times. It can be an extremely time consuming process, but if you are feeling so inclined, you might decide to check a known plagiariser's other answers to see if they too are additional cases of plagiarism.

In the case of exact-match answers, this process can be automated somewhat by using a query such as the following,

DECLARE @lastEditDate datetime2 = (
  SELECT MAX(LastEditDate)
  FROM Posts
  WHERE OwnerUserId = ##UserId:int## AND PostTypeId = 2 -- answers
)

SELECT ROW_NUMBER() OVER (ORDER BY p1.Score DESC, p1.CreationDate) AS Rank,
       p1.Id AS [Post Link], p1.Score, DATEDIFF(day, p1.CreationDate, GETDATE()) AS [Days], p2.Id AS [Post Link]
FROM Posts p1 INNER JOIN Posts p2 ON p1.Body = p2.Body 
WHERE p1.PostTypeId = 2 AND p2.PostTypeId = 2 -- answers
  AND p1.Id <> p2.Id
  AND p1.OwnerUserId <> p2.OwnerUserId
  AND p1.OwnerUserId = ##UserId:int##
  AND p2.CreationDate < @lastEditDate -- don't check answers that are newer than the user's last edit date
ORDER BY p1.Score DESC, p1.CreationDate

This query returns the entire set of potentially plagiarised exact-match answers for a given user. Much like the very first query I presented, it does a self-join of the Posts table, using equal text-bodies as the join-condition. A key addition, however, is the condition that narrows the search results down to answers belonging to a specific user (the known plagiariser),

AND p1.OwnerUserId = ##UserId:int##

As I mentioned, this query only returns exact-match cases of plagiarism. If a known plagiariser (also) uses non-exact-match answers, then you might just have to find original sources manually by using Google and SO's search engine, as I have mentioned.

Can You Improve These Queries (or Make Better Ones)?

There are many areas of improvement to the SQL queries that I have presented, such as making them run more efficiently, or returning a more complete and exhaustive set of results. One interesting enhancement might be to modify the queries to search the revision history for answers, in case an original source and a copy "drift" away in similarity as a plagiariser (or well meaning SO users) edit them over time.

Another simple enhancement would be to strip HTML and Markdown formatting from the post bodies before comparing them. Someone also once suggested using the Levenshtein distance between posts for comparison.

Also, I am not a source control expert, and I would be interested to know if any text comparison techniques used in version control can be applied to this problem. I've also heard about tools that people working in academia use to determine whether a student's paper has been plagiarised from some other source, and I would be interested in hearing about whether these tools can detect non-exact-matches, and about whether their algorithms can be applied to this problem.

Update: Calculating Levenshtein Distance and SEDE

I read up on how Levenshtein Distance is calculated, and it seems too computationally expensive to implement in a SEDE query. I might just make a GitHub project in .NET or Ruby someday that implements this instead (perhaps with an additional public-facing web interface that people can use).

In the meantime, here's a pseudo-code description of the algorithm, along with my notes, derived from the English description in Levenshtein Distance, in Three Flavors. Note that my pseudo-code style is a mish-mash of mathematical notations and syntaxes borrowed from a variety of languages, e.g. Haskell, Ruby, Java/C# etc.

/*
 * - Each iteration of the `for` loops computes the Levenshtein Distance for
 *   the sub-matrix that begins at cell M(1,1) and terminates at cell M(i,j).
 * - Addition and deletion are inverses of each other, and modify string length.
 * - Substitution can only occur along diagonals, i.e. iff index i == j, and
 *   does *not* modify string length.
 * - Algorithm uses 1-based matrix/array indexing, not 0-based.
 */
EditDistance(string a, string b) -> int
{
    int n = a.length
    int m = b.length
    return m if n == 0 // `a` is empty string
    return n if m == 0 // `b` is empty string
    
    M = new Matrix(n,m)
    int cost = 0
    for int i from 1 to n {
        for int j from 1 to m {
            cost = (0 if a(i) == b(j)) else 1
            M(i,j) = min(M(i - 1, j) + 1, M(i, j - 1) + 1, M(i - 1, j - 1) + cost)
        }
    }
    
    return M(n,m)
}
Bob
  • 817
  • 4
  • 15