Speeding up Continuous kNN Join by Binary Sketches

D 2018

Speeding up Continuous kNN Join by Binary Sketches

NÁLEPA, Filip, Michal BATKO a Pavel ZEZULA

Základní údaje

Originální název

Speeding up Continuous kNN Join by Binary Sketches

Autoři

NÁLEPA, Filip (203 Česká republika, garant, domácí), Michal BATKO (203 Česká republika, domácí) a Pavel ZEZULA (203 Česká republika, domácí)

Vydání

Cham, Advances in Data Mining, od s. 183-198, 16 s. 2018

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/18:00100950

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-95785-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-95786-9_14

UT WoS

000469337800014

Klíčová slova anglicky

continuous kNN similarity join; binary sketches

Štítky

DISA

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 13. 5. 2020 19:24, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Real-time recommendation is a necessary component of current social applications. It is responsible for suggesting relevant newly published data to the users based on their preferences. By representing the users and the published data in a metric space, each user can be recommended with their k nearest neighbors among the published data, i.e., the kNN join is computed. In this work, we aim at a frequent requirement that only the recently published data are subject of the recommendation, thus a sliding time window is defined and only the data published within the limits of the window can be recommended. Due to large amounts of both the users and the published data, it becomes a challenging task to continuously update the results of the kNN join as new data come into and go out of the sliding window. We propose a binary sketch-based approximation technique suited especially to cases when the metric distance computation is an expensive operation (e.g., the Euclidean distance in high dimensional vector spaces). It applies cheap Hamming distances to skip over 90% of the expensive metric distance computations. As revealed by our experiments on 4,096 dimensional vectors, the proposed approach significantly outperforms compared existing approaches.

Návaznosti

GA16-18889S, projekt VaV

Název: Analytika pro velká nestrukturovaná data (Akronym: Big Data Analytics for Unstructured Data)

Investor: Grantová agentura ČR, Big Data Analytics for Unstructured Data

Citovat

NÁLEPA, Filip, Michal BATKO a Pavel ZEZULA. Speeding up Continuous kNN Join by Binary Sketches. Online. In Petra Perner. Advances in Data Mining. Cham: Springer, 2018, s. 183-198. ISBN 978-3-319-95785-2. Dostupné z: https://dx.doi.org/10.1007/978-3-319-95786-9_14.

@inproceedings{1418218,
   author = {Nálepa, Filip and Batko, Michal and Zezula, Pavel},
   address = {Cham},
   booktitle = {Advances in Data Mining},
   doi = {http://dx.doi.org/10.1007/978-3-319-95786-9_14},
   editor = {Petra Perner},
   keywords = {continuous kNN similarity join; binary sketches},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-319-95785-2},
   pages = {183-198},
   publisher = {Springer},
   title = {Speeding up Continuous kNN Join by Binary Sketches},
   year = {2018}
}

TY  - JOUR
ID  - 1418218
AU  - Nálepa, Filip - Batko, Michal - Zezula, Pavel
PY  - 2018
TI  - Speeding up Continuous kNN Join by Binary Sketches
PB  - Springer
CY  - Cham
SN  - 9783319957852
KW  - continuous kNN similarity join
KW  - binary sketches
N2  - Real-time recommendation is a necessary component of current social applications. It is responsible for suggesting relevant newly published data to the users based on their preferences. By representing the users and the published data in a metric space, each user can be recommended with their k nearest neighbors among the published data, i.e., the kNN join is computed. In this work, we aim at a frequent requirement that only the recently published data are subject of the recommendation, thus a sliding time window is defined and only the data published within the limits of the window can be recommended. Due to large amounts of both the users and the published data, it becomes a challenging task to continuously update the results of the kNN join as new data come into and go out of the sliding window. We propose a binary sketch-based approximation technique suited especially to cases when the metric distance computation is an expensive operation (e.g., the Euclidean distance in high dimensional vector spaces). It applies cheap Hamming distances to skip over 90% of the expensive metric distance computations. As revealed by our experiments on 4,096 dimensional vectors, the proposed approach significantly outperforms compared existing approaches.
ER  -

NÁLEPA, Filip, Michal BATKO a Pavel ZEZULA. Speeding up Continuous kNN Join by Binary Sketches. Online. In Petra Perner. \textit{Advances in Data Mining}. Cham: Springer, 2018, s.~183-198. ISBN~978-3-319-95785-2. Dostupné z: https://dx.doi.org/10.1007/978-3-319-95786-9\_{}14.

Podrobný výpis o publikaci