title: Fast probabilistic file fingerprinting for big data.
abstract: BACKGROUND
  Biological data acquisition is raising new challenges, both in data analysis and handling. Not only is it proving hard to analyze the data at the rate it is generated today, but simply reading and transferring data files can be prohibitively slow due to their size. This primarily concerns logistics within and between data centers, but is also important for workstation users in the analysis phase. Common usage patterns, such as comparing and transferring files, are proving computationally expensive and are tying down shared resources.
  
  
  RESULTS
  We present an efficient method for calculating file uniqueness for large scientific data files, that takes less computational effort than existing techniques. This method, called Probabilistic Fast File Fingerprinting (PFFF), exploits the variation present in biological data and computes file fingerprints by sampling randomly from the file instead of reading it in full. Consequently, it has a flat performance characteristic, correlated with data variation rather than file size. We demonstrate that probabilistic fingerprinting can be as reliable as existing hashing techniques, with provably negligible risk of collisions. We measure the performance of the algorithm on a number of data storage and access technologies, identifying its strengths as well as limitations.
  
  
  CONCLUSIONS
  Probabilistic fingerprinting may significantly reduce the use of computational resources when comparing very large files. Utilisation of probabilistic fingerprinting techniques can increase the speed of common file-related workflows, both in the data center and for workbench analysis. The implementation of the algorithm is available as an open-source tool named pfff, as a command-line tool as well as a C library. The tool can be downloaded from http://biit.cs.ut.ee/pfff.
authors: Institute of Computer Science, University of Tartu, J, Liivi 2, 50409 Tartu, Estonia. Konstantin.Tretjakov@ut.ee
authors: Konstantin
authors: K
authors: Tretyakov
authors: Sven
authors: S
authors: Laur
authors: Geert
authors: G
authors: Smant
authors: Jaak
authors: J
authors: Vilo
authors: Pjotr
authors: P
authors: Prins
mesh_terms: D000465:Algorithms; D001330:Electronic Data Processing / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D012984:Software