Static TOC indexing system and method
View Patent ↗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.
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.