BM-index: Balanced Metric Space Index based on Weighted Voronoi
Partitioning

D 2019

BM-index: Balanced Metric Space Index based on Weighted Voronoi Partitioning

ANTOL, Matej a Vlastislav DOHNAL

Základní údaje

Originální název

BM-index: Balanced Metric Space Index based on Weighted Voronoi Partitioning

Autoři

ANTOL, Matej (703 Slovensko, domácí) a Vlastislav DOHNAL (203 Česká republika, garant, domácí)

Vydání

LNCS 11695. Cham, Advances in Databases and Information Systems, 23th East European Conference, ADBIS 2019, od s. 337-353, 17 s. 2019

Nakladatel

Springer International Publishing

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00109747

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-28729-0

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-28730-6_21

UT WoS

000558104700024

Klíčová slova anglicky

Indexing structure;k-nearest neighbor query;Approximate search;Metric space;Voronoi partitioning

Štítky

core_B, DISA, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 30. 9. 2020 12:42, doc. RNDr. Vlastislav Dohnal, Ph.D.

Anotace

V originále

Processing large volumes of various data needs index structures that can efficiently organize them on secondary memory. Methods based on so-called pivot permutations have become popular in addressing these requirements because of their tremendous querying performance. They localize data objects by ordering preselected anchor objects by their distances to the data objects, and so no coordinate system is exploited to partition the data. This represents a generic solution for unstructured and high-dimensional data. In principle, pivot permutations implement recursive Voronoi tessellation. Also, due to the fixed preselected anchors, such partitioning cannot adapt to the data distribution and leads to very unbalanced cells. In this paper, we address this issue and propose a novel schema called BM-index. It exploits weighted Voronoi partitioning to create pivot permutations that adapt to data distribution. Secondary memory is then accessed efficiently with respect to the existing disk-oriented structures, such as M-index. We present an algorithm to balance the data partitions, and we show its correctness. In experiments on a real-life image collection CoPhIR, we show superior performance in I/O costs when evaluating k-nearest neighbors queries.

Návaznosti

EF16_019/0000822, projekt VaV

Název: Centrum excelence pro kyberkriminalitu, kyberbezpečnost a ochranu kritických informačních infrastruktur

MUNI/A/1411/2019, interní kód MU

Název: Aplikovaný výzkum: softwarové architektury kritických infrastruktur, bezpečnost počítačových systémů, zpracování přirozeného jazyka a jazykové inženýrství, vizualizaci velkých dat a rozšířená realita.

Investor: Masarykova univerzita, Aplikovaný výzkum: softwarové architektury kritických infrastruktur, bezpečnost počítačových systémů, zpracování přirozeného jazyka a jazykové inženýrství, vizualizaci velkých dat a rozšířená realita., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

ANTOL, Matej a Vlastislav DOHNAL. BM-index: Balanced Metric Space Index based on Weighted Voronoi Partitioning. In Lecture Notes in Computer Science. Advances in Databases and Information Systems, 23th East European Conference, ADBIS 2019. LNCS 11695. Cham: Springer International Publishing, 2019, s. 337-353. ISBN 978-3-030-28729-0. Dostupné z: https://dx.doi.org/10.1007/978-3-030-28730-6_21.

@inproceedings{1534362,
   author = {Antol, Matej and Dohnal, Vlastislav},
   address = {Cham},
   booktitle = {Advances in Databases and Information Systems, 23th East European Conference, ADBIS 2019},
   doi = {http://dx.doi.org/10.1007/978-3-030-28730-6_21},
   edition = {LNCS 11695},
   editor = {Lecture Notes in Computer Science},
   keywords = {Indexing structure;k-nearest neighbor query;Approximate search;Metric space;Voronoi partitioning},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-030-28729-0},
   pages = {337-353},
   publisher = {Springer International Publishing},
   title = {BM-index: Balanced Metric Space Index based on Weighted Voronoi Partitioning},
   url = {https://link.springer.com/chapter/10.1007/978-3-030-28730-6_21},
   year = {2019}
}

TY  - JOUR
ID  - 1534362
AU  - Antol, Matej - Dohnal, Vlastislav
PY  - 2019
TI  - BM-index: Balanced Metric Space Index based on Weighted Voronoi Partitioning
PB  - Springer International Publishing
CY  - Cham
SN  - 9783030287290
KW  - Indexing structure;k-nearest neighbor query;Approximate search;Metric space;Voronoi partitioning
UR  - https://link.springer.com/chapter/10.1007/978-3-030-28730-6_21
L2  - https://link.springer.com/chapter/10.1007/978-3-030-28730-6_21
N2  - Processing large volumes of various data needs index structures that can efficiently organize them on secondary memory. Methods based on so-called pivot permutations have become popular in addressing these requirements because of their tremendous querying performance. They localize data objects by ordering preselected anchor objects by their distances to the data objects, and so no coordinate system is exploited to partition the data. This represents a generic solution for unstructured and high-dimensional data. In principle, pivot permutations implement recursive Voronoi tessellation. Also, due to the fixed preselected anchors, such partitioning cannot adapt to the data distribution and leads to very unbalanced cells. In this paper, we address this issue and propose a novel schema called BM-index. It exploits weighted Voronoi partitioning to create pivot permutations that adapt to data distribution. Secondary memory is then accessed efficiently with respect to the existing disk-oriented structures, such as M-index. We present an algorithm to balance the data partitions, and we show its correctness. In experiments on a real-life image collection CoPhIR, we show superior performance in I/O costs when evaluating k-nearest neighbors queries.
ER  -

ANTOL, Matej a Vlastislav DOHNAL. BM-index: Balanced Metric Space Index based on Weighted Voronoi Partitioning. In Lecture Notes in Computer Science. \textit{Advances in Databases and Information Systems, 23th East European Conference, ADBIS 2019}. LNCS 11695. Cham: Springer International Publishing, 2019, s.~337-353. ISBN~978-3-030-28729-0. Dostupné z: https://dx.doi.org/10.1007/978-3-030-28730-6\_{}21.

Podrobný výpis o publikaci