A system and method provides video recommendations for a target video in a video sharing environment. The system selects one or more videos that are on one or more video playlists together with the target video. The video co-occurrence data of the target video associates the target video and another video on one or more same video playlists and frequency of the target video and another video on the video playlists is computed. Based on the video co-occurrence data of the target video, one or more co-occurrence videos are selected and ranked based on the video co-occurrence data of the target video. The system selects one or more videos from the co-occurrence videos as video recommendations for the target video.