Mathematical techniques to reduce the amount of storage memory - MathOverflow

Mathematical techniques to reduce the amount of storage memory

2013-02-05T17:09:40Z

Apologies for the length question. Those acquainted with the analytics industry will know that the next big thing in the information technology world will be the Big Data revolution where huge volumes of data will be processed. Big Data revolution will imply huge requirement of storage space/memory hence it is critical to store data as efficiently as possible. We want to store data in the smartest way that requires the least amount of storage. The following question is on the application of mathematical ideas to reduce the amount of storage memory required to store information of a particular kind.

Problem: This is a consumer information storage problem. There are $k$ customers and $n$ books. Each customer can buy one or more books (without repetition). We want to identify the book purchased by a given customer using the minimum number of memory required for storage. We do not seek to improve the time complexity, we only seek to reduce storage space required.

Method 1 - Traditional approach: This is the common and default approach. Give each book a $d$ digit code and create a field in the data base where the code of the books purchased by the customer in entered, separated by commas. So in the worst case when a customer has brought all $n$ books, we will need $D = nd+d-1$ characters to store this information (including $d-1$ commas) about the customer.

Method 2. Using prime numbers: Assign a unique prime number to each of the books, 2 denotes the first book, 3 the second, $\ldots$ and $p_n$ denotes the $n$-th. Every customer $C_i$ assigned a number $N_i$ which is equal to the product of the prime numbers corresponding to books purchased. By factoring $N_i$, unique factorization theorem ensures that we can identify the exactly the books purchased by the customer. More over two customers will have a common book if and only if they have a common factor. The greater the number of common factors, the greater is the similarity between the customers. This this method in principle carries more business information. Let us do the heuristics for the number of characters needed. In the worst case when the customer $C_i$ has purchased all the $n$ books, $$ N_i = p_1 p_2 \ldots p_n < p_n^n. $$ (This inequality can be strengthened using the estimates of the Chevyshev function of the first kind but right now, that is not the objective as I only want to demonstrate the underlying idea). Hence the number of characters required is $$ D_i = \log_{10} N_i < n\log_{10}p_n < nd + d - 1 $$

for $p_n < 10^d$ which is a safe assumption since most of the UPC code numbers given to products sold in the market have multiple digits. Hence with a small number of books say $<100$ we expect method 2 to use lesser number of character (hence memory) to store the same information. For example if I have 10 books them to store the information about a customer who purchased all the 10 books, method one with a 2 digit code for each book will require 21 characters where as method 2 will require only 10 characters. Unfortunately when there are a large number of books, the products of primes grows very fast and we may end up requiring more memory space than in method 1. Hence this method is not scale-able.

Method 3: We can do better than method 2. Let the $k$-th book be given the number $2^{k}$. Every time a customer buys a unique book, we add its corresponding number. Since a number can be decomposed as the sum of non-repeating powers of two in only one way, we can identify the exact books purchased by the customer $C_i$ by decomposing his/her total sum $S_i$. For example if the sum of the book numbers for a customer is 154, since $154=2^7 + 2^4 + 2^3 + 2^1$, we know that the customer has purchased the first, third, fourth and the seventh book. So instead of storing the code of these four books or the product of three primes, I can just store the three digit number 154 which will give me the same information. In the worst case when the customer has purchased all the n books,

$$ S_i = 2^1 + 2^2 +\ldots + 2^n = 2^{n+1} - 2 $$

$$ D_i < \log_{10}(2^{n+1}-2) < n\log_{10}2 + 1 $$

Thus with method 3, we can store the same information using the least number of characters thus far. Also two customers will have a book in common if and only if the decomposition of their sum contains an identical power of 2.

Questions: Is there are better method of identifying the books uniquely using less than $n\log_{10}2$ characters? I think that if there is indeed a better method, it could possible be using some of the property of integers.

Answer by François G. Dorais for Mathematical techniques to reduce the amount of storage memory

2013-02-05T18:14:34Z

This is one of the basic problems that led to the field of information theory. It would take a while to explain all that is known about this, but the following will get you started.

Suppose we assign each book $b$ a binary string $\sigma_b$ such that no two strings are prefixes of each other (like telephone numbers). Then a consumer's purchases can be encoded by concatenating these strings back-to-back (without separating tokens or other marks). The total number of bits used to encode all the customer's purchases is $\sum_b n_b|\sigma_b|$, where $n_b$ is the number of times book $b$ has been purchased. We now have the optimization problem of minimizing this sum subject to the constraint that no two strings are prefixes of each other. This seemingly complex constraint actually has a simple existence criterion, namely the necessary fact that $\sum_b 2^{-|\sigma_b|} \leq 1$. So the whole thing boils down to finding $$\min \sum_b n_b \ell_b \quad\text{subject to}\quad \sum_b 2^{-\ell_b} \leq 1,$$ where $\ell_b$ is the length of the binary string used to encode the book $b$.

Generalizing a bit, we can think of $p_b = 2^{-\ell_b}$ as a probability associated to the book $b$. Translating the above becomes the problem of finding $$\max \sum_b n_b \log p_b \quad\text{subject to}\quad \sum_b p_b = 1,$$ where $p_b \in [0,1]$ are no longer restricted to being powers of $\frac12$. This continuous optimization problem has solution $p_b = n_b/n$, where $n = \sum_b n_b$ is the total number of books sold. Assuming that this solution happens to be such that the probabilities $p_b$ are all powers of $\frac12$, the total number of bits used is $$n \log_2 n - \sum_b n_b\log_2 n_b.$$ Dividing by $n$ to get the average number of bits used per book sold we get $$\log_2 n - \sum_b \frac{n_b}{n} \log_2 n_b = - \sum_b p_b \log_2 p_b.$$ This is the Shannon entropy of the distribution $p_b = n_b/n$ and this is an absolute lower bound for lossless encoding of this kind of data. Even if the probabilities are not powers of $\frac12$ encodings arbitrarily close to this bound can be achieved through arithmetic coding. In the situation you describe, it seems likely that the distribution $p_b$ is not known in advance, which is the main difficulty with achieving this optimal bound in practice.

Answer by Brendan McKay for Mathematical techniques to reduce the amount of storage memory

2013-02-06T00:09:04Z

It seems like you want to use the same number of bits for each customer. That is a big mistake and you won't find a good solution unless you drop that requirement.

What you need is an adaptive scheme that is designed according to the customer profile. Allow enough space per customer that will be enough for say 95% of customers. That should be quite a small amount per customer since most people will buy few books. The 5% big spenders are also in this store, but instead of containing a list of books it has a special code indicating it is a big spender. Then you look them up in a second store that just contains the big spenders with more space for each (probably a variety of $B$-tree that allows variable space per customer). The average total space per customer will be small.

Clearly you can tune parameters, and even have more than two levels if you want.

By the way, this is all very very standard data-base methodology.

Answer by Joel David Hamkins for Mathematical techniques to reduce the amount of storage memory

2013-02-06T00:57:53Z

The amount of space that your data need take up will depend ultimately on what that data is, and you will be able to achieve further compression depending on the actual data. For example, in the situation where no customer has bought any books at all, then you can indicate this situation in very little space, without reserving any extra unused bits for the books that were not bought. Similarly, if it happened that every customer bought every single book available, then one could indicate this in very little space, whereas it would take a lot of space in the schemes you are considering.

Ultimately, the smallest possible space describing a given set of data is known as the Kolmogorov complexity of that data, and it doesn't much matter what initial form one uses to represent the data. The Kolmogorov complexity of a data collection is an optimal degree of compression for that data, which one cannot improve by any means. That may sound great at first, but the situation is that in general, the exact Kolmogorov complexity of a given set of data is not computable in principle. Basically, one cannot generally know computably what is the smallest amount of space sufficient to represent a given data set. (One can prove this by observing that if Kolmogorov complexity were computable, then with a simple program one could search for and find the shortest string with enormous Kolmogorov complexity; a contradiction.) In this sense, the answer to your question, taken in the extreme optimal form of finding the best, smallest space to represent a given data set, is that this is not computably decidable.