TU Darmstadt / ULB / TUbiblio

Fast Indexing Strategies for Robust Image Hashes

Winter, Christian ; Steinebach, Martin ; Yannikos, York (2014)
Fast Indexing Strategies for Robust Image Hashes.
In: Digital Investigation (Elsevier), 11 (Supplement 1)
doi: 10.1016/j.diin.2014.03.004
Article, Bibliographie

Abstract

Similarity preserving hashing can aid forensic investigations by providing means to recognize known content and modified versions of known content. However, this raises the need for efficient indexing strategies which support the similarity search. We present and evaluate two indexing strategies for robust image hashes created by the ForBild tool. These strategies are based on generic indexing approaches for Hamming spaces, i.e. spaces of bit vectors equipped with the Hamming distance. Our first strategy uses a vantage point tree, and the second strategy uses locality-sensitive hashing (LSH). Although the calculation of Hamming distances is inexpensive and hence challenging for indexing strategies, we improve the speed for identifying similar items by a factor of about 30 with the tree-based index, and a factor of more than 100 with the LSH index. While the tree-based index retrieves all approximate matches, the speed of LSH is paid with a small rate of false negatives.

Item Type: Article
Erschienen: 2014
Creators: Winter, Christian ; Steinebach, Martin ; Yannikos, York
Type of entry: Bibliographie
Title: Fast Indexing Strategies for Robust Image Hashes
Language: English
Date: 2014
Journal or Publication Title: Digital Investigation (Elsevier)
Volume of the journal: 11
Issue Number: Supplement 1
Event Location: Amsterdam, Netherlands
DOI: 10.1016/j.diin.2014.03.004
Abstract:

Similarity preserving hashing can aid forensic investigations by providing means to recognize known content and modified versions of known content. However, this raises the need for efficient indexing strategies which support the similarity search. We present and evaluate two indexing strategies for robust image hashes created by the ForBild tool. These strategies are based on generic indexing approaches for Hamming spaces, i.e. spaces of bit vectors equipped with the Hamming distance. Our first strategy uses a vantage point tree, and the second strategy uses locality-sensitive hashing (LSH). Although the calculation of Hamming distances is inexpensive and hence challenging for indexing strategies, we improve the speed for identifying similar items by a factor of about 30 with the tree-based index, and a factor of more than 100 with the LSH index. While the tree-based index retrieves all approximate matches, the speed of LSH is paid with a small rate of false negatives.

Uncontrolled Keywords: Secure Data;Robust hashing, ForBild, indexing, vantage point tree, locality-sensitive hashing
Identification Number: TUD-CS-2014-0926
Divisions: LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
LOEWE > LOEWE-Zentren
LOEWE
Date Deposited: 30 Dec 2016 20:23
Last Modified: 17 May 2018 13:02
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details