Musipedia

The melodic contour search uses an editing distance. Because of this, the search engine finds not only entries with exactly the contour that is entered as a query, but also the most similar ones among the contours that are not identical. The similarity is measured by determining the editing steps (inserting, deleting, or replacing a character) that are needed for converting the query contour into that of the search result. Since only the melodic contour is relevant, one can find melodies even if the key, rhythm, or the exact intervals are unknown.

The pitch and onset time-based search takes more properties of the melody into account. This search method, which is used by default, is still transposition-invariant and tempo-invariant, but it takes rhythm and intervals into account. The melody can be entered in various ways, for example by clicking on a virtual keyboard on the screen. The search engine then segments the query, converts each segment into a set of points in the two-dimensional space of onset time and pitch, and, by using the Earth Mover's Distance, compares each point set to pre-computed point sets representing segments of melodies from the database. As with the contour search, little alterations of the query will lead to correspondingly small changes in the results, which makes the search method somewhat error-tolerant.

The "query by tapping" method that only takes the rhythm into account uses the same algorithm as the pitch and onset time method, but assumes all pitches to be the same. As a result, the algorithm can be used for tapped queries that only contain onset times.

This search method is also very easy to do for those with limited accessibility options or using very small input devices.

Both search algorithms are made faster with indices that are based on vantage objects. Instead of calculating the distance between the query and every single database entry, Musipedia just calculates the distance between the query and each of a few vantage objects. For every vantage object, the distance to each database entry is known. Since the triangle inequality holds for both the editing distance for contours and the variant of the Earth Mover's Distance used by Musipedia, the search algorithm needs, in a second step, to take a closer look at only those database entries whose distances to the vantage objects are similar to the distances between the query and the vantage objects.