{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:27:48Z","timestamp":1750307268147,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,6,1]],"date-time":"2011-06-01T00:00:00Z","timestamp":1306886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P2-0246"],"award-info":[{"award-number":["P2-0246"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>This article presents a new Fast Hash-based File Existence Checking (FHFEC) method for archiving systems. During the archiving process, there are many submissions which are actually unchanged files that do not need to be re-archived. In this system, instead of comparing the entire files, only digests of the files are compared. Strong cryptographic hash functions with a low probability of collision can be used as digests. We propose a fast algorithm to check if a certain hash, that is, a corresponding file, is already stored in the system. The algorithm is based on dividing the whole domain of hashes into equally sized regions, and on the existence of a pointer array, which has exactly one pointer for each region. Each pointer points to the location of the first stored hash from the corresponding region and has a null value if no hash from that region exists. The entire structure can be stored in random access memory or, alternatively, on a dedicated hard disk. A statistical performance analysis has been performed that shows that in certain cases FHFEC performs nearly optimally. Extensive simulations have confirmed these analytical results. The performance of FHFEC has been compared to the performance of a binary search (BIS) and B+tree, which are commonly used in file systems and databases for table indices. The results show that FHFEC significantly outperforms both of them.<\/jats:p>","DOI":"10.1145\/1970343.1970345","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T17:31:10Z","timestamp":1309282270000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast file existence checking in archiving systems"],"prefix":"10.1145","volume":"7","author":[{"given":"Saso","family":"Tomazic","sequence":"first","affiliation":[{"name":"University of Ljubljana, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vesna","family":"Pavlovic","sequence":"additional","affiliation":[{"name":"University of Belgrade, Beograd, Serbia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jasna","family":"Milovanovic","sequence":"additional","affiliation":[{"name":"University of Belgrade, Beograd, Serbia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaka","family":"Sodnik","sequence":"additional","affiliation":[{"name":"University of Ljubljana, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anton","family":"Kos","sequence":"additional","affiliation":[{"name":"University of Ljubljana, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sara","family":"Stancin","sequence":"additional","affiliation":[{"name":"University of Ljubljana, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veljko","family":"Milutinovic","sequence":"additional","affiliation":[{"name":"IPSI Belgrade"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_2_1","unstructured":"Bingmann T. 2010a. Speed test results. http:\/\/idlebox.net\/2007\/stx-btree\/stx-btree-0.8-doxygen\/speedtest.html.  Bingmann T. 2010a. Speed test results. http:\/\/idlebox.net\/2007\/stx-btree\/stx-btree-0.8-doxygen\/speedtest.html."},{"key":"e_1_2_1_3_1","unstructured":"Bingmann T. 2010b. Stx b+ tree c++ template classes. http:\/\/idlebox.net\/2007\/stx-btree\/.  Bingmann T. 2010b. Stx b+ tree c++ template classes. http:\/\/idlebox.net\/2007\/stx-btree\/."},{"key":"e_1_2_1_4_1","unstructured":"Bohn R. etal 2008. How much information&quest; At the global information industry center. http:\/\/hmi.ucsd.edu\/howmuchinfo.php.  Bohn R. et al. 2008. How much information&quest; At the global information industry center. http:\/\/hmi.ucsd.edu\/howmuchinfo.php."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Broder A. Z. 1993. Some Applications of Rabin's Fingerprinting Method Sequences II: In Methods in Communications Security and Computer Science Springer-Verlag.  Broder A. Z. 1993. Some Applications of Rabin's Fingerprinting Method Sequences II: In Methods in Communications Security and Computer Science Springer-Verlag.","DOI":"10.1007\/978-1-4613-9323-8_11"},{"key":"e_1_2_1_6_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill."},{"key":"e_1_2_1_7_1","unstructured":"Corwin E. M. 2010. Average case of binary search. http:\/\/www.mcs.sdsmt.edu\/ecorwin\/cs251\/binavg\/binavg.htm.  Corwin E. M. 2010. Average case of binary search. http:\/\/www.mcs.sdsmt.edu\/ecorwin\/cs251\/binavg\/binavg.htm."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844155"},{"key":"e_1_2_1_9_1","unstructured":"FIPS 180-2 2002. Secure hash standard. National Institute of Standards and Technology.  FIPS 180-2 2002. Secure hash standard. National Institute of Standards and Technology."},{"key":"e_1_2_1_10_1","unstructured":"IBM 2010. Grouping hash implementation. http:\/\/publib.boulder.ibm.com\/infocenter\/iseries\/v5r3\/index.jsp?topic=\/rzajq\/groupopt.htm.  IBM 2010. Grouping hash implementation. http:\/\/publib.boulder.ibm.com\/infocenter\/iseries\/v5r3\/index.jsp?topic=\/rzajq\/groupopt.htm."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1032623"},{"edition":"3","volume-title":"Sorting and Searching","author":"Knuth D.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the USENIX Technical Conference.","author":"Kulkarni P.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Lyman P. Varian H. R. Swearingen K. Chanles P. Good N. Jorvan L. L. and Pal J. 2003. How much information&quest; 2003. http:\/\/www2.sims.berkeley.edu\/research\/projects\/how-much-info-2003.  Lyman P. Varian H. R. Swearingen K. Chanles P. Good N. Jorvan L. L. and Pal J. 2003. How much information&quest; 2003. http:\/\/www2.sims.berkeley.edu\/research\/projects\/how-much-info-2003."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502052"},{"key":"e_1_2_1_16_1","unstructured":"Papoulis A. 1984. Probability Random Variables and Stochastic Processes 2nd Ed. McGraw-Hill.  Papoulis A. 1984. Probability Random Variables and Stochastic Processes 2nd Ed. McGraw-Hill."},{"key":"e_1_2_1_17_1","unstructured":"Parlante N. 2001. Linked List Basics. Stanford University.  Parlante N. 2001. Linked List Basics. Stanford University."},{"key":"e_1_2_1_18_1","unstructured":"PCGuide 2010. Logical block addressing (LBA). http:\/\/www.pcguide.com\/ref\/hdd\/bios\/modesLBA-c.html.  PCGuide 2010. Logical block addressing (LBA). http:\/\/www.pcguide.com\/ref\/hdd\/bios\/modesLBA-c.html."},{"volume-title":"Proceedings of the USENIX Conference.","author":"Policroniades C.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the 1st USENIX Conference on File and Storage Technologies.","author":"Quinlan S.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","unstructured":"RFC 1321 1992. The MD5 message-digest algorithm. IETF.  RFC 1321 1992. The MD5 message-digest algorithm. IETF."},{"key":"e_1_2_1_22_1","first-page":"17","article-title":"One approach to efficient management of zillion signatures","volume":"2","author":"Rudan S.","year":"2006","journal-title":"PSI Trans. Internet Res."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970343.1970345","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1970343.1970345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:52Z","timestamp":1750243972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970343.1970345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1145\/1970343.1970345"],"URL":"https:\/\/doi.org\/10.1145\/1970343.1970345","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2011,6]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}