Programming

Logical operations over matrices of sorted numbers

Our e-commerce view engine (E.V.E.) works with matrices of sorted number on the lowest level of its application logic. I’d like to describe some of the algorithms we use to combine such matrices in logic operations. Why do we keep data in matrices in sorted order? There is a price to be paid when adding new number to the matrix when sorted order is required - appending number on last position would be much faster.

What lies on background of e-commerce site

I’d like to start series of posts about problems we’re facing in e-commerce area and what algorithms we used to solve them. There are a lot of e-commerce sites on different levels of complexity in terms of feature richness, data amount, throughput requirements, consistency and realtime updates. Let me first introduce the situation we’re trying to handle and then move to the solution space. Domain Let’s look at example of some e-commerce site product listing:

Precalculated modified preorder tree traversal

MPTT it quite old and very clever way for transposing hierarchical - tree structure to a two-dimensional representation that is suitable for relational databases. MPTT allows to translate information about node tree position into two numbers - left and right bound. Two number fields can be easily indexed and look ups for records in the tree can take advantage of database indexes and perform really quickly. I won’t go into details of the (well) documented MPTT algorithm itself, because there are a lot of sources where you can go for comprehensible explanation (better than I would be able to provide).