Цель проекта - разработать архитектуру и написать прототип среды для коммуникации между бизнесами и потребителями.

Подробнее о проекте

Similarity search is the problem of preprocessing a database of N objects
in such a way that given a query object, one can effectively determine its
nearest neighbors in database.

Similarity search is closely connected to many algorithmic
problems in the web: In this talk we will focus on:
- Personalized news aggregation: Searching for news articles
that are most similar to the user's profile of interests
- Behavioral targeting: Searching for the most relevant
advertisement for displaying to a given user.
- Social network analysis: Suggesting new friends.
- Computing co-occurrence similarities.
- "Best match search": Searching resumes, jobs, BF/GF,
cars, apartments


We describe features that make web applications somewhat different
from previously studied models. Thus we re-examine the formalization and
the classical algorithms for similarity search. This leads us to new algorithms
(we present two of them) and numerous open problems in the field.

Соответствующие слайды

We contribute to combinatorics and algorithmics of words
by introducing new types of periodicities in words. A tiling period of a
word w is partial word u such that w can be decomposed into several
disjoint parallel copies of u, e.g. a_b is a tiling period of aabb. We investigate
properties of tiling periodicities and design an algorithm working
in O(n log(n) log log(n)) time which nds a tiling period of minimal size,
the number of such periods and their compact representation. The combinatorics
of tiling periods differs significantly from that for classical full
periods, for example unlike the classical case the same word can have
many different primitive tiling periods. We consider also a related new
type of periods called in the paper multi-periods. As a side product of
the paper we solve an open problem posted by T. Harju.

The paper and slides are available at Homepage of Yury Lifshits

What kind of operations can we perform effectively (without
full unpacking) with compressed texts? In this paper we consider three
fundamental problems: (1) check the equality of two compressed texts,
(2) check whether one compressed text is a substring of another compressed
text, and (3) compute the number of different symbols (Hamming
distance) between two compressed texts of the same length.
We present an algorithm that solves the first problem in O(n^3) time and
the second problem in O(n^2m) time. Here n is the size of compressed
representation (we consider representations by straight-line programs) of
the text and m is the size of compressed representation of the pattern.
Next, we prove that the third problem is actually #P-complete. Thus,
we indicate a pair of similar problems (equivalence checking, Hamming
distance computation) that have radically different complexity on compressed
texts. Our algorithmic technique used for problems (1) and (2)
helps for computing minimal periods and covers of compressed texts.

The paper and slides are available at Homepage of Yury Lifshits

Yury Lifshits. Algorithms for Nearest Neighbors Search.

Nearest neighbors problem is formulated as follows: Given a set S
of points in some space V (equipped with similarity function),
construct a data structure which given any query point q from V
finds the closest point in S to q. This kind of search problems
arise in many areas: pattern recognition, recommendation systems,
text classification, data compression, coding theory, computational
statistics.

In the first part we consider key algorithms for this problem.
In particular, we discuss (1) black-box model: search space is represented
by oracle that returns a similarity value for any pair of points;
and (2) vector model: all points belong to high-dimesional euclidian
space. In the second part we survey results in theoretical
analysis of algorithms for nearest neighbors. We discuss the best known
results for worst case complexity, average case complexity as well
as known lower bounds.

Slides are available at Homepage of Yury Lifshits

In this paper, we consider the decidability of two problems related to
information flow in a system with respect to some property. A flow occurs in a
system if the conditional probability of the property under some partial observation
differs from the a priori probability of that property. For systems modelled
as finite Markov chains we prove that the two following problems are decidable:
does a system has information flow for a given regular property? is it true that the
system has no information flow for any (sequential) property?

The paper and slides are available at Homepage of Yury Lifshits

How could one estimate the total number of clicks a new advertisement
could potentially receive in the current market? This question,
called the click volume estimation problem is investigated in this
paper. This constitutes a new research direction for advertising engines.
We propose a model of computing an estimation of the click volume.
A key component of our solution is the application of linear regression
to a large (but sparse) data set. We propose an iterative method in order
to achieve a fast approximation of the solution. We prove that our
algorithm always converges to optimal parameters of linear regression.
To the best of our knowledge, it is the first time when linear regression
is considered in such a large scale context.

The paper and slides are available at Homepage of Yury Lifshits

Джон Клейнберг получил премию Неванлинны (аналог медали Филдса в теоретической информатике) в 2006 году на Международном математическом конгрессе в Мадриде. В официальном пресс-релизе указано четыре наиболее существенные группы его результатов:

1. Алгоритмы поиска ближайших соседей. Клейнберг предложил новый способ предварительной обработки семейства точек в евклидовом пространстве, позволяющей по новой точке быстро находить ближайшую точку в базе. Впервые удалось построить метод, который доказуемо быстрее, чем полный перебор.

2. Способ определения авторитетности интернет-страниц. Метод, предложенный Клейнбергом основан на вычислении собственного вектора матрицы, описывающей структуру ссылок в вебе. На этих идеях основан алгоритм PageRank, сделавший Google лучшей системой интернет-поиска.

3. Математические модели эффекта "как тесен мир". Джон Клейнберг предложил интересную модель социальной сети с параметром, характеризующим способ создания связей в сети. Ему удалось обнаружить необычное свойство этой модели: существует единственное значение параметра, при котором есть эффективный способ быстро передать сообщение до любого адресата "по цепочке знакомых".

4. Математическая модель "информационных всплесков". В этой работе рассматривается поток некторых информационных сообщений (например, научные статьи, e-mail'ы, новости). Всплеском (burst) называется интервал времени, в который определенное ключевое слово встречается чаще обычного. Клейнберг предложил способ перечислить все всплески, отсортировать их по "весу" и построить их иерархию.

Слайды, слайды для печати.

Абстрактно, задачу о ближайших соседях можно сформулировать
следующим образом. Есть некоторое пространство с метрикой близости.
Нам дана большая коллекция элементов этого пространства. Требуется
провести такие предварительные вычисления, чтобы при получении
нового элемента как можно быстрее определить его ближайшего
соседа в нашей коллекции. Алгоритмы поиска ближайших соседей играют
важнейшую роль в классификации текстов, распознавании образов,
рекомендующих системах и системах размещения интернет-рекламы.

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

Слайды, слайды для печати.

According to World Wide Web Consortium, "The Semantic Web is an evolving extension of the World Wide Web in which web content can be expressed not only in natural language, but also in a form that can be understood, interpreted and used by software agents, thus permitting them to find, share and integrate information more easily."

The first step towards Semantic Web was to develop a machine-understandable standard for describing content. This was done by introducing RDF language. But the second step, namely, construction of algorithms for performing "semantic" search in RDF data is just starting now.

In this talk we describe the current achievements in the field and pose algorithmic problems that ultimately related to semantic search.


A Guide to Web Research