Back to results
US 11,030,151 B2Granted
Constructing an inverted index
AssigneeAvast Software s.r.o.
InventorAntonín K{hacek over (r)}í{hacek over (z)}
Life of this patent
Estimating the term…
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.
Claims15
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.
14 more elements
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.
14 more elements
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.
17 more elements
Dependencies are inferred from the claim text.