Modifying Hamming Spaces for Efficient Search

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00103668" target="_blank" >RIV/00216224:14330/18:00103668 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1109/ICDMW.2018.00137" target="_blank" >http://dx.doi.org/10.1109/ICDMW.2018.00137</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ICDMW.2018.00137" target="_blank" >10.1109/ICDMW.2018.00137</a>

Result language

angličtina

Original language name

Modifying Hamming Spaces for Efficient Search

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EF16_019%2F0000822" target="_blank" >EF16_019/0000822: CyberSecurity, CyberCrime and Critical Information Infrastructures Center of Excellence</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

18th International Conference on Data Mining Workshops (ICDMW), Singapore, November 17-21, 2018

ISBN

9781538692882

ISSN

2375-9232

e-ISSN

—

Number of pages

9

Pages from-to

945-953

Publisher name

IEEE

Place of publication

USA

Event location

Singapur

Event date

Jan 1, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000465766800128