Top-k bounded diversification

Top-k bounded diversification

Valerio Panzica La Manna
DEI PhD Student

DEI - PT1 Room
November 15th, 2011
2 pm


This research investigates diversity queries over objects embedded in a low-dimensional vector space. An interesting case is provided by geo-referenced Web objects, which are produced in great quantity by location-based services that let users attach content to places, and arise also in trip planning, news analysis, and real estate scenarios. The targeted queries aim at retrieving the best set of objects relevant to given user criteria and well distributed over a region of interest. Such queries are a particular case of diversified top-k queries, for which existing methods are too costly, as they evaluate diversity by accessing and scanning all relevant objects, even if only a small subset is needed. The Space Partitioning and Probing (SPP) algorithm has been proposed to reduce the number of fetched objects by producing the same result as MMR, the most popular diversification algorithm. Three variants of SPP are proposed, analyzed, and compared with respect to the original version. Their effectiveness is therefore evaluated both with synthetic and real data sets.

Research area:
Advanced software architectures and methodologies