Constructing an inverted index

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.

2. 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.

3. The method of claim 1 , further comprising sorting and deduplicating the hashed n-gram values associated with each of the plurality of documents.

4. The method of claim 1 , wherein the plurality of documents includes at least one binary file.

5. The method of claim 1 , wherein the heap data structure is a max heap data structure.

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.

7. 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.

8. 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.

9. The non-transitory machine-readable medium of claim 6 , wherein the plurality of documents include at least one binary file.

10. The non-transitory machine-readable medium of claim 6 , wherein the heap data structure is a max heap data structure.

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.

12. 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.

13. 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.

14. The apparatus of claim 11 , wherein the plurality of documents includes at least one binary file.

15. The apparatus of claim 11 , wherein the heap data structure is a max heap data structure.