Transmitting or storing subsegments is disclosed. A data stream or a data block is received and broken into a plurality of segments. For at least one segment, the segment is broken into a plurality of subsegments. A previously stored or transmitted segment similar to the at least one segment is identified. A fingerprint is computed for at least one subsegment. And, using the fingerprint for the at least one subsegment, determining whether the at least one subsegment is identical to a subsegment of the previously stored or transmitted segment without directly comparing the content of the at least one subsegment with the content of the subsegment of the previously stored or transmitted segment.