# US 2020/0401928 A1 · Term-uid generation, mapping and lookup > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401928 A1 - Document ID: US20200401928A1 - Status: Published application - Kind: A1 - Application number: 16/445,408 - Filed: 2019-06-19 - Published: 2020-12-24 - Earliest claimed: 2019-06-19 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Sanjay Sachdev - Web page: https://patentgrep.com/patent/US20200401928A1 ## CPC - G06N 20/00: Machine learning - G06F 16/9017: {using directory or table look-up (use of a directory or look-up table in file systems G06F16/13)} - G06F 16/90335: {Query processing} - G06N 5/02: Knowledge representation; Symbolic representation - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract The disclosed embodiments provide a system for processing data. During operation, the system applies a hash function to a first term to produce a first index into a term offset table. Next, the system obtains, from a first entry at the first index in the term offset table, a first offset of a first record in a log-structured record store. The system retrieves a first UID for the first term from the first record and/or another record that is linked to the first record via a corresponding mapping to the first index. Finally, the system outputs the first UID in association with the first term. ## Claims ### Claim 1 A method, comprising: applying, by one or more computer systems, a hash function to a first term comprising a string to produce a first index into a term offset table; obtaining, by the one or more computer systems from a first entry at the first index in the term offset table, a first offset of a first record in a log-structured record store; upon locating the first term in the first record, retrieving a first unique identifier (UID) for the first term from the first record; and outputting the first UID in association with the first term. ### Claim 2 (depends on 1) The method of claim 1, further comprising: upon verifying an absence of a second term in the first record at the offset in the log-structured record store, retrieving, from the first record, a first link to a second record in the log-structured record store that maps to the first index in the term offset table; and scanning the second record for the second term. ### Claim 3 (depends on 2) The method of claim 2, further comprising: upon verifying the absence of the second term in the second record, scanning additional records linked to the second record in the log-structured record store for the second term. ### Claim 4 (depends on 3) The method of claim 3, further comprising: upon verifying the absence of the second term in the additional records, generating a new UID for the second term. ### Claim 5 (depends on 1) The method of claim 1, further comprising: generating a second UID for a second term; applying the hash function to the second term to produce a second index into the term offset table; obtaining a second offset into the log-structured record store from a second entry at the second index in the term offset table; storing, in a second record at an end of the log-structured record store, the second UID, the second term, and a first link to the second offset; and storing, in the second entry at the second index in the term offset table, a third offset of the second record in the log-structured record store. ### Claim 6 (depends on 1) The method of claim 1, further comprising: generating a second UID for a second term; applying the hash function to the second term to produce a second index into the term offset table; upon verifying a lack of offset into the log-structured record store from a second entry at the second index in the term offset table, storing, in a second record at an end of the log-structured record store, the second UID, the second term, and an indication of a lack of a previous record associated with the second index; and storing, in the second entry at the second index in the term offset table, a second offset of the second record in the log-structured record store. ### Claim 7 (depends on 1) The method of claim 1, further comprising: scanning one or more chains of records in the log-structured record store for a second record comprising a second UID; and retrieving a second term for the second UID from the second record. ### Claim 8 (depends on 1) The method of claim 1, further comprising: storing, in the log-structured record store, a set of terms in a set of records that is ordered by increasing term frequency. ### Claim 9 (depends on 1) The method of claim 1, further comprising: storing the log-structured record store in one or more memory-mapped files. ### Claim 10 (depends on 1) The method of claim 1, further comprising: maintaining the term offset table in memory on the one or more computer systems. ### Claim 11 A method, comprising: applying, by one or more computer systems, a modulo operation to a first unique identifier (UID) to produce a first index into an identifier (ID) offset table; obtaining, by the one or more computer systems, a first offset into a log-structured record store from a first entry at the first index in the ID offset table; upon locating the first UID in a first record at the offset in the log-structured record store, retrieving a first term mapped to the first UID from the first record; and outputting the first term in association with the first UID. ### Claim 12 (depends on 11) The method of claim 11, further comprising: upon verifying an absence of a second UID in the first record at the offset in the log-structured record store, determining a number of links between the first record and a second record containing the second UID by dividing a number of records between the first record and the second record by a divisor of the modulo operation; traversing the number of links from the first record to the second record in the log-structured record store; and retrieving a second term for the second UID from the second record. ### Claim 13 (depends on 11) The method of claim 11, further comprising: generating a second UID for a second term; applying the modulo operation to the second UID to produce a second index into the ID offset table; obtaining a second offset into the log-structured record store from a second entry at the second index in the ID offset table; storing, in a second record at an end of the log-structured record store, the second UID, the second term, and a first link to the second offset; and storing, in the second entry at the second index in the ID offset table, a third offset of the second record in the log-structured record store. ### Claim 14 (depends on 13) The method of claim 13, further comprising: applying a hash function to the second term to produce a third index into a term offset table; obtaining a fourth offset into the log-structured record store from a third entry at the third index in the term offset table; storing a second link to the fourth offset in the second record; and storing, in the third entry at the third index in the term offset table, the third offset of the second record. ### Claim 15 (depends on 13) The method of claim 13, further comprising: storing, at an end of the second record, a link to a beginning of the second record. ### Claim 16 (depends on 13) The method of claim 13, further comprising: storing the log-structured record store in one or more memory-mapped files; and maintaining the term offset table and the ID offset table in memory on the one or more computer systems. ### Claim 17 (depends on 13) The method of claim 13, wherein generating the second UID for the second term comprises: setting the second UID to a counter representing a next available UID. ### Claim 18 (depends on 11) The method of claim 11, further comprising: generating a second UID for a second term; applying the modulo operation to the second UID to produce a second index into the ID offset table; upon verifying a lack of offset into the log-structured record store from a second entry at the second index in the ID offset table, storing, in a second record at an end of the log-structured record store, the second UID, the second term, and an indication of a lack of a previous record associated with the second index; and storing, in the second entry at the second index in the ID offset table, a second offset of the second record in the log-structured record store. ### Claim 19 A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising: applying a hash function to a first term comprising a string to produce a first index into a term offset table; obtaining, from a first entry at the first index in the term offset table, a first offset of a first record in a log-structured record store; upon locating the first term in the first record, retrieving a first unique identifier (UID) for the first term from the first record; and outputting the first UID in association with the first term. ### Claim 20 (depends on 19) The non-transitory computer-readable storage medium of claim 19, the method further comprising: generating a second UID for a second term; applying the hash function to the second term to produce a second index into the term offset table; obtaining a second offset into the log-structured record store from a second entry at the second index in the term offset table; storing, in a second record at an end of the log-structured record store, the second UID, the second term, and a first link to the second offset; and storing, in the second entry at the second index in the term offset table, a third offset of the second record in the log-structured record store.