"Gaining Constant time Lookup over Unorganized Data" - Ghadi Shayban, Jeb Beich

Discover how to leverage unorganized data with constant time lookup using a durable hash index, a concrete implementation that provides efficient random access and key-based retrieval.

Key takeaways

Unorganized data can be leveraged through constant time lookup using a durable hash index.
There are only a few ways to organize data, and one of them is using a hash index.
The durable hash index provides an implementation of ilookup, which is sufficient for most use cases.
The index is not an abstraction, but a concrete thing that uses a dataset and data structure.
The dataset needs to be able to expose its keys and values or locations.
The index allows for random access, and the dataset abstraction returns a record given an offset.
The primary operation for this service is lookup by unique key.
The main insight is that lookup by unique key is sufficient, and logarithmic time is not always ideal.
The durable hash index can be used for various use cases, such as certificate revocation lists, credit limit increases, and experimentation platforms.
It can also be used for non-membership tests, where you are actually getting an element by key.
The index is not ideal for every case, but it provides a good balance between performance and simplicity.
The dataset can be a file, and the index can be used to organize the data a single time.
The durable hash index provides a way to achieve constant time lookup over unorganized data.

"Gaining Constant time Lookup over Unorganized Data" - Ghadi Shayban, Jeb Beich

More talks