Usage
  • 20 views
  • 51 downloads

Geometric Filter: A Space and Time Efficient Lookup Table with Bounded Error

  • Author / Creator
    Zhao, Yang
  • Lookup tables are frequently used in many applications to store and retrieve keyvalue pairs. Designing efficient lookup tables can be challenging with constraints placed on storage, query response time and/or result accuracy. This thesis proposes Geometric filter, a lookup table with a space requirement close to the theoretical lower bound, efficient construction, fast querying speed, and guaranteed accuracy. Geometric filter consists of a sequence of hash tables, the sizes of which form a descending geometric series. Compared with its predecessor, Bloomier filter, its encoding runs two times faster, uses less memory, and it allows updates after encoding. We analyze the efficiency of the proposed lookup table in terms of its storage requirement and error bound, and run experiments on Web 1TB 5-gram dataset to evaluate its effectiveness.

  • Subjects / Keywords
  • Graduation date
    2009-11
  • Type of Item
    Thesis
  • Degree
    Master of Science
  • DOI
    https://doi.org/10.7939/R3M12J
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
    English
  • Institution
    University of Alberta
  • Degree level
    Master's
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Rafiei, Davood (Computing Science)
    • Nascimento, Mario (Computing Science)
  • Examining committee members and their departments
    • Salavatipour, Mohammad (Computing Science)
    • Reformat, Marek (Electrical and Computer Engineering)