Quantized time range indexing for out of order event collections
AssigneeAmazon Technologies, Inc.
InventorErik Hagerup
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.