About: Perils of Combining Parallel Distance Computations with Metric and Ptolemaic Indexing in kNN Queries

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Perils of Combining Parallel Distance Computations with Metric and Ptolemaic Indexing in kNN Queries Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://link.springer.com/chapter/10.1007/978-3-319-11988-5_12
Description	Similarity search methods face serious performance issues since similarity functions are rather expensive to compute. Many optimization techniques were designed to reduce the number of similarity computations, when a query is being resolved. Indexing methods, like pivot table prefiltering, based on the metric properties of feature space, are one of the most popular methods. They can increase the speed of query evaluation even by orders of magnitude. Another approach is to employ highly parallel architectures like GPUs to accelerate evaluation by unleashing their raw computational power. Unfortunately, resolving the k~nearest neighbors (kNN) queries optimized with metric indexing is a problem that is serial in nature. In this paper, we explore the perils of kNN parallelization and we propose a new algorithm that basically converts kNN queries into range queries, which are perfectly parallelizable. We have experimentally evaluated all approaches using a~highly parallel environment comprised of multiple GPUs. The new algorithm demonstrates more than 2x speedup to the naive parallel implementation of kNN queries. Similarity search methods face serious performance issues since similarity functions are rather expensive to compute. Many optimization techniques were designed to reduce the number of similarity computations, when a query is being resolved. Indexing methods, like pivot table prefiltering, based on the metric properties of feature space, are one of the most popular methods. They can increase the speed of query evaluation even by orders of magnitude. Another approach is to employ highly parallel architectures like GPUs to accelerate evaluation by unleashing their raw computational power. Unfortunately, resolving the k~nearest neighbors (kNN) queries optimized with metric indexing is a problem that is serial in nature. In this paper, we explore the perils of kNN parallelization and we propose a new algorithm that basically converts kNN queries into range queries, which are perfectly parallelizable. We have experimentally evaluated all approaches using a~highly parallel environment comprised of multiple GPUs. The new algorithm demonstrates more than 2x speedup to the naive parallel implementation of kNN queries. (en)
Title	Perils of Combining Parallel Distance Computations with Metric and Ptolemaic Indexing in kNN Queries Perils of Combining Parallel Distance Computations with Metric and Ptolemaic Indexing in kNN Queries (en)
skos:prefLabel	Perils of Combining Parallel Distance Computations with Metric and Ptolemaic Indexing in kNN Queries Perils of Combining Parallel Distance Computations with Metric and Ptolemaic Indexing in kNN Queries (en)
skos:notation	RIV/00216208:11320/14:10281374!RIV15-GA0-11320___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GA13-08195S), P(GP14-14292P)
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Yaghob, Jakub Kruliš, Martin
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	36186
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10281374
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	indexing; similarity search; kNN queries; GPU; parallel (en)
http://linked.open.../riv/klicoveSlovo	kNN queries similarity search indexing GPU parallel
http://linked.open...ontrolniKodProRIV	[1AAB8A8ADB2A]
http://linked.open...v/mistoKonaniAkce	Los Cabos, Mexiko
http://linked.open...i/riv/mistoVydani	Heidelberg, Germany
http://linked.open...i/riv/nazevZdroje	Similarity Search and Applications
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Vysoce škálovatelné paralelní a distribuované metody zpracování vědeckých dat Employing Modern Parallel Architectures in Specific Domains of Database Systems
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Yaghob, Jakub Kruliš, Martin Kirchhoff, Steffen
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2014-10-29 (xsd:date)
issn	0302-9743
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-319-11988-5_12
http://purl.org/ne...btex#hasPublisher	Springer-Verlag. (Berlin; Heidelberg)
https://schema.org/isbn	978-3-319-11987-8
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software