Client-based generation of music playlists via clustering of music similarity vectors

• US 7,571,183 B2
• Filed: 01/27/2005
• Issued: 08/04/2009
• Est. Priority Date: 11/19/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John, Renshaw, Erin
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Arjomandi; Noosha
• Application Number:
  US11/045,926
• Publication Number:
  US 20060112098A1
• Time in Patent Office: 1,650 Days
• Field of Search: 707/102, 707/3, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/635 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/639 using playlists
• CPC Class Codes: G06F 16/68 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G10H 2240/091 Info, i.e. juxtaposition of unrelated auxiliary information or commercial messages with or between music files metadata G10H2240/075
• CPC Class Codes: G10H 2240/135 Library retrieval index, i.e. using an indexing scheme to efficiently retrieve a music piece
• CPC Class Codes: G10H 2240/155 Library update, i.e. making or modifying a musical database using musical parameters as indices data structures involving musical parameters G10H2240/005
• CPC Class Codes: G10H 2250/005 Algorithms for electrophonic musical instruments or musical processing, e.g. for automatic composition or resource allocation mathematical functions therefor G10H2250/131; details of musical waveform synthesis G10H2250/541
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A “Music Mapper” automatically constructs a set coordinate vectors for use in inferring similarity between various pieces of music. In particular, given a music similarity graph expressed as links between various artists, albums, songs, etc., the Music Mapper applies a recursive embedding process to embed each of the graphs music entries into a multi-dimensional space. This recursive embedding process also embeds new music items added to the music similarity graph without reembedding existing entries so long a convergent embedding solution is achieved. Given this embedding, coordinate vectors are then computed for each of the embedded musical items. The similarity between any two musical items is then determined as either a function of the distance between the two corresponding vectors. In various embodiments, this similarity is then used in constructing music playlists given one or more random or user selected seed songs or in a statistical music clustering process.

Claims

1. A system for generating clusters of similar media objects, comprising using a computing device for:

identifying a set of locally available media objects;

querying a remote server computer to retrieve a set of coordinate vectors corresponding to each of the locally available media objects;

determining distances between the retrieved coordinate vectors;

forming at least one cluster of at least one coordinate vector relative to a first adjustable minimum distance threshold such that any group of one or more of the coordinate vectors whose mutual distances are less than the first adjustable minimum distance threshold are assigned to a common cluster, wherein forming at least one cluster of at least one coordinate vector comprises recursively identifying clusters of similar media objects;

initially placing each coordinate vector into a unique cluster;

identifying a coordinate vector having a largest number of neighboring coordinate vectors within the first adjustable minimum distance threshold, and forming a new cluster from the identified coordinate vector and the identified neighboring coordinate vectors;

removing any coordinate vectors already added to a new cluster from further cluster considerations; and

repeating the formation of new clusters and removing of coordinate vectors from further cluster consideration until all coordinate vectors have been assigned to a new cluster of at least one coordinate vector;

selecting at least one media object; and

generating a media object playlist to automatically populate the playlist with media objects corresponding to coordinate vectors in any cluster including the coordinate vectors of the selected media objects.

2. The system of claim 1 wherein the coordinate vectors are computed from a sparse graph of media object similarities.

3. The system of claim 1 further comprising weighting distances between any two or more of the coordinate vectors.

4. The system of claim 1 further comprising forming at least one super-cluster of existing clusters for existing clusters having less than a minimum number of coordinate vectors and being less than a second adjustable minimum distance threshold apart.

5. A physical computer-readable medium having computer executable instructions stored thereon for generating media object playlists from a set of coordinate vectors derived from a sparse graph of music object similarities, comprising:

identifying a set of media objects available to a local client computer;

querying a remote server computer to retrieve a set of coordinate vectors corresponding to each of the music objects available to the local client computer;

recursively forming clusters of at least one of the retrieved coordinate vectors as a function of computed distances between the retrieved coordinate vectors in multidimensional space; and

wherein recursively forming clusters comprises;

initially placing each retrieved coordinate vector into a unique cluster,

identifying a coordinate vector having a largest number of neighboring coordinate vectors within a first minimum distance threshold, and forming a new cluster from the identified coordinate vector and the identified neighboring coordinate vectors,

removing any coordinate vectors already added to a new cluster from further cluster considerations, and

repeating the formation of new clusters and removing of coordinate vectors from further cluster consideration until all coordinate vectors have been assigned to a new cluster of at least one coordinate vector.

6. The computer-readable medium of claim 5 wherein the first minimum distance threshold is adjustable.

7. The computer-readable medium of claim 5 further comprising weighting distances between any two or more of the coordinate vectors.

8. The computer-readable medium of claim 5 further comprising a user interface for selecting the media objects for generating at least one media object playlist from the media objects corresponding to coordinate vectors assigned to the clusters.

9. The computer-readable medium of claim 5 further comprising a user interface for interacting with the media objects and the clusters.

10. The computer-readable medium of claim 8 further comprising automatic playback of media objects comprising the at least one media object playlist.

11. A computer-implemented process for constructing music playlists through clustering of music similarity vectors, comprising steps for:

constructing a set of multidimensional music similarity vectors from a sparse graph of music similarities representing interrelationships between a plurality of music objects;

recursively forming clusters of at least one of the music similarity vectors as a function of computed distances between the music similarity vectors in multidimensional space;

wherein recursively forming the clusters further comprises steps for;

initially placing each music similarity vector into a unique cluster,

identifying a music similarity vector having a largest number of neighboring music similarity vectors within a minimum distance threshold, and forming a new cluster from the identified music similarity vector and the identified neighboring music similarity vectors,

removing any music similarity vectors already added to a new cluster from further cluster considerations, and

repeating the formation of new clusters and removing of music similarity vectors from further cluster consideration until all music similarity vectors have been assigned to a new cluster of at least one music similarity vector; and

generating at least one music playlist by automatically populating the playlist with at least one music object corresponding to music similarity vectors from clusters corresponding to the music similarity vectors of at least one music object selected via a user interface.

12. The computer-implemented process of claim 11 wherein the step for constructing the set of multidimensional music similarity vectors is performed by a remote server computer.

13. The computer-implemented process of claim 12 wherein the steps for recursively forming clusters and generating at least one music playlist are performed by a local client computer following downloading a set of music similarity vectors corresponding to locally available music objects from the remote server computer.

14. The computer-implemented process of claim 11 further comprising a step for weighting the distances between the music similarity vectors in multidimensional space.

15. The computer-implemented process of claim 11 further comprising a step for adjusting the minimum distance threshold via the user interface.