TU Darmstadt / ULB / TUbiblio

Fast Indexing Strategies for Robust Image Hashes

Winter, Christian and Steinebach, Martin and Yannikos, York (2014):
Fast Indexing Strategies for Robust Image Hashes.
11, In: Digital Investigation (Elsevier), (Supplement 1), pp. S27–S35, DOI: 10.1016/j.diin.2014.03.004,
[Article]

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 and Steinebach, Martin and Yannikos, York
Title: Fast Indexing Strategies for Robust Image Hashes
Language: ["languages_typename_1" not defined]
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.

Journal or Publication Title: Digital Investigation (Elsevier)
Volume: 11
Number: Supplement 1
Uncontrolled Keywords: Secure Data;Robust hashing, ForBild, indexing, vantage point tree, locality-sensitive hashing
Divisions: LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
LOEWE > LOEWE-Zentren
LOEWE
Event Location: Amsterdam, Netherlands
Date Deposited: 30 Dec 2016 20:23
DOI: 10.1016/j.diin.2014.03.004
Identification Number: TUD-CS-2014-0926
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)

View Item View Item