DETAILED ACTION
This office action is in response to the communication filed on March 31, 2026. Claims 1-20 are currently pending.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Applicant's arguments filed on March 31, 2026 have been fully considered but they are not persuasive for the following reasons:
Applicant in Pages 7-8 of the Remarks argues that the amended claims are directed to statutory subject matter.
Examiner respectfully disagrees.
The generating and determining steps recited in independent claim 1, and similarly recited in independent claims 12 and 20, recites an abstract idea within the “Mental Processes” grouping of abstract ideas, because a person can mentally or using a pen and paper perform the limitations recited in said steps, as discussed in detail in the 101 rejection below.
The remaining steps in the claims that are identified as reciting additional elements, such as the obtaining, indexing, and receiving steps in claims 1, 12, and 19, are only adding insignificant extra-solution activity to the judicial exception, are recognized as a well understood, routine, and conventional activity within the field of computer functions, and are applying the exception using generic computer components, which is not sufficient to amount to significantly more than the judicial exception and are not directed to any specific improvement in computer technology.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Applicant in Pages 8-10 of the Remarks argues that Benjamin-Deckert and Waghulde do not teach or even suggest the amended features “indexing the document in a search index including a plurality of index entries of time series data arranged in a time sorted order” and “generating, each of the plurality of index entries having a common fixed key size and a common fixed value size, a first index entry having a key based on the digest and a pointer for pointing to a storage location of the document, wherein the pointer is a value of the first index entry in the time sorted order and is a document identification pointing to the storage location”, as recited in amended independent claim 1 and similarly recited in amended independent claims 12 and 20.
Examiner respectfully disagrees. The previously cited prior art Benjamin-Deckert and Waghulde and the newly cited prior art alone and/or in combination discloses the argued features.
In response to applicant's arguments against the references individually, one cannot show nonobviousness by attacking references individually where the rejections are based on combinations of references. See In re Keller, 642 F.2d 413, 208 USPQ 871 (CCPA 1981); In re Merck & Co., 800 F.2d 1091, 231 USPQ 375 (Fed. Cir. 1986).
Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document.
Benjamin-Deckert in [0071] discloses arranging the ordering of index values.
Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index.
Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database.
Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length.
Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field.
Benjamin-Deckert does not explicitly disclose index entries of time series data arranged in a time sorted order, but the Waghulde and Vemulapalli references disclose the features.
Benjamin-Deckert in [0054] and [0161] discloses generating a primary key for indexing a document, adding metadata to the primary key, modifying the document to include the primary key and metadata, storing the document, allowing access based on key-name:key-value pair relationship search of a primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document.
Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document.
Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document.
Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index.
Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database.
Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length.
Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field.
Benjamin-Deckert does not explicitly disclose a first index entry in the time sorted order, but the Waghulde and Vemulapalli references disclose the features.
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, however, Benjamin-Deckert does not explicitly disclose:
…index entries arranged in a…sorted order...;
…an offset relative to the…sorted order…;
Waghulde in [0036] and [0037] discloses data partitioned into data partitions, each partition has range of key values that are partially sorted, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key, key values are stored in partially sorted key order in partitions and prefix tree keeps the sorted order of a start key of each partition so data can be read in key order by following the prefix tree index node order, each data partition can be fully sorted before executing range query.
Waghulde in [0042] and [0043] discloses each partition contains key-value pairs, partition contains sorted list of keys with value offset.
Waghulde in [0053], [0058], and [0059] discloses merging keys list and creating a new sorted keys list, perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned, looking up key in sorted key list, if key is location then corresponding offset is looked up and value is returned.
Benjamin-Deckert and Waghulde do not explicitly disclose index entries of time series data arranged in a time sorted order, but the Vemulapalli reference discloses the feature.
It would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert and Waghulde, to have combined Benjamin-Deckert and Waghulde. The motivation to combine Benjamin-Deckert and Waghulde would be to efficiently store and retrieve data using space optimized prefix tree index.
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, and Waghulde discloses indexing entries in a sorted order, however, Benjamin-Deckert and Waghulde do not explicitly disclose:
index entries of time series data arranged in a time sorted order;
Vemulapalli in [0004] discloses storing a time series in a plurality of documents, storing an array of data points of the time series along with metadata representing a time range of the data points stored in the document.
Vemulapalli in [0018] and 29 discloses a time series document database providing a range of querying and indexing capabilities and enables efficient retrieval and processing of time series data based on time and other criteria, storing time series in a plurality of documents, time series including a series of data points indexed in time order.
Vemulapalli in [0092] and [0093] discloses indexing time series documents based on their time ranges, determining a time range associated with a query and selecting one or more time series documents in a database that contain data points in that particular time range based on the document index.
It would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert, Waghulde, and Vemulapalli, to have combined Benjamin-Deckert, Waghulde, and Vemulapalli. The motivation to combine Benjamin-Deckert, Waghulde, and Vemulapalli would be to enable efficient retrieval and processing of time series data based on time and other criteria by utilizing a time series document database providing a range of querying and indexing capabilities.
For the above reasons, Examiner states that rejection of the current Office action is proper.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-21 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
At step 1:
Independent claims 1, 12, and 20 respectively recite a method, a system, and a computer program product, which are directed to a statutory category such as a process, machine, or an article of manufacture.
At step 2A, prong one:
Independent claim 1 and similarly independent claims 12 and 20 recite the limitations:
“generating, each of the plurality of index entries having a common fixed key size and a common fixed value size, a first index entry having a key based on the digest and a pointer for pointing to a storage location of the document, wherein the pointer is a value of the first index entry in the time sorted order and is a document identification pointing to the storage location”;
A person can mentally or using a pen and paper generate, each of a plurality of index entries having a common fixed key size and a common fixed value size, a first index entry having a key based on a digest and a pointer for pointing to a storage location of a document, wherein the pointer is a value of the first index entry in a time sorted order and is a document identification pointing to the storage location.
“determining whether any index entry in the search index matches the search query, including by searching at least a portion of the plurality of index entries of the search index addressable using an offset relative to the time sorted order and based on the common fixed key size and the common fixed value size”;
A person can mentally or using a pen and paper analyze index entries in a search index and can mentally or using a pen and paper compare information in a search query with information in the entries in the search index.
The person can mentally or using a pen and paper compare the information in the search query with the information in the entries in the search index to mentally or using a pen and paper make a determination of whether any index entry in the search index matches the search query.
The person can mentally or using a pen and paper make a determination of whether any index entry in the search index matches the search query by mentally or using a pen and paper searching at least a portion of the plurality of index entries of the search index addressable using an offset relative to a time sorted order and based on a common fixed key size and a common fixed value size.
The limitations, as recited above, are processes that, under their broadest reasonable interpretation, cover steps that can be performed in the human mind or by a human using a pen and paper, but for recitation of generic computer components.
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of generic computer components, then it falls within the “Mental Processes” grouping of abstract ideas. Accordingly, the claims recite an abstract idea.
At step 2A, prong two:
This judicial exception is not integrated into a practical application.
Independent claim 1 and similarly independent claims 12 and 20 recite the limitations:
“obtaining a digest associated with a document”, which is a step of obtaining data. The step is recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity (MPEP 2106.05(g)).
“indexing the document in a search index including a plurality of index entries of time series data arranged in a time sorted order”, which is a step of indexing or storing data. The step is recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity (MPEP 2106.05(g)).
“receiving a search query”, which is a step of receiving data. The step is
recited at a high level of generality, and amounts to mere data gathering, which is a
form of insignificant extra-solution activity (MPEP 2106.05(g)).
The additional elements “a search index” and “a storage location” in the steps in claim 1 are recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using generic computer components.
The additional elements “a system, comprising: a processor configured to:”, “a search index”, “a storage location”, and “a memory coupled to the processor and configured to provide the processor with instructions” in the steps in claim 12 are recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using generic computer components.
The additional elements “a computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:”, “a search index”, and “a storage location” in the steps in claim 20 are recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using generic computer components.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
At step 2B:
Independent claims 1, 12, and 20 recite the same additional elements as identified in step 2A prong two above. These additional elements are not sufficient to amount to significantly more than the judicial exception.
Independent claim 1 and similarly independent claims 12 and 20 recite the limitations:
“obtaining a digest associated with a document”, which is a step of obtaining or receiving data, and is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of receiving or transmitting data over a network (MPEP 2106.05(d)(II)(i)).
“indexing the document in a search index including a plurality of index entries of time series data arranged in a time sorted order”, which is a step of indexing or storing data, and is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of storing and retrieving information in memory (MPEP 2106.05(d)(II)(iv)).
“receiving a search query”, which is a step of receiving data, and is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of receiving or transmitting data over a network (MPEP 2106.05(d)(II)(i)).
Accordingly, the additional limitations are not sufficient to amount to significantly more than the judicial exception. Therefore, the claims are directed to an abstract idea and are not patent eligible.
Dependent claim 2 and similarly dependent claim 13 recites additional limitations, such as:
“generating the key based on at least a portion of the digest generated for the document, wherein the digest generated for the document comprises a fixed-length message digest, and wherein the key has a one-to-one mapping to the document”.
This limitation is directed to the same abstract idea under the mental processes grouping as independent claims 1 and 12, because a person can mentally or using a pen and paper generate a key based on at least a portion of a digest generated for a document, wherein the digest generated for the document comprises a fixed-length message digest, and wherein the key has a one-to-one mapping to the document, and because the limitation does not recite any additional elements that are sufficient to amount to significantly more.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 3 recites additional limitations, such as:
“wherein the key is associated by one-to-one mapping to the value associated with the storage location of the document”, which is a step of storing data.
At step 2A prong two, the step is recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity.
At step 2B, the step is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of storing and retrieving information in memory (MPEP 2106.05(d)(II)(iv)).
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 4 and similarly dependent claim 14 recites additional limitations, such as:
“wherein the determining of whether any index entry in the search index matches the search query comprises:
determining a primary key based on the search query; and
determining whether any index entry in the search index matches the primary key based on a primary key lookup in the search index”.
These limitations are directed to the same abstract idea under the mental processes grouping as independent claims 1 and 12, because a person can mentally or using a pen and paper determine whether any index entry in a search index matches a search query by mentally or using a pen and paper determining a primary key based on the search query and by mentally or using a pen and paper determining whether any index entry in the search index matches the primary key based on a primary key lookup in the search index, and because the limitations do not recite any additional elements that are sufficient to amount to significantly more.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 5 and similarly dependent claim 15 recites additional limitations, such as:
“determining a prefix of the key, wherein the prefix of the key comprises a beginning number of bits of the key, wherein the number of bits is a prefix length”.
This limitation is directed to the same abstract idea under the mental processes grouping as independent claims 1 and 12, because a person can mentally or using a pen and paper determine a prefix of a key, wherein the prefix of the key comprises a beginning number of bits of the key, wherein the number of bits is a prefix length, and because the limitation does not recite any additional elements that are sufficient to amount to significantly more.
“storing the first index entry in a particular block of a plurality of blocks of the search index based on the prefix of the key, wherein a group of index entries stored in the particular block share an identical prefix”, which is a step of storing data.
At step 2A prong two, the step is recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity.
At step 2B, the step is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of storing and retrieving information in memory (MPEP 2106.05(d)(II)(iv)).
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 6 recites additional limitations, such as:
“determining the prefix length based on a document count in the search index”.
This limitation is directed to the same abstract idea under the mental processes grouping as independent claim 1, because a person can mentally or using a pen and paper determine a prefix length based on a document count in a search index, and because the limitation does not recite any additional elements that are sufficient to amount to significantly more.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 7 and similarly dependent claim 16 recites additional limitations, such as:
“storing in a block header of the particular block a start offset field, wherein the start offset field indicates a starting offset of the particular block on a storage disk;
storing in the block header of the particular block an end offset field, wherein the end offset field indicates an ending offset of the particular block on the storage disk; and
storing a probabilistic filter that is used to test whether an indicated index entry is not a member of the particular block”, which are steps of storing data.
At step 2A prong two, the steps are recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity.
At step 2B, the steps are recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of storing and retrieving information in memory (MPEP 2106.05(d)(II)(iv)).
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 8 recites additional limitation, such as:
“wherein the probabilistic filter comprises a Bloom filter”, which is a step of storing data.
At step 2A prong two, the step is recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity.
At step 2B, the step is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of storing and retrieving information in memory (MPEP 2106.05(d)(II)(iv)).
The additional element “a Bloom filter” is recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using generic computer components.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 9 and similarly dependent claim 17 recites additional limitations, such as:
“determining a primary key based on the search query; and
locating the particular block based on a prefix of the primary key”.
These limitations are directed to the same abstract idea under the mental processes grouping as independent claims 1 and 12, because a person can mentally or using a pen and paper determine a primary key based on a search query, and the person can mentally or using a pen and paper locate a particular block based on a prefix of the primary key, and because the limitations do not recite any additional elements that are sufficient to amount to significantly more.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 10 and similarly dependent claim 18 recites additional limitations, such as:
“determining whether the particular block contains at least one index entry based on the start offset field and the end offset field of the particular block; and
based at least in part in determining that the particular block does not contain at least one index entry, providing an indication that there is not any index entry matching the search query”.
These limitations are directed to the same abstract idea under the mental processes grouping as independent claims 1 and 12, because a person can mentally or using a pen and paper determine whether a particular block contains at least one index entry based on a start offset field and an end offset field of a particular block, and the person can mentally or using a pen and paper provide an indication that there is not any index entry matching a search query based at least in part in determining that the particular block does not contain at least one index entry, and because the limitations do not recite any additional elements that are sufficient to amount to significantly more.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 11 and similarly dependent claim 19 recites additional limitations, such as:
“using the probabilistic filter to determine whether there is not any index entry that matches the search query;
in response to determining that there is not any index entry that matches the search query using the probabilistic filter, indicating that there is not any index entry matching the search query; and
in response to determining that the probabilistic filter cannot determine whether there is a match, performing a binary search on the particular block”.
These limitations are directed to the same abstract idea under the mental processes grouping as independent claims 1 and 12, because a person can mentally or using a pen and paper determine whether there is not any index entry that matches a search query by using a probabilistic filter, in response to determining that there is not any index entry that matches the search query using the probabilistic filter, the person can mentally or using a pen and paper indicate that there is not any index entry matching the search query, and in response to determining that a probabilistic filter cannot determine whether there is a match the person can mentally or using a pen and paper perform a binary search on a particular block, and because the limitations do not recite any additional elements that are sufficient to amount to significantly more.
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Dependent claim 21 recites additional limitation, such as:
“wherein the pointer is the value of the first index entry and is a document ID”, which is a step of storing data.
At step 2A prong two, the step is recited at a high level of generality, and amounts to mere data gathering, which is a form of insignificant extra-solution activity.
At step 2B, the step is recognized as a well understood, routine, and conventional activity within the field of computer functions as an element of storing and retrieving information in memory (MPEP 2106.05(d)(II)(iv)).
Accordingly, the additional elements, individually or in combination, do not integrate the abstract idea into a practical application, even viewing the claims a whole, because it does not impose any meaningful limits on practicing the abstract idea.
Accordingly, dependent claims 2-11, 13-19, and 21 are also directed to abstract idea without significantly more and are not patent eligible.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Benjamin-Deckert (US Pub 2019/0179948) in view of Waghulde (US Pub 2017/0212680) and in further view of Vemulapalli (US Pub 2024/0346057, provisional application filing date 04/12/23).
With respect to claim 1, Benjamin-Deckert discloses a method, comprising:
obtaining a digest associated with a document (Benjamin-Deckert in [0054] and [0161] discloses storing document in a database by taking the document, parsing the document to determine a characterization of the document, generating a primary key for indexing the document, adding metadata to the primary key, modifying the document to include the primary key, storing the modified document, and allowing access based on a key-name: key value pair relationship search of the primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document; Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document);
indexing the document in a search index including a plurality of index entries of…data…arranged in a…order (Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0071] discloses arranging the ordering of index values; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose index entries of time series data arranged in a time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below);
generating, each of the plurality of index entries having a common fixed key size and a common fixed value size, a first index entry having a key based on the digest and a pointer pointing to a storage location of the document, wherein the pointer is a value of the first index entry…and is a document identification pointing to the storage location (Benjamin-Deckert in [0054] and [0161] discloses generating a primary key for indexing a document, adding metadata to the primary key, modifying the document to include the primary key and metadata, storing the document, allowing access based on key-name:key-value pair relationship search of a primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document; Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document; Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose a first index entry in the time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below);
receiving a search query (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database); and
determining whether any index entry in the search index matches the search query, including by searching at least a portion of the plurality of index entries of the search index addressable using an offset…and based on the common fixed key size and the common fixed value size (Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose an offset relative to the time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below).
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, however, Benjamin-Deckert does not explicitly disclose:
…index entries arranged in a…sorted order...;
…an offset relative to the…sorted order…;
The Waghulde reference discloses index entries arranged in a sorted order and an offset relative to the sorted order (Waghulde in [0036] and [0037] discloses data partitioned into data partitions, each partition has range of key values that are partially sorted, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key, key values are stored in partially sorted key order in partitions and prefix tree keeps the sorted order of a start key of each partition so data can be read in key order by following the prefix tree index node order, each data partition can be fully sorted before executing range query; Waghulde in [0042] and [0043] discloses each partition contains key-value pairs, partition contains sorted list of keys with value offset; Waghulde in [0053], [0058], and [0059] discloses merging keys list and creating a new sorted keys list, perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned, looking up key in sorted key list, if key is location then corresponding offset is looked up and value is returned; here Benjamin-Deckert and Waghulde do not explicitly disclose index entries of time series data arranged in a time sorted order, but the Vemulapalli reference discloses the feature, as discussed below);
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert and Waghulde, to have combined Benjamin-Deckert and Waghulde. The motivation to combine Benjamin-Deckert and Waghulde would be to efficiently store and retrieve data using space optimized prefix tree index (Waghulde: [0002]).
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, and Waghulde discloses indexing entries in a sorted order, however, Benjamin-Deckert and Waghulde do not explicitly disclose:
index entries of time series data arranged in a time sorted order;
The Vemulapalli reference discloses index entries of time series data arranged in a time sorted order (Vemulapalli in [0004] discloses storing a time series in a plurality of documents, storing an array of data points of the time series along with metadata representing a time range of the data points stored in the document; Vemulapalli in [0018] and 29 discloses a time series document database providing a range of querying and indexing capabilities and enables efficient retrieval and processing of time series data based on time and other criteria, storing time series in a plurality of documents, time series including a series of data points indexed in time order; Vemulapalli in [0092] and [0093] discloses indexing time series documents based on their time ranges, determining a time range associated with a query and selecting one or more time series documents in a database that contain data points in that particular time range based on the document index).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert, Waghulde, and Vemulapalli, to have combined Benjamin-Deckert, Waghulde, and Vemulapalli. The motivation to combine Benjamin-Deckert, Waghulde, and Vemulapalli would be to enable efficient retrieval and processing of time series data based on time and other criteria by utilizing a time series document database providing a range of querying and indexing capabilities (Vemulapalli: [0018]).
With respect to claim 2, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 1, further comprising:
generating the key based on at least a portion of the digest generated for the document, wherein the digest generated for the document comprises a fixed-length message digest, and wherein the key has a one-to-one mapping to the document (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database).
With respect to claim 3, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 1, wherein the key is associated by one-to-one mapping to the value associated with the storage location of the document (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database).
With respect to claim 4, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 1, wherein the determining of whether any index entry in the search index matches the search query comprises:
determining a primary key based on the search query (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database); and
determining whether any index entry in the search index matches the primary key based on a primary key lookup in the search index (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database).
With respect to claim 5, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 1, however, Benjamin-Deckert does not explicitly disclose:
determining a prefix of the key, wherein the prefix of the key comprises a beginning number of bits of the key, wherein the number of bits is a prefix length (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
storing the first index entry in a particular block of a plurality of blocks of the search index based on the prefix of the key, wherein a group of index entries stored in the particular block share an identical prefix (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 6, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 5, further comprising:
determining the prefix length based on a document count in the search index (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 7, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 5, further comprising:
storing in a block header of the particular block a start offset field, wherein the start offset field indicates a starting offset of the particular block on a storage disk (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter);
storing in the block header of the particular block an end offset field, wherein the end offset field indicates an ending offset of the particular block on the storage disk (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
storing a probabilistic filter that is used to test whether an indicated index entry is not a member of the particular block (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 8, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 7, wherein the probabilistic filter comprises a Bloom filter (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 9, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 7, further comprising:
determining a primary key based on the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
locating the particular block based on a prefix of the primary key (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 10, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 9, further comprising:
determining whether the particular block contains at least one index entry based on the start offset field and the end offset field of the particular block (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
based at least in part in determining that the particular block does not contain at least one index entry, providing an indication that there is not any index entry matching the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 11, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the method of claim 10, further comprising:
using the probabilistic filter to determine whether there is not any index entry that matches the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter);
in response to determining that there is not any index entry that matches the search query using the probabilistic filter, indicating that there is not any index entry matching the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
in response to determining that the probabilistic filter cannot determine whether there is a match, performing a binary search on the particular block (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 12, Benjamin-Deckert discloses a system (Benjamin-Deckert in [0032] discloses a computer system), comprising:
a processor (Benjamin-Deckert in [0032] discloses a computer system including one or more processors) configured to:
obtain a digest associated with a document (Benjamin-Deckert in [0054] and [0161] discloses storing document in a database by taking the document, parsing the document to determine a characterization of the document, generating a primary key for indexing the document, adding metadata to the primary key, modifying the document to include the primary key, storing the modified document, and allowing access based on a key-name: key value pair relationship search of the primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document; Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document);
index the document in a search index including a plurality of index entries of…data…arranged in a…order (Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0071] discloses arranging the ordering of index values; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose index entries of time series data arranged in a time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below);
generate, each of the plurality of index entries having a common fixed key size and a common fixed value size, a first index entry having a key based on the digest and a pointer pointing to a storage location of the document, wherein the pointer is a value of the first index entry…and is a document identification pointing to the storage location (Benjamin-Deckert in [0054] and [0161] discloses generating a primary key for indexing a document, adding metadata to the primary key, modifying the document to include the primary key and metadata, storing the document, allowing access based on key-name:key-value pair relationship search of a primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document; Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document; Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose a first index entry in the time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below);
receive a search query (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database); and
determine whether any index entry in the search index matches the search query, including by searching at least a portion of the plurality of index entries of the search index addressable using an offset…and based on the common fixed key size and the common fixed value size (Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose an offset relative to the time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below); and
a memory coupled to the processor and configured to provide the processor with instructions (Benjamin-Deckert in [0031], [0032], and [0035] discloses a computer system including one or more processors and memory storing instructions).
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, however, Benjamin-Deckert does not explicitly disclose:
…index entries arranged in a…sorted order...;
…an offset relative to the…sorted order…;
The Waghulde reference discloses index entries arranged in a sorted order and an offset relative to the sorted order (Waghulde in [0036] and [0037] discloses data partitioned into data partitions, each partition has range of key values that are partially sorted, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key, key values are stored in partially sorted key order in partitions and prefix tree keeps the sorted order of a start key of each partition so data can be read in key order by following the prefix tree index node order, each data partition can be fully sorted before executing range query; Waghulde in [0042] and [0043] discloses each partition contains key-value pairs, partition contains sorted list of keys with value offset; Waghulde in [0053], [0058], and [0059] discloses merging keys list and creating a new sorted keys list, perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned, looking up key in sorted key list, if key is location then corresponding offset is looked up and value is returned; here Benjamin-Deckert and Waghulde do not explicitly disclose index entries of time series data arranged in a time sorted order, but the Vemulapalli reference discloses the feature, as discussed below);
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert and Waghulde, to have combined Benjamin-Deckert and Waghulde. The motivation to combine Benjamin-Deckert and Waghulde would be to efficiently store and retrieve data using space optimized prefix tree index (Waghulde: [0002]).
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, and Waghulde discloses indexing entries in a sorted order, however, Benjamin-Deckert and Waghulde do not explicitly disclose:
index entries of time series data arranged in a time sorted order;
The Vemulapalli reference discloses index entries of time series data arranged in a time sorted order (Vemulapalli in [0004] discloses storing a time series in a plurality of documents, storing an array of data points of the time series along with metadata representing a time range of the data points stored in the document; Vemulapalli in [0018] and 29 discloses a time series document database providing a range of querying and indexing capabilities and enables efficient retrieval and processing of time series data based on time and other criteria, storing time series in a plurality of documents, time series including a series of data points indexed in time order; Vemulapalli in [0092] and [0093] discloses indexing time series documents based on their time ranges, determining a time range associated with a query and selecting one or more time series documents in a database that contain data points in that particular time range based on the document index).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert, Waghulde, and Vemulapalli, to have combined Benjamin-Deckert, Waghulde, and Vemulapalli. The motivation to combine Benjamin-Deckert, Waghulde, and Vemulapalli would be to enable efficient retrieval and processing of time series data based on time and other criteria by utilizing a time series document database providing a range of querying and indexing capabilities (Vemulapalli: [0018]).
With respect to claim 13, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 12, wherein the processor is further configured to:
generate the key based on at least a portion of the digest generated for the document, wherein the digest generated for the document comprises a fixed-length message digest, and wherein the key has a one-to-one mapping to the document (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database).
With respect to claim 14, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 12, wherein the determining of whether any index entry in the search index matches the search query comprises to:
determine a primary key based on the search query (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database); and
determine whether any index entry in the search index matches the primary key based on a primary key lookup in the search index (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database).
With respect to claim 15, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 12, however, Benjamin-Deckert does not explicitly disclose:
determine a prefix of the key, wherein the prefix of the key comprises a beginning number of bits of the key, wherein the number of bits is a prefix length (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
store the first index entry in a particular block of a plurality of blocks of the search index based on the prefix of the key, wherein a group of index entries stored in the particular block share an identical prefix (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 16, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 15, wherein the processor is further configured to:
store in a block header of the particular block a start offset field, wherein the start offset field indicates a starting offset of the particular block on a storage disk (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter);
store in the block header of the particular block an end offset field, wherein the end offset field indicates an ending offset of the particular block on the storage disk (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
store a probabilistic filter that is used to test whether an indicated index entry is not a member of the particular block (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 17, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 16, wherein the processor is further configured to:
determine a primary key based on the search query; and locate the particular block based on a prefix of the primary key (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 18, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 17, wherein the processor is further configured to:
determine whether the particular block contains at least one index entry based on the start offset field and the end offset field of the particular block (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
based at least in part in determining that the particular block does not contain at least one index entry, provide an indication that there is not any index entry matching the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 19, Benjamin-Deckert in view of Waghulde and in further view of Vemulapalli discloses the system of claim 18, wherein the processor is further configured to:
use the probabilistic filter to determine whether there is not any index entry that matches the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter);
in response to determining that there is not any index entry that matches the search query using the probabilistic filter, indicate that there is not any index entry matching the search query (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter); and
in response to determining that the probabilistic filter cannot determine whether there is a match, perform a binary search on the particular block (Waghulde in [0036] discloses data partitioned into data partitions, each partition has range of key values, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key; Waghulde in [0038] and [0059] discloses performing binary search if key is not present after an index lookup, searching for lookup key in prefix tree, if key is located then corresponding value is looked up and returned, if key is not present then a binary search is performed in the list of keys to retrieve the value, if the key is not found after all memory levels have been searched then key not found is returned; Waghulde in [0040] discloses using prefix tree for referencing the start key of data blocks, data inside data blocks sorted in key order, size of data blocks is specified; Waghulde in [0042] discloses each partition contains key-value pairs; Waghulde in [0046] and [0047] discloses length of the key is specified, fixed amount of memory allocation for a key is used, data structure for a key has first few bytes to denote length of the key, then the actual key, and then reference to the value; Waghulde in [0051] discloses allocating space for length of the value, such as 2 bytes or based on expected value size; Waghulde in [0053], [0054], and [0073] discloses key value length based on reference count; Waghulde in [0058] and [0059] discloses perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned; Waghulde in [0085] and in Figure 12 discloses key index is prefix tree index for all keys, each key in the key index store its value offset, scanning block using key index or stored bloom filter, which is a probabilistic filter).
With respect to claim 20, Benjamin-Deckert discloses a computer program product embodied in a non-transitory computer readable medium and comprising computer instructions (Benjamin-Deckert in [0025] and [0175] discloses a computer program product including a non-transitory computer readable storage medium storing program instructions used by an instruction execution device) for:
obtaining a digest associated with a document (Benjamin-Deckert in [0054] and [0161] discloses storing document in a database by taking the document, parsing the document to determine a characterization of the document, generating a primary key for indexing the document, adding metadata to the primary key, modifying the document to include the primary key, storing the modified document, and allowing access based on a key-name: key value pair relationship search of the primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document; Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document);
indexing the document in a search index including a plurality of index entries of…data…arranged in a…order (Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0071] discloses arranging the ordering of index values; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose index entries of time series data arranged in a time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below);
generating, each of the plurality of index entries having a common fixed key size and a common fixed value size, a first index entry having a key based on the digest and a pointer pointing to a storage location of the document, wherein the pointer is a value of the first index entry…and is a document identification pointing to the storage location (Benjamin-Deckert in [0054] and [0161] discloses generating a primary key for indexing a document, adding metadata to the primary key, modifying the document to include the primary key and metadata, storing the document, allowing access based on key-name:key-value pair relationship search of a primary index, a key-name is used for the document, key-name generated by assigning an identifier to the document; Benjamin-Deckert in [0055] and [0056] discloses primary key-value in a primary key-name and key-value pair is hashed, the resulting hash value is used as a key for indexing in the primary index, primary key provides rapid access to any document via the key pair, which includes the primary key-name associated with the key-value, which is obtaining a hash or digest associated with a document, creating secondary or alternate indexes in addition to the primary index to allow alternate ways to reference the document; Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] and [0097] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying an index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data, index entry including metadata of a document, a number of base pointers for the particular document, a version indicator for the index, a length for an index key, a value for the index key, and one or more base keys, database is searchable using the one or more keys, such that after the index is consulted using one of the based pointers for the particular document, one or more entries in the primary index is determines using one or more of the keys, thereby allowing the desired document to be located with the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose a first index entry in the time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below);
receiving a search query (Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database); and
determining whether any index entry in the search index matches the search query, including by searching at least a portion of the plurality of index entries of the search index addressable using an offset…and based on the common fixed key size and the common fixed value size (Benjamin-Deckert in [0059] discloses index including a record of values for a key-name:key-value and an associated hash key used to locate the stored document; Benjamin-Deckert in [0094] discloses index includes hash value, obtaining a first key value associated with the document, rapidly locating the document by searching using the index; Benjamin-Deckert in [0096] discloses receiving a request to access the document, request including a hash value specific to the document, or the primary key-name:key-value pair, or just the primary key-value specific to the desired document, querying the index of the database using the hash value to determine a location of the document, outputting the located data in response to receiving the request to access the data; Benjamin-Deckert in [0097] discloses creating an index for the database, each entry in the index related to one data record of the database, each entry includes hash value keys that match on a one-to-one basis, database is searchable using the keys, allowing desired data records to be located within the database; Benjamin-Deckert in [0102], [0106], and [0108] discloses each record having a key specified by a fixed length offset, offset for each data value is fixed, key for a record is constructed based on offset and length; Benjamin-Deckert in [0111] and [0112] discloses key value hashed into fixed length hash value field; here Benjamin-Deckert does not explicitly disclose an offset relative to the time sorted order, but the Waghulde and Vemulapalli references disclose the features, as discussed below).
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, however, Benjamin-Deckert does not explicitly disclose:
…index entries arranged in a…sorted order...;
…an offset relative to the…sorted order…;
The Waghulde reference discloses index entries arranged in a sorted order and an offset relative to the sorted order (Waghulde in [0036] and [0037] discloses data partitioned into data partitions, each partition has range of key values that are partially sorted, a key of a data determines the partition, partition searched such that the data key would fall in to the key range of that partition, prefix tree has start key of each partition and helps to efficiently find the partition by traversing the prefix tree to compare the data key with the start key, key values are stored in partially sorted key order in partitions and prefix tree keeps the sorted order of a start key of each partition so data can be read in key order by following the prefix tree index node order, each data partition can be fully sorted before executing range query; Waghulde in [0042] and [0043] discloses each partition contains key-value pairs, partition contains sorted list of keys with value offset; Waghulde in [0053], [0058], and [0059] discloses merging keys list and creating a new sorted keys list, perform lookup for a key in the prefix tree and find the node representing the partition where the key value belongs, lookup key is searched in the prefix tree, if key is located then the corresponding value is looked up and returned, looking up key in sorted key list, if key is location then corresponding offset is looked up and value is returned; here Benjamin-Deckert and Waghulde do not explicitly disclose index entries of time series data arranged in a time sorted order, but the Vemulapalli reference discloses the feature, as discussed below);
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert and Waghulde, to have combined Benjamin-Deckert and Waghulde. The motivation to combine Benjamin-Deckert and Waghulde would be to efficiently store and retrieve data using space optimized prefix tree index (Waghulde: [0002]).
Benjamin-Deckert discloses indexing entries including hash value keys for data records, searching a database using the keys, identifying and sorting information to manage data records in the database, arranging the ordering of index values, and each record having a key that is specified by an offset, and Waghulde discloses indexing entries in a sorted order, however, Benjamin-Deckert and Waghulde do not explicitly disclose:
index entries of time series data arranged in a time sorted order;
The Vemulapalli reference discloses index entries of time series data arranged in a time sorted order (Vemulapalli in [0004] discloses storing a time series in a plurality of documents, storing an array of data points of the time series along with metadata representing a time range of the data points stored in the document; Vemulapalli in [0018] and 29 discloses a time series document database providing a range of querying and indexing capabilities and enables efficient retrieval and processing of time series data based on time and other criteria, storing time series in a plurality of documents, time series including a series of data points indexed in time order; Vemulapalli in [0092] and [0093] discloses indexing time series documents based on their time ranges, determining a time range associated with a query and selecting one or more time series documents in a database that contain data points in that particular time range based on the document index).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having the teachings of Benjamin-Deckert, Waghulde, and Vemulapalli, to have combined Benjamin-Deckert, Waghulde, and Vemulapalli. The motivation to combine Benjamin-Deckert, Waghulde, and Vemulapalli would be to enable efficient retrieval and processing of time series data based on time and other criteria by utilizing a time series document database providing a range of querying and indexing capabilities (Vemulapalli: [0018]).
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Remarks
The relevant prior art of record that are not used in claim rejections but are pertinent to the claims or disclosure are:
Smith-Mickelson (US Pat 11,947,550), which discloses searching using a search query for matching documents in an index storing information for a plurality of time ranges and returning time-series data.
Kussmaul (US Pub 2020/0334297), which discloses searching documents in a search index and a series of values indexed in time order as a time-series.
Kan (US Pub 2010/0179953), which discloses using a search index to search for documents and the index arranged on a time-series basis.
Contact Information
Any inquiry concerning this communication or earlier communications from the examiner should be directed to REZWANUL MAHMOOD whose telephone number is (571)272-5625. The examiner can normally be reached M-F 9-5:30.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Ann J. Lo can be reached at 571-272-9767. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/R.M/Examiner, Art Unit 2159 /ANN J LO/Supervisory Patent Examiner, Art Unit 2159
Prosecution Insights