Bit-Vector Search Filtering with Application to a Kanji Dictionary

Matthew Skala

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Database query problems can be categorized by the expressiveness of their query languages, and data structure bounds are better for less expressive languages. Highly expressive languages, such as those permitting Boolean operations, lead to difficult query problems with poor bounds, and high dimensionality in geometric problems also causes their query languages to become expressive and inefficient. The IDSgrep kanji dictionary software approaches a highly expressive tree-matching query problem with a filtering technique set in 128-bit Hamming space. It can be a model for other highly expressive query languages. We suggest improvements to bit vector filtering of general applicability, and evaluate them in the context of IDSgrep.
Original languageEnglish
Title of host publicationSimilarity Search and Applications: 9th International Conference, SISAP 2016, Tokyo, Japan, October 24-26, 2016
Publication date2016
ISBN (Print)978-3-319-46758-0
ISBN (Electronic)978-3-319-46759-7
Publication statusPublished - 2016
SeriesLecture Notes in Computer Science


  • Database Query Problems
  • Expressive Query Languages
  • Data Structure Bounds
  • Tree-Matching
  • 128-bit Hamming Space
  • Filtering Techniques
  • IDSgrep
  • Bit Vector Filtering
  • Geometric Problems
  • Boolean Operations


Dive into the research topics of 'Bit-Vector Search Filtering with Application to a Kanji Dictionary'. Together they form a unique fingerprint.

Cite this