Applying The Bin Packing Algorithm To Optimize Images On A Market Map
Here’s how our engineers are thinking outside of the “bin” to deliver next-level enhancements to the Market Map Maker.
One of the biggest pains our clients have when developing a Market Map on paper is efficiently and nicely arranging images on them.
The challenge arises from two things:
- Manually arranging images on a market map (sizing and resizing, moving and placing them) is inefficient and can take hours of time.
- Every time a user wants to add more companies to a category on a market map, they have to reposition all existing logos to make it fit & look nice.
Take the Market Map below as an example.
If you’d created this and your boss came in and said, “Let’s add these 2 companies to the Exchanges & Trading section”, that would start a game of image Tetris forcing you to resize and move all existing images to make room for the 2 new ones.
(Note: See this post for all the pain points of creating market maps manually.)
Seeing this pain, CB Insights’ Engineering team Don’t Panic created a solution inspired by the Bin Packing Algorithm.
First, what is the Bin Packing Algorithm?
In a bin packing problem, objects of different volumes must be packed into the minimal number of containers (bins) as possible.
There are various bin packing algorithms, and we came across this good writeup on the subject by Jake Gordon here.
One quote he mentions from the Algorithm Design Manual struck us.
Analytical and empirical results suggest that ‘first fit decreasing’ is the best heuristic. Sort the objects in decreasing order of size, so that the biggest object is first and the smallest last. Insert each object one by one in to the first bin that has room for it.”
And then he shows it in action with the image below which is trying to fit blocks of various sizes into a larger box.
(Please note: per the Jake Gordon example above, we’ll refer to fit first descending bin packing as just bin packing from here on.)
Bin packing (well, kinda)
While the Bin Packing algorithm addressed an issue similar to what we were solving for in the Market Map Maker (i.e. putting objects in containers), it also did not entirely present a solution for helping to optimize Market Map Maker images for a few reasons.
Left Justified Images: The Bin Packing algorithm causes images to be left-justified, with the largest images populating on the top left corner of the “bin”. Here’s an example of what that this looks like in the context of the Market Map Maker, in which the ‘bin’ is a category and the images are company names within the category
Size sorting: A pre-condition for the bin packing algorithm is that the set is sorted, and the best heuristic is by size. But most clients using the Market Map Maker ultimately want images of the same size.
Sorting by size has no UX benefits to the users of the Market Map Maker (and in fact could add confusion, raising questions such as, are the biggest logos at the top of the category because they are the most important companies? or are those the best companies or most well-funded companies? You get the idea.)
No padding: Market Maps are often used in presentations, so the companies on a map need be legible and distinct from each other (i.e., there needs to be white space between each image.) But, the fundamental idea of bin packing is to reduce padding to nothing.
Since pure bin packing doesn’t give any padding, we would need to include padding. We considered creating artificial padding on each image as a first step before sorting using this approach.
This didn’t work for us for two reasons:
- To fake the padding, we would have had to pre-process the companies, temporarily increasing their height and width to act as padding in the bin packing process. Additionally, we’d have to add another field to our “company” representation to store the size of this “offset.” The padding would need to be pre-determined, since it gets set on all companies before the sorting process even starts.
- We’d need to have a version of the offset that pretends it’s bigger.
Our Solution: Smart Logo Positioning
We needed to adapt the bin packing algorithm so that it wouldn’t conflict with some of our goals. As a result, we chose not to sort logos and applied padding by redistributing the available space, first tackling horizontal auto positioning.
Horizontal auto positioning
First, we iterated through all images, and packed them into as few rows as possible, without any padding between them, storing each row as a list.
Within each row list, we then
- Found the remaining space on the right (since all images were packed to the left)
- Redistributed this space between the images
Vertical auto positioning
Now that horizontal spacing was accounted for, we needed to account for vertical spacing. This process mimicked the approach we used for a horizontal row.
First we determined the remaining space below the bottom point on the last row of images, and then redistributed this space between the rows.
Once all of these calculations are completed, the resulting image coordinates are cast into the display and your image positions update!
This is how it looks in action:
What’s next?
With Smart Image Positioning , CB Insights clients can create market maps at record speed and, perhaps more importantly, spend less time on logo Tetris and more time on understanding and analyzing the market. Stay tuned for more Market Map Maker enhancements coming soon.
If you’re an engineer interested in helping us solve fun problems like this one, check out our open positions .
Originally published at https://www.cbinsights.com.
