This paper reports on recent findings regarding diversity queries over objects embedded in a low-dimensional vector space. Among the many contexts of interest, we mention spatial Web objects, which are abundant in location-based services that let users attach content to places. Typical queries aim at retrieving the best set of relevant objects that are well distributed over a region of interest. Existing methods for answering diversified top-k queries are too costly, as they evaluate diversity by accessing and scanning all relevant objects, even if only a small subset thereof is needed. Our proposal, named SPP, is an algorithm that, while finding exactly the same result as MMR (one of the most popular diversification algorithms), does not require retrieving all the relevant objects and, indeed, minimizes the number of accessed objects. Experiments confirm that SPP saves a significant amount of accesses while incurring a very low computational over- head.

Efficient Diversification of Top-k Queries over Bounded Regions

FRATERNALI, PIERO;MARTINENGHI, DAVIDE;TAGLIASACCHI, MARCO
2012-01-01

Abstract

This paper reports on recent findings regarding diversity queries over objects embedded in a low-dimensional vector space. Among the many contexts of interest, we mention spatial Web objects, which are abundant in location-based services that let users attach content to places. Typical queries aim at retrieving the best set of relevant objects that are well distributed over a region of interest. Existing methods for answering diversified top-k queries are too costly, as they evaluate diversity by accessing and scanning all relevant objects, even if only a small subset thereof is needed. Our proposal, named SPP, is an algorithm that, while finding exactly the same result as MMR (one of the most popular diversification algorithms), does not require retrieving all the relevant objects and, indeed, minimizes the number of accessed objects. Experiments confirm that SPP saves a significant amount of accesses while incurring a very low computational over- head.
2012
SEBD 2012
9788896477236
File in questo prodotto:
File Dimensione Formato  
SEBD2012-fraternali-p139.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 1.1 MB
Formato Adobe PDF
1.1 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/667528
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact