Další formáty:
BibTeX
LaTeX
RIS
@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.
|