Use clean master to delete junk files. I've noticed it picks up folders for ads that may have come from sites you've visited and deletes them. Then delete the ad videos in your gallery. I never had your issue though so this is just a shot in the dark. I clean cache/junk filed weekly and after I uninstall apps.
"You silly twisted boy, you" - Hercules Grytpype-Thynne