# US 11,030,151 B2 · Constructing an inverted index > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,030,151 B2 - Document ID: US11030151B2 - Status: Granted - Kind: B2 - Application number: 15/940,302 - Filed: 2018-03-29 - Published: 2018-10-04 - Granted: 2021-06-08 - Earliest claimed: 2017-03-29 - Assignees: Avast Software s.r.o. - Applicants: Avast Software s.r.o. - Inventors: Antonín K{hacek over (r)}í{hacek over (z)} - Web page: https://patentgrep.com/patent/US11030151B2 ## CPC - G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)} - G06F 16/31: Indexing; Data structures therefor; Storage structures - G06F 16/951: Indexing; Web crawling techniques - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems and methods create an inverted index for a set of documents utilizing a heap data structure. The documents can be divided into a series of n-grams. The n-grams can be hashed, producing hashed n-gram values. A first hashed n-gram value can be placed into the heap data structure. Operations performed using the heap data structure obtain document identifiers that are associated with documents that include a hashed n-gram value that matches the top n-gram value in the heap. ## Claims ### Claim 1 A method for creating an inverted index, the method comprising: receiving a plurality of documents to be indexed; dividing each of the plurality of documents into a plurality of n-grams, wherein an n-gram comprises a series of n bytes from the document; hashing each n-gram of the plurality of n-grams to produce a plurality of hashed n-gram values; for each document of the plurality of documents, placing the plurality of hashed n-gram values of the document and a document identifier associated with the document into a heap data structure, wherein the heap data structure is a tree-based data structure in which a key for a node is ordered with respect to a key for a parent of the node in the same way across all of the nodes in the heap; and while the heap data structure is not empty, performing first operations comprising: obtaining a first top hashed n-gram value from the heap data structure, obtaining from the heap data structure the document identifier of every document of the plurality of documents having at least one hashed n-gram value that is the same as the first top hashed n-gram value, wherein obtaining from the heap data structure the document identifier comprises: saving a copy of a second top hashed n-gram value; and while the heap data structure is not empty, performing second operations comprising: determining whether a third top hashed n-gram value matches the copy of the second top hashed n-gram value, in response to determining that the third top hashed n-gram value does not match the copy of the second top hashed n-gram value, returning a results list, in response to determining that the third top hashed n-gram value matches the copy of the second top hashed n-gram value, performing operations comprising: inserting a document identifier associated with the third top hashed n-gram value into the results list, and popping the third top hashed n-gram value from the heap, and placing the obtained document identifiers into an inverted index in association with the first top hashed n-gram value. ### Claim 2 (depends on 1) The method of claim 1, wherein the second operations further comprise: saving a copy of a current top item of the heap; getting a next hashed n-gram value from a document associated with the copy of the current top item of the heap; and pushing the next hashed n-gram value into the heap. ### Claim 3 (depends on 1) The method of claim 1, further comprising sorting and deduplicating the hashed n-gram values associated with each of the plurality of documents. ### Claim 4 (depends on 1) The method of claim 1, wherein the plurality of documents includes at least one binary file. ### Claim 5 (depends on 1) The method of claim 1, wherein the heap data structure is a max heap data structure. ### Claim 6 A non-transitory machine-readable medium having instructions stored thereon, the instructions comprising computer executable instructions that when executed, cause one or more processors to: receive a plurality of documents to be indexed; divide each of the plurality of documents into a plurality of n-grams, wherein an n-gram comprises a series of n bytes from the document; hash each n-gram of the plurality of n-grams to produce a plurality of hashed n-gram values; for each document of the plurality of documents, place the plurality of hashed n-gram values of the document and a document identifier associated with the document into a heap data structure, wherein the heap data structure is a tree-based data structure in which a key for a node is ordered with respect to a key for a parent of the node in the same way across all of the nodes in the heap; and while the heap data structure is not empty, perform first operations comprising: obtain a first top hashed n-gram value from the heap data structure, obtain from the heap data structure the document identifier of every document of the plurality of documents having at least one hashed n-gram value that is the same as the first top hashed n-gram value, wherein obtain from the heap data structure the document identifier comprises: save a copy of a second top hashed n-gram value; and while the heap data structure is not empty, perform second operations comprising: determine whether a third top hashed n-gram value matches the copy of the second top hashed n-gram value, in response to a determination that the third top hashed n-gram value does not match the copy of the second top hashed n-gram value, return a results list, in response to a determination that the third top hashed n-gram value matches the copy of the second top hashed n-gram value, perform operations comprising: insert a document identifier associated with the third top hashed n-gram value into the results list, and pop the third top hashed n-gram value from the heap, and place the obtained document identifiers into an inverted index in association with the first top hashed n-gram value. ### Claim 7 (depends on 6) The non-transitory machine-readable medium of claim 6, wherein the second operations further comprise: save a copy of a current top item of the heap; get a next hashed n-gram value from a document associated with the copy of the current top item of the heap; and push the next hashed n-gram value into the heap. ### Claim 8 (depends on 6) The non-transitory machine-readable medium of claim 6, wherein the computer executable instructions further comprise instructions to sort and deduplicate the hashed n-gram values associated with each of the plurality of documents. ### Claim 9 (depends on 6) The non-transitory machine-readable medium of claim 6, wherein the plurality of documents include at least one binary file. ### Claim 10 (depends on 6) The non-transitory machine-readable medium of claim 6, wherein the heap data structure is a max heap data structure. ### Claim 11 An apparatus comprising: one or more processors; and a non-transitory machine-readable medium having computer executable instructions stored thereon, that when executed, cause the one or more processors to: receive a plurality of documents to be indexed; divide each of the plurality of documents into a plurality of n-grams, wherein an n-gram comprises a series of n bytes from the document; hash each n-gram of the plurality of n-grams to produce a plurality of hashed n-gram values; for each document of the plurality of documents, place the plurality of hashed n-gram values of the document and a document identifier associated with the document into a heap data structure, wherein the heap data structure is a tree-based data structure in which a key for a node is ordered with respect to a key for a parent of the node in the same way across all of the nodes in the heap; and while the heap data structure is not empty, perform first operations comprising: obtain a first top hashed n-gram value from the heap data structure, obtain from the heap data structure the document identifier of every document of the plurality of documents having at least one hashed n-gram value that is the same as the first top hashed n-gram value, wherein obtain from the heap data structure the document identifier comprises: save a copy of a second top hashed n-gram value; and while the heap data structure is not empty, perform second operations comprising: determine whether a third top hashed n-gram value matches the copy of the second top hashed n-gram value, in response to a determination that the third top hashed n-gram value does not match the copy of the second top hashed n-gram value, return a results list, in response to a determination that the third top hashed n-gram value matches the copy of the second top hashed n-gram value, perform operations comprising: insert a document identifier associated with the third top hashed n-gram value into the results list, and pop the third top hashed n-gram value from the heap, and place the obtained document identifiers into an inverted index in association with the first top hashed n-gram value. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the second operations further comprise: save a copy of a current top item of the heap; get a next hashed n-gram value from a document associated with the copy of the current top item of the heap; and push the next hashed n-gram value into the heap. ### Claim 13 (depends on 11) The apparatus of claim 11, wherein the computer executable instructions further comprise instructions to sort and deduplicate the hashed n-gram values associated with each of the plurality of documents. ### Claim 14 (depends on 11) The apparatus of claim 11, wherein the plurality of documents includes at least one binary file. ### Claim 15 (depends on 11) The apparatus of claim 11, wherein the heap data structure is a max heap data structure.