Mathematical model for key search by hashing, and asymptotic evaluation on efficiency of search

• FUTAGAMI Tsuneji

  Department of Industrial Management Systems Engineering School of Science and Engineering, Waseda University

• MATSUSHIMA Toshiyasu

  Department of Industrial Management Systems Engineering School of Science and Engineering, Waseda University

• HIRASAWA Shigeichi

  Department of Industrial Management Systems Engineering School of Science and Engineering, Waseda University

Bibliographic Information

Other Title

• ハッシュ技法によるデータ探索の数学的モデル化, 及び探索効率の漸近的評価

Abstract

In this study, an algorithm in which records stored in secondary storage by hashing are efficiently searched is proposed. Keys inherent to records and a quary are represented by binary vectors, and records having keys close to a quary in the Hamming space are searched. The search for all records leads to large access time to secondary storage. In this study, an algorithm was proposed that a vector representing a key of a record are divided into some blocks, and Hamming distances between a record and some code words in each block are stored in RAM. The condition that a number of searched records decreases in the proposed method compared with the previous method is found when the length of a vector is large enough.

Journal

• IEICE technical report. Information theory

  IEICE technical report. Information theory 97 (80), 79-84, 1997-05-30

  The Institute of Electronics, Information and Communication Engineers

Keywords

• key search
• hashing
• associative memory

Details

• CRID: 1572543027237602944
• NII Article ID: 110003197000
• NII Book ID: AN10013083
• Text Lang: ja
• Data Source:
  • CiNii Articles