Effective Method to Manage and Search Through 100,000+ Objects Instantly? (C#)

Question

I'm writing a media player for enthusiasts with large collections (over 100,000 tracks) and one of my main goals is speed in search. I would like to allow the user to perform a Google-esque search of their entire music collection based on these factors:

• Song Path and File Name
• Items in ID3 Tag (Title, Artist, Album, etc.)
• Lyrics

What is the best way for me to store this data and search through it? Currently I am storing each track in an object and iterating over an array of these objects checking each of their variables for string matches based on given search text.

I've run into problems though where my search is not effective because it is always a phrase search and I'm not sure how to make it more fuzzy. Would an internal DB like SQLlite be faster than this? Any ideas on how I should structure this system?

I also need playlist persistence, so that when they close the app and open the app their same playlist loads immediately. How should I store the playlist information so it can load quickly when the application starts? Currently I am JSON encoding the entire playlist, storing it in a text file, and reading it into the ListView at runtime, but it is getting sluggish over 20,000 tracks.

Thanks!

Answer 1

SQLite should work fine with this. For extended searching functionality, you could take a look at Lucene.NET. About your large playlists, these should also be stored in the db, and loading them with paging (i.e. 50 tracks at a time).

Answer 2

Several suggestions:

1. Don't read the file into the ListView. Use the MVVM pattern and read the file into a collection, letting data binding fill the ListView.

2. Enable virtualization on the ListView.

3. Do the data load in a separate thread. That way the UI will be responsive while items are loading.

4. Linear in-RAM searching is generally ok for only 100,000 items. Build indexes only where necessary.

5. In your view model, store the entire list of tracks in one field and the currently filtered list of tracks in a different field. When the filter changes, compute a new filtered list and set the property to the new value rather than making changes to the existing filtered collection. Don't use CollectionView to do your filtering.

6. Maybe consider using a more efficient data format than json. A variation of CSV replacing the comma with a special character tends to be very fast and backward-compatible.

7. For searches, consider breaking the titles into words and searching for any/all words instead of exact phrases.

Answer 3

Look into Lucene.NET for a really good full-text search engine that you can use easily in your application. It is Open Source, easy to use and there is a lot of community support.

For your playlist persistence, since you are using JSON already, look into MongoDB. This is a pretty cool NoSQL database that sounds like it would be a great fit for your needs and there are .NET drivers to make it easy to add into .NET applications.

Cheers.

Answer 4

I have build a multi-zone music player that handles large music collections. The approach I took was to create a Tag table and an association Song-Tag. I have various Tag types, TagArtist, TagAlbum, TagGenre, TagWord, ... that all derive from Tag.

Using Entity Framework 4 I can query for any word, genre, title, artist efficiently and get all the songs that contain that word. I can query either by 'any word anywhere in artist, title, genre, ...' or by a specific tag type, e.g. Artist starts with 'X'.

To handle random playlists I also store a random number with each song in the database. An ordered random result can be obtained by XORing today's random number with the number in the database (an operation you can do in the database).

Using LINQ to EF you never need to hold the whole playlist in memory, you use Skip() and Take() to get to the right 'page', or individual song.

My system also responds to natural language queries like 'play songs added last week' or 'play artist:Phil', or just 'play X'. See demo on blog.

I believe it's also the first music player that doesn't play seasonal music in the wrong season!