http://www.cnr.it/ontology/cnr/individuo/prodotto/ID14379
An approximate algorithm for top-k closest pairs join query in large high dimensional data (Articolo in rivista)
- Type
- Label
- An approximate algorithm for top-k closest pairs join query in large high dimensional data (Articolo in rivista) (literal)
- Anno
- 2005-01-01T00:00:00+01:00 (literal)
- Alternative label
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Angiulli Fabrizio, Pizzuti Clara (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Note
- ISI Web of Science (WOS) (literal)
- Titolo
- An approximate algorithm for top-k closest pairs join query in large high dimensional data (literal)
- Abstract
- In this paper we present a novel approximate algorithm to
calculate the top-$k$ closest pairs join query of two large and
high dimensional data sets. The algorithm has worst case time
complexity ${\cal O}(d^2nk)$ and space complexity ${\cal O}(nd)$
and guarantees a solution within a ${\cal O}(d^{1+\frac{1}{t}})$
factor of the exact one, where $t\in\{1,2,\ldots,\infty\}$ denotes
the Minkowski metrics $L_t$ of interest and $d$ the
dimensionality. It makes use of the concept of space filling curve
to establish an order between the points of the space and performs
at most $d+1$ sorts and scans of the two data sets. During a scan,
each point from one data set is compared with its closest points,
according to the space filling curve order, in the other data set
and points whose contribution to the solution has already been
analyzed are detected and eliminated. Experimental results on real
and synthetic data sets show that our algorithm behaves as an
exact algorithm in low dimensional spaces; it is able to prune the
entire (or a considerable fraction of the) data set even for high
dimensions if certain separation conditions are satisfied; in any
case it returns a solution within a small error to the exact one.
(literal)
- Prodotto di
- Autore CNR
Incoming links:
- Prodotto
- Autore CNR di
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
