A video search system provides a user with a list of videos that are similar to a reference video selected by the user. A client device operated by the user may receive the reference video and transmit it to the video search system. The video search system generates a reference textual representation of actions depicted in the reference video based on an analysis of the contents of the reference video. The video search system further compares the reference textual representation with a plurality of textual representations generated based on videos stored in a library of videos. Based at least partly on the comparison, the video search system generates video search results that are provided to the client device. In certain functions, the client device may generate the reference textual representation and transmit the reference textual representation to the video search system for comparison.