Other formats:
BibTeX
LaTeX
RIS
@inproceedings{33519,
author = {Míč, Vladimír and Novák, David and Zezula, Pavel},
address = {USA},
booktitle = {18th International Conference on Data Mining Workshops (ICDMW), Singapore, November 17-21, 2018},
keywords = {Similarity search;Hamming space;Hamming Weight Tree; Lower bound inthe Hamming space},
howpublished = {tištěná verze "print"},
language = {eng},
location = {USA},
isbn = {978-1-5386-9288-2},
pages = {945-953},
publisher = {IEEE},
title = {Modifying Hamming Spaces for Efficient Search},
year = {2018}
}
TY - JOUR
ID - 33519
AU - Míč, Vladimír - Novák, David - Zezula, Pavel
PY - 2018
TI - Modifying Hamming Spaces for Efficient Search
PB - IEEE
CY - USA
SN - 9781538692882
KW - Similarity search;Hamming space;Hamming Weight Tree
KW - Lower bound inthe Hamming space
N2 - We focus on the efficient search for the most similar bit strings to a given query in the Hamming space. The distance of this space can be lower-bounded by a function based on a difference of the number of ones in the compared strings, i.e. their weights. Recently, such property has been successfully used by the Hamming Weight Tree (HWT) indexing structure. We propose modifications of the bit strings that preserve pairwise Hamming distances but improve the tightness of these lower bounds, so the query evaluation with the HWT is several times faster. We also show that the unbalanced bit strings, recently reported to provide similar quality of search as the traditionally used balanced bit strings, are more easy to index with the HWT. Combined with the distance preserving modifications, the HWT query evaluation can be more than one order of magnitude faster than the HWT baseline. Finally, we show that such modifications are useful even for a very complex data where the search with the HWT is slower than a sequential search.
ER -
MÍČ, Vladimír, David NOVÁK and Pavel ZEZULA. Modifying Hamming Spaces for Efficient Search. In \textit{18th International Conference on Data Mining Workshops (ICDMW), Singapore, November 17-21, 2018}. USA: IEEE, 2018, p.~945-953. ISBN~978-1-5386-9288-2.
|
