Scribd
Upload
4 views20 pages

L28 DisjointSetDataStructure

The document discusses disjoint set data structures, focusing on user ID deduplication in large organizations. It outlines the problem of merging accounts when duplications are detected and presents various data structure operations needed for this purpose, including Union and Find. Additionally, it explores optimization techniques such as Union by size and path compression to improve time complexity for operations.

Uploaded by

sandipssahoo2005
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views20 pages

L28 DisjointSetDataStructure

The document discusses disjoint set data structures, focusing on user ID deduplication in large organizations. It outlines the problem of merging accounts when duplications are detected and presents various data structure operations needed for this purpose, including Union and Find. Additionally, it explores optimization techniques such as Union by size and path compression to improve time complexity for operations.

Uploaded by

sandipssahoo2005
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

L28: Disjoint set data

structures
ID2230: Data Structures and Applications
Instructor: Rakesh Venkat
13th Nov 2025 (Thu)
Reference for today’s lecture
• Algorithm Design by Kleinberg and Tardos, Sec 4.6
User ID Deduplication
• Large organizations (e.g. databases/banks) discover that
different IDs belong to the same person, via user
attributes, e.g.
• Phone number
• Email Address

• Goal: Whenever a duplication is detected, “merge” the


accounts
• Assume that duplicate detection is done separately

• Once merged, accounts don’t need to be unmerged


Problem Abstraction
• Start off with a universe 𝑈 of (singleton) elements (say 𝑈 = 𝑛)

• A stream of duplications are given : 𝑢1 , 𝑣1 , 𝑢2 , 𝑣2 , …

• When a duplication is given between 𝑢, 𝑣 ∈ 𝑆, put 𝑢, 𝑣 into the


same “set”

• Note that duplications may be found between elements that


are already known to be duplicates

• Can think of this as a graph evolving with the addition of edges


Data Structure Operations needed
• MakeUnionFind(S): Initialization

• Find(u):

• What Should Find return?

• Union(A,B):
Solution 1: Array-based implementation
• Suppose 𝑆 = {1,2, … 𝑛}

• Array C

• Find procedure
Array-implementation
• Union Procedure:

• Union Time Complexity:


Optimization: Union by Size
• Only change the component entries of the smaller set
Time Complexity
• Any sequence of 𝑘 Union operations takes 𝑂(𝑘 log 𝑘)
time
Solution 2: Using Pointers
• Each node has a pointer to the “name” of the set

• Name of a set = ID number of some element in it

• Name of the set containing an element may change over


course of the operations

• Change pointer from an old name to a new name


Example
• : Union(w, u), Union(s, u), Union(t, v), Union(z, v), Union(i,
x), Union(y, j), Union(x, j), and Union(u, v)
Union operation
Find operation

• Time Complexity?
Optimization: Union by size
Time complexity
• Theorem: Union takes 𝑂(1). Find(v) takes time ______
Further improvements
• What is a bad case for the running time?
Path compression
Time complexity
• Can be shown that the time complexity is 𝑂(𝑛 𝛼 𝑛 ) for a
sequence of 𝑛 Find operations

• 𝛼 𝑛 is the inverse Ackermann function

• Ackermann Function:

• 𝐴 4,2 = 265536 − 3
• Inverse of 𝑓 𝑛 ≔ 𝐴 𝑛, 𝑛 is very slowly growing , ≤ 5 for
any practical input size

You might also like