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
Artikel, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2014 |
| Autor(en): | Winter, Christian ; Steinebach, Martin ; Yannikos, York |
| Art des Eintrags: | Bibliographie |
| Titel: | Fast Indexing Strategies for Robust Image Hashes |
| Sprache: | Englisch |
| Publikationsjahr: | 2014 |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Digital Investigation (Elsevier) |
| Jahrgang/Volume einer Zeitschrift: | 11 |
| (Heft-)Nummer: | Supplement 1 |
| Veranstaltungsort: | Amsterdam, Netherlands |
| DOI: | 10.1016/j.diin.2014.03.004 |
| Kurzbeschreibung (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. |
| Freie Schlagworte: | Secure Data;Robust hashing, ForBild, indexing, vantage point tree, locality-sensitive hashing |
| ID-Nummer: | TUD-CS-2014-0926 |
| Fachbereich(e)/-gebiet(e): | LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt LOEWE > LOEWE-Zentren LOEWE |
| Hinterlegungsdatum: | 30 Dez 2016 20:23 |
| Letzte Änderung: | 17 Mai 2018 13:02 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum