# US 11,030,174 B1 · Quantized time range indexing for out of order event collections > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,030,174 B1 - Document ID: US11030174B1 - Status: Granted - Kind: B1 - Application number: 15/957,849 - Filed: 2018-04-19 - Granted: 2021-06-08 - Earliest claimed: 2018-04-19 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Erik Hagerup - Web page: https://patentgrep.com/patent/US11030174B1 ## CPC - G06F 16/2246: {Trees, e.g. B+trees} - G06F 21/64: Protecting data integrity, e.g. using checksums, certificates or signatures - G06F 16/2379: {Updates performed during online database operations; commit processing} - G06F 16/2477: {Temporal data queries} - G06F 21/602: {Providing cryptographic facilities or services} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system receives a set of log data generated from one or more computing services. The system identifies a first timestamp and a second timestamp associated with a set of log data. The system generates an index by encoding the quantized first and second timestamps and identifies a prefix length between the first and second timestamps. The prefix length is then used as a basis to interweave the encoded bits associated with the first and second timestamps to generate an index value. The index value may then be used as a key in connection with the index to locate log data to satisfy a query request. ## Claims ### Claim 1 A computer-implemented method, comprising: obtaining a set of log data; identifying a beginning timestamp and an end timestamp associated with the set of log data; generating an index for the set of log data by at least: encoding bits associated with the beginning timestamp to generate an encoded beginning timestamp and encoding the end timestamp to generate an encoded end timestamp; determining a maximum prefix length between the encoded beginning timestamp and the encoded end timestamp, wherein the determination is performed by at least comparing the bits associated with the encoded beginning timestamp and the encoded end timestamp; interweaving, based at least in part on the determination, the encoded beginning timestamp and the encoded end timestamp using a tristate representation to result in an index value prefix; padding the index value prefix to generate an index value; and adding the index value to the index; and using the index to satisfy a query request to locate log data, the query request including information indicating a start and an end time. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the set of log data are obtained from one or more computing services operated by a computer resource service provider. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the index value prefix is encoded, using hex encoding, to a hex encoded prefix. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, further comprising: comparing a size of the set of log data is compared against a threshold; and in response to the size of the set of log data not exceeding the threshold, force flushing the set of log data. ### Claim 5 A system, comprising: one or more processors; and memory that stores computer-executable instructions that, as a result of being executed, cause the one or more processors to: identify a first data item and a second data item associated with a set of data indicating a range for items of the set of data; generate an index for the set of data by at least: obtaining a first value of the first data item and a second value of the second data item; determining a maximum prefix length between encoded bits representing the first value and encoded bits representing the second value; and combining the first value and the second value, based at least in part on the determination, by at least interweaving the encoded bits representing the first value and encoded bits representing the second value using a tristate representation to form an index value; and update the index to associate the index value with a set of data that comprises the first data item and the second data item. ### Claim 6 (depends on 5) The system of claim 5, wherein the first value and second value are timestamps. ### Claim 7 (depends on 5) The system of claim 5, wherein the first value and second value indicate, respectively, a position of the first data item and second data item in the set of data. ### Claim 8 (depends on 7) The system of claim 7, wherein the first value and second value, respectively, correspond to an earliest data item and latest data item in a time-based ordering of the set of data. ### Claim 9 (depends on 5) The system of claim 5, wherein combining the first data item and second data item include interweaving a set of respective bits associated with the first data item and second data item, wherein the set of respective bits is equal to the amount of bits of the maximum prefix length. ### Claim 10 (depends on 5) The system of claim 5, wherein the instructions further comprise computer-executable instructions that, as a result of being executed by the one or more processors, cause the system to pad the index value. ### Claim 11 (depends on 10) The system of claim 10, wherein the index value is padded to a length of encoded bits representing the first value or a length of encoded bits representing the second value. ### Claim 12 (depends on 5) The system of claim 5, wherein the index is a B-Tree index. ### Claim 13 A non-transitory computer-readable storage medium comprising executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least: identify a first value and a second value associated with a set of data indicating a range for items of the set of data; generate an index for the set of data by at least: determining a maximum prefix length between encoded bits representing the first value and encoded bits representing the second value; and combine the first value and the second value based on the length of bits associated with the maximum prefix length, by at least interweaving encoded bits representing the first value and encoded bits representing the second value using a tristate representation, to form an index value for a query request; and use the index value to search an index to satisfy the query request to locate a set of data. ### Claim 14 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to recursively generate the index value by removing the last value of the index value and padding a value such that all data in a time range are identified. ### Claim 15 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to perform one or more modifications to the data, wherein the one or more modification includes aggregating the data. ### Claim 16 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the first value indicates a first time and second value indicates a second time. ### Claim 17 (depends on 16) The non-transitory computer-readable storage medium of claim 16, wherein first value includes a timestamp indicating an earliest value and the second value includes a timestamps indicating a latest value in a time-based ordering set of data. ### Claim 18 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the index is a tree-based index. ### Claim 19 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the index value is generated by at least obtaining the first value indicating earliest in time and the second value indicating latest in time from the query request. ### Claim 20 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein combining the first value and the second value to form an index value for a query request further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to interweave the encoded bits starting from a first position of the first value and encoded bits starting from a first position of the second value.