{"corpus_id":2723596,"paper_sha":"3449592f90c5f5329cf541f027925db085ea33fd","doi":"10.1145/320083.320092","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":2087966340,"dblp_id":"journals/tods/FaginNPS79","acl_id":null,"title":"Extendible hashing—a fast access method for dynamic files","year":1979,"publication_date":"1979-09-01","venue":"ACM Transactions on Database Systems","journal":{"name":"ACM Transactions on Database Systems (TODS)","pages":"315 - 344","volume":"4"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Computer Science"],"reference_count":21,"citation_count":774,"influential_citation_count":37,"is_open_access":true,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"https://dl.acm.org/doi/pdf/10.1145/320083.320092","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/3449592f90c5f5329cf541f027925db085ea33fd","s2_open_access_license":null,"s2_open_access_status":"BRONZE","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.","claims":[{"public_id":"cl_18ef143c0d514b110711d0b80ac60c45","status":"active","text":"Analysis and simulation indicate that extendible hashing is an attractive alternative to balanced trees and other access methods.","confidence":0.87,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_18ef143c0d514b110711d0b80ac60c45"},{"public_id":"cl_8bd04cad6f25dace03b4656936b33a9f","status":"active","text":"Extendible hashing simultaneously solves the problem of making hash tables extendible and radix search trees balanced.","confidence":0.91,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_8bd04cad6f25dace03b4656936b33a9f"},{"public_id":"cl_6d9445055c6b67e17b74436a2db1107a","status":"active","text":"No more than two page faults are required to locate the data associated with a given key.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_6d9445055c6b67e17b74436a2db1107a"},{"public_id":"cl_87c30894a0795138fe3e9602604ef410","status":"active","text":"The structure grows and shrinks gracefully as the database grows and shrinks.","confidence":0.92,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_87c30894a0795138fe3e9602604ef410"}],"concepts":[{"public_id":"co_0bffe1893e920850afc45e64a3139ab6","status":"active","name":"dynamic files","description":"Files whose size changes over time as records are inserted or removed.","types":["data structure"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_0bffe1893e920850afc45e64a3139ab6"},{"public_id":"co_4014f7d5b76824e83b7a1135fc59ca94","status":"active","name":"extendible hashing","description":"A dynamic hashing access technique for retrieving data by key.","types":["method"],"aliases":["extendible hash"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_4014f7d5b76824e83b7a1135fc59ca94"},{"public_id":"co_45eb5f66eaacc1132e6325f19a05e35e","status":"active","name":"database growth and shrinkage","description":"Changes in database size caused by additions and deletions of records.","types":["process"],"aliases":["grows and shrinks"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_45eb5f66eaacc1132e6325f19a05e35e"},{"public_id":"co_5a7f155e0ff2fd28848f949200d7e9b8","status":"active","name":"radix search trees","description":"Search trees organized by key digits or bit prefixes.","types":["data structure"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_5a7f155e0ff2fd28848f949200d7e9b8"},{"public_id":"co_b7b4cb77dc4470c3fed2daf33e704a37","status":"active","name":"page faults","description":"Storage accesses that require fetching a page to locate requested data.","types":["performance measure"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b7b4cb77dc4470c3fed2daf33e704a37"},{"public_id":"co_b9c49b0a033fe82ec27429dddd81c109","status":"active","name":"key","description":"A unique identifier used to locate associated data.","types":["identifier"],"aliases":["unique identifier"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b9c49b0a033fe82ec27429dddd81c109"},{"public_id":"co_bf4042eb0f49b763c246dcb847c7d98f","status":"active","name":"balanced trees","description":"Tree-based access methods that maintain balance to support efficient operations.","types":["baseline"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_bf4042eb0f49b763c246dcb847c7d98f"},{"public_id":"co_d399cda5e9a53c0949adef51a3798273","status":"active","name":"other access methods","description":"Alternative file access techniques considered for comparison.","types":["baseline"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d399cda5e9a53c0949adef51a3798273"},{"public_id":"co_dab079c81d968d2ea7a2c1fc9ede0aa8","status":"active","name":"hash tables","description":"Data structures that map keys to storage locations using hashing.","types":["data structure"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_dab079c81d968d2ea7a2c1fc9ede0aa8"},{"public_id":"co_dbcfa90a600864456b6e1cb12faa76b3","status":"active","name":"analysis and simulation","description":"Evaluation approaches used to study the performance of the access method.","types":["evaluation method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_dbcfa90a600864456b6e1cb12faa76b3"}],"external_ids":{"DOI":"10.1145/320083.320092","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":2087966340,"DBLP":"journals/tods/FaginNPS79","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://dl.acm.org/doi/pdf/10.1145/320083.320092","landing_url":"https://www.semanticscholar.org/paper/3449592f90c5f5329cf541f027925db085ea33fd","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":null,"status":"BRONZE","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635705,"paper_uid":"9b6da663-b0bf-401e-a9cc-e8cec09b223f","canonical_identity":{"paper_id":635705,"paper_uid":"9b6da663-b0bf-401e-a9cc-e8cec09b223f","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/2723596"}