A device, system and method for altering a memory using rule signatures and connected components for deduplication is provided. A server accesses a memory storing guest records identified by respective identifiers. The server generates, using one or more matching rules and the guest rules, a plurality of rule signatures associated with respective identifiers of a guest record from which a rule signature was generated. A rule signature comprises a string of values from a guest record substituted for corresponding information defined by a matching rule. A graph is generated comprising connected components of the rule signatures and respective identifiers, a connected component corresponding to a distinct guest of the guest records. An assigned identifier identifies a connected component. The server alters the memory to add the assigned identifiers to the guest records identified by respective identifiers associated with respective rule signatures of the connected components.