Duplicate Elimination: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== Problem Description== 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. == Bounds Chart == 1050px ==...")
 
No edit summary
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:Duplicate Elimination (Duplicate Elimination)}}
== Description ==  
 
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.
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.
Databases, therefore, can have duplicate entries. The problem deals with identifying and removing duplicates from a database.


== Bounds Chart ==
== Parameters ==  
[[File:Duplicate_EliminationBoundsChart.png|1050px]]
 
No parameters found.
 
== Table of Algorithms ==


== Step Chart ==
{| class="wikitable sortable"  style="text-align:center;" width="100%"
[[File:Duplicate_EliminationStepChart.png|1050px]]
 
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference


== Improvement Table ==
{| class="wikitable" style="text-align:center;" width="100%"
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
|-
| rowspan="1" | Exp/Factorial
|
|
|-
|-
| rowspan="1" | Polynomial > 3
 
|
| [[Sorting based (Merge Sort) (Duplicate Elimination Duplicate Elimination)|Sorting based (Merge Sort)]] || 1964 || $O(nlogn)$ || $O(n)$ || Exact || Deterministic ||
|
|-
|-
| rowspan="1" | Cubic
| [[Sorting based (Merge Sort) + real-time elimination (Duplicate Elimination Duplicate Elimination)|Sorting based (Merge Sort) + real-time elimination]] || 1964 || $O(nlogn)$ ||  || Exact || Deterministic || 
|
|
|-
|-
| rowspan="1" | Quadratic
| [[BST Algorithm (Duplicate Elimination Duplicate Elimination)|BST Algorithm]] || 1999 || $O(nlogn)$ || $O(\log n)$ || Exact || Deterministic ||
| [ Priority Queue Algorithm (1976)]
|
|-
|-
| rowspan="1" | nlogn
| [[Priority Queue Algorithm (Duplicate Elimination Duplicate Elimination)|Priority Queue Algorithm]] || 1976 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || 
| [Sorting based [Merge Sort] (1964)]
|-
| [[Sorted Neighborhood Algorithm (SNA) (Duplicate Elimination Duplicate Elimination)|Sorted Neighborhood Algorithm (SNA)]] || 1998 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/article/10.1023/A:1009761603038 Time]
|-
| [[Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) (Duplicate Elimination Duplicate Elimination)|Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA)]] || 2002 || $O(nlogn)$ ||  || Exact || Deterministic || 
|-
| [[Adaptive Duplicate Detection Algorithm (ADD) (Duplicate Elimination Duplicate Elimination)|Adaptive Duplicate Detection Algorithm (ADD)]] || 2003 || $O(n^{3})$ || $O({1})$ || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/956750.956759 Time]
|-
|}
 
== Time Complexity graph ==
 
[[File:Duplicate Elimination - Time.png|1000px]]


[Sorting based [Merge Sort] + real-time elimination (1964)]
== Space Complexity graph ==


[BST Algorithm (1999)]
[[File:Duplicate Elimination - Space.png|1000px]]


[sorted neighborhood algorithm (1993)]
== Pareto Decades graph ==
[Duplicate elimination sorted neighborhood algorithm (DE-SNA) (2002)]


[https://dl.acm.org/doi/10.1145/956750.956759 adaptive duplicate detection algorithm (ADD) (2003)]
[[File:Duplicate Elimination - Pareto Frontier.png|1000px]]
|
|-
| rowspan="1" | Linear
|
|
|-
| rowspan="1" | logn
|
|
|-|}

Revision as of 10:24, 15 February 2023

Description

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.

Parameters

No parameters found.

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Sorting based (Merge Sort) 1964 $O(nlogn)$ $O(n)$ Exact Deterministic
Sorting based (Merge Sort) + real-time elimination 1964 $O(nlogn)$ Exact Deterministic
BST Algorithm 1999 $O(nlogn)$ $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(nlogn)$ Exact Deterministic
Adaptive Duplicate Detection Algorithm (ADD) 2003 $O(n^{3})$ $O({1})$ Exact Deterministic Time

Time Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Pareto Decades graph

Error creating thumbnail: Unable to save thumbnail to destination
Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Duplicate_Elimination&oldid=44099"