An online system stores media files (i.e., stored media files) and receives a user request to upload a video file (i.e., a requested media file). The online system determines whether the requested media file matches one of the stored media files based on hash values. If there is a mismatch in hash value, the online system may determine the match based on fingerprints. If it is determined that the requested media file does not match any stored media file, the online system stores the requested media file. Even if there is a match, the online system compares a quality of the requested media file with the matched media file and replaces the matched media file with the requested media file having a higher quality metric.