Duplicate Elimination (Duplicate Elimination)

From Algorithm Wiki
Jump to navigation Jump to search


SQL does not eliminate duplicates implicitly. It allows to enter duplicate values on columns other than candidate key or if did not specified any keys. If the user wants to eliminate duplicate records, he has to use DISTINCT keyword in the query.

Databases, therefore, can have duplicate entries. The problem deals with identifying and removing duplicates from a database.


$n$: number of records

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Sorting based (Merge Sort) 1964 $O(n \log n)$ $O(n)$ Exact Deterministic
Sorting based (Merge Sort) + real-time elimination 1964 $O(n \log n)$ Exact Deterministic
BST Algorithm 1999 $O(n \log n)$ $O(\log n)$ Exact Deterministic
Priority Queue Algorithm 1976 $O(n^{2})$ $O(n)$ Exact Deterministic
Sorted Neighborhood Algorithm (SNA) 1998 $O(n^{2})$ $O(n)$ Exact Deterministic Time
Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) 2002 $O(n \log n)$ Exact Deterministic
Adaptive Duplicate Detection Algorithm (ADD) 2003 $O(n^{3})$ $O({1})$ Exact Deterministic Time

Time Complexity Graph

Duplicate Elimination - Time.png