Static TOC indexing system and method

• US 8,472,289 B2
• Filed: 12/06/2010
• Issued: 06/25/2013
• Est. Priority Date: 12/01/2010
• Status: Active Grant

• Current Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Original Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Scherf, Steven D., Stroud, Gary
• Primary Examiner(s): Dinh, Tan X
• Application Number:
  US12/961,470
• Publication Number:
  US 20120140605A1
• Time in Patent Office: 932 Days
• Field of Search: 369/275.3, 369/275.2, 369/275.1, 369/275.4, 369/275.5, 369/30.03, 369/30.04, 369/30.07, 369/30.08, 369/30.09, 428/64.1, 428/64.4, 430/320, 430/321
• US Class Current: 369/30.04
• CPC Class Codes: G11B 2220/2545 CDs
• CPC Class Codes: G11B 27/329 on a disc [VTOC]

Abstract

A method and system is provided for doing compact disc TOC look-ups cheaply and efficiently by using a special indexing mechanism particularized to TOC look-ups. The indexing scheme allows a successful search of TOCs using as few as 2 disk seeks in contrast to the usual hundreds of disk seeks required by a general purpose indexing scheme. This performance improvement is achieved by using a static database of TOCs in a read-only implementation so that the data organization and code for lookups can be optimized without regard for any updates to this data at a later time. The index data structure is arranged in a fashion that allows for seek-less, linear scans of index information once the proper scan location in the index has been identified.

Claims

1. A computer-implemented method of finding a match for a reference TOC comprising:

using one or more processors to perform operations of;

organizing a TOC database into a look-up table and buckets,

wherein the lookup tables are divided into the number of tracks in a set and the total playtime of the set,

and wherein each bucket comprises a linear table of TOCs organized by number of tracks in the set, and further where at least two of the buckets are arranged contiguously;

identifying the start of a bucket range containing the matching TOC using two seeks, wherein the first seek identifies a coordinate in the look-up table and retrieves a pointer from the coordinate, and the second seek uses the pointer to identify the start of the bucket range; and

scanning the bucket range to find a match for the reference TOC.

2. The method of claim 1, wherein all buckets are organized in a linear fashion in ascending or descending order.

3. The method of claim 2, wherein the bucket range consists of multiple buckets.

4. The method of claim 2, wherein all buckets reside in memory.

5. The method of claim 1, further comprising retrieving metadata, cover-art or any other data related to music files associated with the reference TOC after finding a match in the bucket range.

6. The method of claim 5, further comprising hashing the TOCs and storing them in a separate hash table.

7. The method of claim 1, further comprising storing updates in a second database that is distinct from the TOC database.

8. The method of claim 1, wherein the offset values contained in the TOC in the bucket are stored as 15 or fewer bit integers.