Music indexing and search
I want a few ways to navigate the music:
- genres -> artists -> albums -> tracks
- artists -> albums -> tracks
- albums -> tracks
- search
As I'm targeting large music collections, I will preindex the collection, store is as binaries and load it in RAM. For searching, I'll use a TRIE.
Music indexing
I developped a little node-js tool that scrolls through the folders, reads the metadata and genrates a binary file for each relationship between the entities:
- genre_to_artists.bin
- genre_to_albums.bin
- genre_to_tracks.bin
- artist_to_albums.bin
- artist_to_tracks.bin
- album_to_tracks.bin
Then I have a few more files that are holding the actual data:
- genre_index.bin
- artist_index.bin
- album_index.bin
- track_index.bin
- path_index.bin
Relationship files structure
For the relationships I have a header with 2 uint32:
- the number of sources
- the number of targets
Then I write all the sourceIds as uint32, the first index in the array and the number of targets and then the targetIds.
To consult the index, just binary search for the sourceId, then read the start target index and number of targets and read the targetIds.
function readIds(query: number, array: Uint32Array): number[] {
const hearderLength = 2;
const start = hearderLength; // start after the header
const end = hearderLength + array[0]; // number of sources
const index = binarySearch(query, array, start, end);
if (index === -1) {
return [];
}
const targetStartIndex = array[hearderLength + index * 2];
const targetCount = array[hearderLength + index * 2 + 1];
const targetIds = [];
for (let i = 0; i < targetCount; i++) {
targetIds.push(array[targetStartIndex + i]);
}
return targetIds;
}Data files structure
Datafiles holds the names for each entity, with a header of 2 uint32s:
- the number of entities
- the size of the data in bytes
Then I write the id of each entity, the size of the name in bytes, and then the name itself.
function readNames(ids: number[], array: Uint8Array): string[] {
const headerLength = 8; // 2 uint32s
const names: string[] = [];
const start = headerLength; // start after the header
const end = headerLength + array[0]; // number of entities
for (const id of ids) {
const index = binarySearch(id, array, start, end);
if (index === -1) {
continue;
}
const nameStart = array[headerLength + index * 2];
const nameLength = array[headerLength + index * 2 + 1];
const name = new TextDecoder().decode(
array.slice(nameStart, nameStart + nameLength)
);
names.push(name);
}
return names;
}Music search
For searching I build a TRIE to have both fast prefix search and low memory usage. It is stored as a binary file (music_index.bin) with a header of 4 uint32s:
- the size of the string pool
- the number of nodes
- the number of results
- the number of string offsets
How much space does it take?
Let's say we have 40k songs, split into 200artists, 1000 albums, and 10 genres.
- Each song has a name of 50 characters on average, so the string pool is 2MB.
- Each artist has a name of 30 characters on average, so the string pool is 600KB.
- Each album has a name of 40 characters on average, so the string pool is 160KB.
- Each genre has a name of 20 characters on average, so the string pool is 40KB.
- The total string pool size is 2.8MB
- Each node has 2 children on average, so we have 80k nodes.
- Each node has 2 bytes for the character, 4 bytes for the string offset, and 4 bytes for the number of results, so each node takes 10 bytes.
- The total size of the nodes is 800KB