This week we lay out our plan for figuring out the search paradox, which is that tunes have a widely variety of overlap with their two-note patterns (tuples), from zero to thousands, sometimes contrary to how common the notes look to the eye.
We have to control for genre. The ratio of common to rare tuples varies across genres, and to control for that we need to choose a single genre for our test. Of the genres in the database, the obvious choice is folk music. About a third of the tunes in the database are folk tunes with anonymous authorship. Furthermore, folk music stretches across time, geographic boundaries, and cultures. It has been continuously produced for at least 500 years. That is not true of any other genre, most of which can be counted in decades, not centuries. Folk tunes allow us to experiment across most of the database.
The Experiment
Here’s the plan to solve the search engine paradox. For every tune in the database that is a folk tune with an anonymous composer:
- Find its longest contiguous non-rest tuple run.
- Determine the highest supported requested length of tuples among 4, 6, 8, …, 20.
- Select a search starting point only from passages supporting that maximum.
- Find 4 tuples at the selected starting point
- Deduplicate the tuples.
- Record each tuple’s reference-corpus frequency (how many times it appears in the database)
- Create a set for each search tuple such that the set includes only tunes with that search tuple.
- Find the set of tunes that intersects all those created sets. This set is made up of tunes that contain all the tuples in the search term, though not necessarily in the correct order.
- Record the results.
- Move up to 6 tuples and repeat. Stop after completing a 20-tuple run,
This algorithm essentially repeats the example from last week when we introduced the search engine paradox, but formalizes and standardizes it so we can do something statistically wth the results.
Notice that our algorithm does not result in a completed search. We stop just short of checking to see if the tunes with all the search terms have the same search order as the search term.
Let’s Try a Run
We start with a 10-tuple run. The number “10” is arbitrary, but it’s just for illustration and we will supplement it next week with runs of other tuple lengths. This experiment took place with about 83,500 tunes in the database, of which about 24,250 tunes qualified as folk tunes where the composer was anonymous.
- 23,831 anonymously written folk tunes contained a qualifying contiguous, rest-free 10-tuple passage.
- 2,396 supported tunes produced zero intersections.
- That is a zero-intersection rate of 10.1 percent with a reported 95 percent confidence interval of 9.7 to 10.4 percent.
- The remaining 21,435 tunes, or 89.9 percent, matched at least one other tune.
- The median intersection was 75 other tunes.
- The mean was much higher at 1,559, showing an extremely right-skewed distribution.
Each tune contributed one selected 10-position passage. After duplicates in that passage were removed, the script counted how many other tunes contained all remaining distinct tuples. Those 23,831 intersection counts were then sorted from smallest to largest. The middle result was 75. The median of 75 means that among the 23,831 supported 10-tuple searches, half (11,916) produced an intersection count of 75 or fewer other tunes, and half (the other 11,916) produced an intersection count of 75 or more other tunes. Most searches produced far fewer than 1,559 matches, while a relatively small number produced very large intersection counts and pulled the mean upward.
This is a highly skewed distribution. The median of 75 tunes were not typical. The mean was 1,559 because a minority of searches returned extremely large intersections. But the median of 75 is the better description of what happened to the middle tune: its deduplicated 10-tuple set was shared by about 75 other database tunes.
What This Suggests About the Paradox
For this test, rarity of a tuple was the strongest measured predictor of intersection count in the 10-tuple run. To make this concrete, consider the following Irish folk song:
Circled in red is the selection of notes from this tune chosen at random. When you convert these to tuples, the result is
| [0, 1]; [0, 4]; [0, 1/2]; [0, 1]; [0, 1]; [2, 1]; [2, 1]; [-4, 1]; [-3, 7]; [10, 1/14] |
Deduplicating leaves the following:
| [0, 1]; [0, 4]; [0, 1/2]; [2, 1]; [-4, 1]; [-3, 7]; [10, 1/14] |
Now let’s look at the rarity of each in the database. The following are the number of tunes each of those tuples appears at least once (excluding the above tune):
| 53365; 8860; 29812; 67427; 37476; 272; 0 |
Notice the zero at the end. This tune happens to contain a unique tuple, one that doesn’t appear anywhere else in the database. Looking at the musical notation above, we see that it represents a 14-semitone jump from a whole note tied to a dotted half note up to an eighth note. The eighth note has a duration value of 2 and the whole note tied to the dotted half note has a duration value of 28 (16 + 12), so the duration ration is 2 / 28 or 1/14. Thus the final tuple in the deduplicated list above is [10,1/14], a tuple which doesn’t appear in any other tune.
It is obvious that if one of the search tuples is not in any other tune, you’re not going to find another tune with all the search tuples. This is a trivial case and does not occur that often. In fact, in this experiment there were only three such tunes, a tiny percentage of the tunes sampled.
Bottleneck Rarity
But a tune doesn’t have to have a unique tuple to produce a 10-tuple search term that results in zero intersections with all other tunes. Here’s an example:
Here are the tuples in the selected search term:
| [0, 1]; [2, 1]; [-16, 1]; [0, 1]; [7, 1]; [5, 3/2]; [2, 1/3]; [0, 3]; [0, 1/3]; [2, 2] |
And the deduplicated tuples (there was just one duplicate):
| [0, 1]; [2, 1]; [-16, 1]; [7, 1]; [5, 3/2]; [2, 1/3]; [0, 3]; [0, 1/3]; [2, 2] |
And here are the frequencies of each tuple in the database:
| 53365; 67427; 752; 15453; 5211; 21198; 11913; 17974; 38767 |
Notice that most of these tuples are common, appearing in tens of thousands of times. The most rare tuple is the one that appears just 752 times, corresponding to the A eighth note above the staff falling down to the F eighth note at the bottom of the staff. The duration is the same for each note and the pitch is -16 semitones, so the tuple in question is [-16, 1].
We call this explanation a “bottleneck rarity,” as in Willy Wilky. It has a tuple that occurs once in 111 tunes on average. Those 752 tunes represent just 0.9 percent of the corpus. The existence of that tuple alone in a search term eliminates 99.1 percent of the corpus as having a chance to contain all the tuples in the search term.
Combinatorial Rarity
So far we have relied on the bottleneck rarity, the rarity of a single tuple to explain the lower the chance of finding a zero intersection set of tunes with all the search terms. But there are plenty of examples like this:
The 10 tuples are (no duplicates):
| [-3, 2]; [7, 1]; [1, 3/2]; [-1, 1/3]; [0, 3]; [0, 1/3]; [1, 2]; [-3, 1]; [0, 3/2]; [2, 1/3] |
And here are their frequencies in the same order:
| 15214; 15453; 6259; 13907; 11913; 17974; 30059; 49144; 8857; 21198 |
No single tuple is extraordinarily rare. The rarest occurs in 6,259 other tunes, or 7.5 percent of the corpus. The next-rarest occurs in 8,857 tunes, or 10.6 percent. Nevertheless, not one other tune contains all ten tuples.
La Madam #19 [2] produced zero matches even though its rarest tuple appeared in 6,259 other tunes and none of its ten tuples was exceptionally rare. The result therefore cannot be attributed to one rare tuple. It was the particular combination of otherwise common tuples that was unique.
Conclusion
What we learned this week is that the “search-engine paradox” has at least two mechanisms:
- Bottleneck rarity: one very rare tuple leaves almost no candidates.
- Combinatorial rarity: no tuple is exceptionally rare, but their intersection is empty.
For Willy Wilky [2], bottleneck rarity contributed strongly. For La Madam #19 [2], combinatorial rarity is the clearer explanation.
But this conclusion must remain tentative. We don’t know if there’s something about 10-tuple length search terms that is producing this result. Second, we need a way to estimate how much bottleneck rarities vs combinatorial rarities answer the paradox. That’s next week.