вторник, 24 июля 2012 г.

Простой прием для рандомизации результатов поиска

В последнее время прочитал в сети несколько статей (например эту) где эффективное и элегантное решение достигалось с небольшой помощью теории вероятностей.
Я попытался вспомнить использовал ли я когда нибудь ее для решения своих задач. И да, нашлась одна о которой хотелось бы рассказать.

Допустим, вы пишете сервис знакомств и хотите чтобы результаты поиска основной функции "найди мне вторую половинку" выдавали каждый раз новые результаты. Это естественное требования для сервиса такого рода. Например, мужчина ищет женщину, задает параметры поиска, смотрит на первую страницу результатов, если ему не нравится, листает дальше. В дальнейшем, при последующих заходах на сайт, тоже было бы очень неплохо выдавать ему разные результаты при том же самом запросе.

Это не такая уж большая проблема если у вас есть некое подобие сессии и вы сохраняете метки записей которые были ему показаны и ваша система не очень крупная. С увеличением нагрузки ситуация осложняется - вы уже не можете хранить в сессии такое количество данных или доставать их из какого то хранилища для каждого запроса и\или число запросов становится очень большим и скорость обработки запроса будет уменьшатся и\или каждый посетитель может менять параметры запроса и\иди данные поиска могут меняться и нужно их как-то синхронизовывать - при любых комбинациях этих факторов хранение показанных результатов и их обработка становится головной болью и может резко снизить производительность системы. К тому же, такой подход подразумевает много дополнительного кода.
Почему просто не хранить номер просмотренной страницы? Данные могут храниться в каком то упорядоченном виде (например отсортированными по алфавиту), а нам желательно делать выборку со всего набора.


Формально, мою задачу можно сформулировать следующим образом (это был не сервис знакомств):
Есть большое кол-во данных по которым производится поиск. Поиск производится по нескольким критериям. Эти критерии в общем случае меняются от запроса к запросу. Ранжирование не нужно. Обычное число результатов на каждый вызов - от сотен до десятков тысяч. Результаты должны быть представлены небольшими порциями по 20-50 штук. Полное число данных известно. Непосредственный поиск осуществлялся при помощи Lucene, на каждый подходящий результат из индекса вызывался наш слушатель с передачей ему идентификатора документа.

Основной идеей было произвольно подменять результаты в конечном списке после его предварительно заполнения первыми подходящими данными.
Пусть N - полное число данных (документов);
n - число записей удовлетворяющих параметрам поиска;
h  - размер "выходного" списка данных - 20-50 штук.

Тогда вероятность каждой записи из множества  n подходящих кандидатов быть представленными в конечно списке есть h/n (h<n). Если бы мы знали n для каждого запроса то можно было бы решить задачу так:
1. Заполнить результирующий список первыми h кандидатами.
2. С каждым новым кандидатом заменить с вероятностью h/n один из h результатов в списке  (Как выбрать конкретный элемент для замены обсуждается ниже).

К сожалению, мы не знаем n в процессе поиска. Можно посчитать это число только после того как поисковая машина пробежалась по всему индексу. Возможное решение - запускать поиск два раза - первый раз для подсчета числа n. Но запускать поиск дважды это слишком дорогое удовольствие с точки зрения нагрузки на систему.
Я "пошел другим путем" - число n можно оценивать динамически по текущей статистике результатов. Если мы пробежались по D (из N) записей и имеем d кандидатов то оцениваем n из простой пропорции d/D ~ n/N. n~d*N/D. То есть n динамически меняется во время процесса.
Вероятность каждого нового кандидата быть представленным в конечном списке есть h/n=h*D/(d*N). Если кандидаты начинают попадаться более часто в индексе то оценочное значение n растет быстрее и мы более часто подменяем результаты и наоборот.

Все эти расчеты, конечно, работают идеально только для равномерно распределенных по индексу кандидатах. Если распределение очень неравномерное то и вероятность также будет не идеальной. Для сервиса знакомств это означает что для некоторых людей вероятность оказаться в результатах поиска будет выше/ниже чем у других. Но ошибка в вычислении вероятности велика только поначалу, когда мы прошли лишь небольшую часть индекса. Чем больше мы продвигаемся вперед и накапливаем статистику тем лучше становится оценка n. На практике распределение данных оказалось достаточно хорошим для использования этого метода.

Другой резонный вопрос в этом подходе - как выбрать элемент для замены в конечном списке.
Первая, наивная мысль была выбрать этот элемент произвольным образом генерируя число из диапазона [0, h-1]. Но в этом случае каждый элемент может быть заменен несколько раз, а другие, с большой долью вероятности не заменены ни разу, так как количество замен в среднем это n*h/n=h. Это противоречит всем предыдущим предположениям о вероятностях.
Фактически, если сделать именно так, то подозрительно большая часть в конечном результате будут из первых h результатов.
Хорошим решением данной проблемы оказалось выбирать произвольное число из диапазона [0, h-1] без повторения. В этом случае каждый кандидат будет иметь равные шансы быть замененным. Что если мы уже выбрали все индексы из этого диапазона? Тогда просто начинаем выбирать сначала - это не нарушит нашу логику так как среднее число замен n*h/n=h.

Как выбирать произвольные числа из набора без повторения [0, h-1]? Это одна из широко известных задач с собеседований в компании типа Google и их решение можно легко найти в сети.


понедельник, 23 июля 2012 г.

Simple technique for randomizing search results



 There have been some posts recently (like this one) where efficient and elegant solution is possible with a bit of help from probabilistic theory.
I tried to remember if I ever used it for solving tasks I faced with. Here is the one I'd like to tell you about.


Suppose you are writing the dating service and want different persons to be shown for subsequent calls of you main function - 'search for partners that suits me best'.

Imagine a man who looks for a girl and dislikes the ones presented on the first page. Then he scrolls to another chunk of data service provides. He can also launch this function on visiting the service next time.
There is a sence to present different results to him each time.

It is certainly not a big challenge when you have some kind of a session and can keep track of people shown and you system is not very large. As the system grows you can't afford for a number of reasons to store large amount of data per each request/person and|or the number of searching people is huge and processing time is important (records should be fetched from some permanent storage) and|or the search criteria can be changed by users then recording search items shown for each particular user can have a dramatic impact on performance. Tracking implies a lot of coding also.
Why not just keep the latest page number clicked by a user? Tha data in our storage system can be in some arranged form (as it was in my case), for example sorted by a second name, but we need samples from the entire set.

Formally, my task was the following:
There is a huge amount of data to search for. The search is performed with a set of criteria to match. This criteria are generally different for each call. No need for ranging the results. The ususal number of results per each call is hundreds to tens of thousands. The resulted items to be presented in chunks of a size of 20-50. The total number of items is known. The search process was performed by Lucene library with the custom results collector/listener - upon each matching criteria document its id was passed to that custom listener.


The main idea was to randomly substitute the items after filling in the needed 20-50 chunk with the first results.
Let N be total number of data items;
n - is a number of items which match search citeria;
h  - is a chunk size.
Then the probability of each item from n-matching set to be in the result chunk is h/n (h<n). If n were known it would be possible to solve the task in the following way:
1. Fill the result set with first h results.
2. Upon each new match replace one of h-results with probability of h/n (How to choose which element to subsitute is described later).

Unfortunately, we don't know the number n while searching. It is only known after search engine has walked over the entire index. One possible solution is to walk two times - the first walk is to calc n number. But having two index passes might be too expensive solution from performance point of view.
Another solution I developed was to estimate n based on the current rate of results.
If the engine has walked over D (out of N) items and there are d matches one can estimate n from a simple proportion d/D ~ n/N. n~d*N/D.
So n is dynamically changing over the search process. The probability of each new match to be presented in the resulted chunk is h/n=h*D/(d*N). If the matching data start to be densely located in the index - the estimated number of total results rises quickly and it tends to replace the items in the result chunk more often and vice versa.
This certainly works best for uniformly distributed data. If the data distribution in an index is very skew the probability of appearing in the result chunk for some items will also be skewed. For dating service it means some persons will have higher probabilty to be presented than the others.
The error of probabilty estimation will be higher for initial part of the index. The more we move to the end of the index the less the estimation error.  In practice, the data distribution appeared to be good enough to follow this way.
Another question is how to choose the item to substitute from the filled list of results.
The first, naive thought, was to choose index of element for replacement by generating uniformly distributed value from 0 to h each time replacement is needed.
In this case some items may be replaced multiple times and this contradicts to the estimation of probability to be in the list =n/N. In fact, if you do this the wrongly great part of the results will be from the first h matches.
The possible silution is to pick random value from [0, h-1] values without repetition. In this case each item will have equal probability to be replaced. If it runs out of index values for replacement - just start again as this won't harm the logic - the average number of replaces is n*h/n=h.
How to pick random value from [0, h-1] values without repetition? This is one of well-known "Google interview"-like questions and one can easily find how to solve it.