# US 7,613,701 B2 · Matching of complex nested objects by multilevel hashing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,701 B2 - Document ID: US7613701B2 - Status: Granted - Kind: B2 - Application number: 11/021,689 - Filed: 2004-12-22 - Published: 2006-06-22 - Granted: 2009-11-03 - Earliest claimed: 2004-12-22 - Assignees: International Business Machines Corporation - Inventors: Ting Zhao; Kenneth L. Milsted; Kenneth Carlin Nelson; Christopher T. Lehman; Qing Lu - Web page: https://patentgrep.com/patent/US7613701B2 ## CPC - G06F 16/9014: {hash tables} - Y10S 707/99939: Privileged access - Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation - Y10S 707/99943: Generating database or data structure, e.g. via user interface - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract A computer-based method with multilevel hashing for lookup of a complex nested object (such as access control list) which has a plurality of nesting levels and each level has at least one element. Method stores representatives of a complex nested object in a data structure at locations determined by recursive multilevel hashing of the complex nested object elements. When needed, a match for an inputted complex nested object is determined by applying the same recursive multilevel hashing to the inputted complex nested object, as used during the storing of the complex nested object, and performing integer comparisons with hash values of the stored complex nested object. ## Claims ### Claim 1 A computer-based method using multilevel hashing, in a computer with a physical memory, for lookup of a complex nested object having a plurality of nesting levels, each said level having at least one element, comprising: storing representatives of a complex nested object in a data structure at locations determined by multilevel hashing of the complex nested object elements performed recursively for each said nesting level, each said location defined by calculating a position index for each said representative of the nesting level as a modulo of hash values of the elements from the previous nesting level and the data structure size; and determining a match for an inputted complex nested object by performing the same recursive multilevel hashing on the inputted complex nested object as during storing of the complex nested object, and performing integer comparisons with hash values of the complex nested object, found at the data structure locations determined by the position index calculated from the hash values, by comparing, for each said nesting level, an overall level hash value and, if a match is found, comparing each said element hash value, wherein a complex nested object is an access control list having representatives stored in an array of linked lists, wherein a linked list storing a set of access control lists with a same position index, and wherein the access control list having a set of rules' representatives stored in an array of linked list of rules in the physical memory, where each said rule having a user identifier and a set of attributes. ### Claim 2 (depends on 1) The method according to claim 1, wherein the representatives representing each said nesting level and each said element of the complex nested object in the data structure, and wherein each said representative is chosen from the group comprising an identifier, a hash value, match validation data and the complex nested object elements. ### Claim 3 (depends on 1) The method according to claim 1, wherein the step of determining a match comprises obtaining a matching object identifier. ### Claim 4 (depends on 1) The method according to claim 1, wherein the step of determining a match, if a match was not found, further comprises a step of storing representatives of the inputted complex nested object in the data structure at locations determined by recursive multilevel hashing of the inputted complex nested object elements. ### Claim 5 (depends on 1) The method according to claim 1, wherein the data structure is chosen from the group comprising tables, arrays, hash tables, linked lists, array lists, registers and cache registers. ### Claim 6 (depends on 1) The method according to claim 1, wherein a complex nested object is an access control list of a DB2 Content Manager useable by a Host Interface Server of the DB2 Content Manager Records Manager Enabler. ### Claim 7 A computer-based system using multilevel hashing, in a computer with a physical memory, for lookup of a complex nested object having a plurality of nesting levels, each said level having at least one element, comprising the means for: storing representatives of a complex nested object in a data structure at locations determined by multilevel hashing of the complex nested object elements performed recursively for each said nesting level, each said location defined by calculating a position index for each said representative of the nesting level as a modulo of hash values of the elements from the previous nesting level and the data structure size; and determining a match for an inputted complex nested object by performing the same recursive multilevel hashing on the inputted complex nested object as during storing of the complex nested object, and performing integer comparisons with hash values of the complex nested object, found at the data structure locations determined by the position index calculated from the hash values, by comparing, for each said nesting level, an overall level hash value and, if a match is found, comparing each said element hash value, wherein a complex nested object is an access control list having representatives stored in an array of linked lists, wherein a linked list storing a set of access control lists with a same position index, and wherein the access control list having a set of rules′ representatives stored in an array of linked list of rules in the physical memory, where each said rule having a user identifier and a set of attributes. ### Claim 8 (depends on 7) The system according to claim 7, wherein the representatives representing each said nesting level and each said element of the complex nested object in the data structure and wherein each said representative is chosen from the group comprising an identifier, a hash value, match validation data and the complex nested object elements. ### Claim 9 (depends on 7) The system according to claim 7, wherein the means for determining a match comprises means for obtaining a matching object identifier. ### Claim 10 (depends on 7) The system according to claim 7, wherein the means for determining a match, if a match was not found, further comprises means for storing representatives of the inputted complex nested object in the data structure at locations determined by recursive multilevel hashing of the inputted complex nested object elements. ### Claim 11 (depends on 7) The system according to claim 7, wherein the data structure is chosen from the group comprising tables, arrays, hash tables, linked lists, array lists, registers and cache registers. ### Claim 12 (depends on 7) The system according to claim 7, wherein a complex nested object is an access control list of a DB2 Content Manager useable by a Host Interface Server of the DB2 Content Manager Records Manager Enabler. ### Claim 13 A computer program product embedded in a computer usable medium of a computer with a physical memory and a database management system, tangibly embodying a program of instructions executable by the computer to perform a computer-based method using multilevel hashing for lookup of a complex nested object having a plurality of nesting levels, each said level having at least one element, compnsing: storing representatives of a complex nested object in a data structure at locations determined by multilevel hashing of the complex nested object elements performed recursively for each said nesting level, each said location defined by calculating a position index for each said representative of the nesting level as a modulo of hash values of the elements from the previous nesting level and the data structure size; and determining a match for an inputted complex nested object by performing the same recursive multilevel hashing on the inputted complex nested object as during storing of the complex nested object, and performing integer comparisons with hash values of the complex nested object, found at the data structure locations determined by the position index calculated from the hash values, by comparing, for each said nesting level, an overall level hash value and, if a match is found, comparing each said element hash value, wherein a complex nested object is an access control list having representatives stored in an array of linked lists, wherein a linked list storing a set of access control lists with a same position index, and wherein the access control list having a set of rules′ representatives stored in an array of linked list of rules in the physical memory, where each said rule having a user identifier and a set of attributes. ### Claim 14 (depends on 13) The computer program product according to claim 13, wherein the representatives representing each said nesting level and each said element of the complex nested object in the data structure and wherein each said representative is chosen from the group comprising an identifier, a hash value, match validation data and the complex nested object elements. ### Claim 15 (depends on 13) The computer program product according to claim 13, wherein the step of determining a match comprises obtaining a matching object identifier. ### Claim 16 (depends on 13) The computer program product according to claim 13, wherein the step of determining a match, if a match was not found, further comprises a step of storing representatives of the inputted complex nested object in the data structure at locations determined by recursive multilevel hashing of the inputted complex nested object elements. ### Claim 17 (depends on 13) The computer program product according to claim 13, wherein the data structure is chosen from the group comprising tables, arrays, hash tables, linked lists, array lists, registers and cache registers. ### Claim 18 (depends on 2) The computer program product according to claim 2, wherein a complex nested object is an access control list of a DB2 Content Manager useable by a Host Interface Server of the DB2 Content Manager Records Manager Enabler.