Certain aspects of the present disclosure provide techniques for medoid-based data compression. One example method generally includes receiving item data indicative of one or more items, determining one or more medoids based on the item data, determining, for each item of the one or more items, a corresponding medoid based on the one or more medoids, identifying, for each item of the one or more items, a difference between the item and the corresponding medoid for the item, storing the one or more medoids, and storing, for each item of the one or more items, the identified difference between the item and the corresponding medoid.