TY - GEN
T1 - Bit-Vector Search Filtering with Application to a Kanji Dictionary
AU - Skala, Matthew
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Database Query Problems
KW - Expressive Query Languages
KW - Data Structure Bounds
KW - Tree-Matching
KW - 128-bit Hamming Space
KW - Filtering Techniques
KW - IDSgrep
KW - Bit Vector Filtering
KW - Geometric Problems
KW - Boolean Operations
KW - Database Query Problems
KW - Expressive Query Languages
KW - Data Structure Bounds
KW - Tree-Matching
KW - 128-bit Hamming Space
KW - Filtering Techniques
KW - IDSgrep
KW - Bit Vector Filtering
KW - Geometric Problems
KW - Boolean Operations
U2 - 10.1007/978-3-319-46759-7_11
DO - 10.1007/978-3-319-46759-7_11
M3 - Article in proceedings
SN - 978-3-319-46758-0
T3 - Lecture Notes in Computer Science
SP - 138
EP - 150
BT - Similarity Search and Applications: 9th International Conference, SISAP 2016, Tokyo, Japan, October 24-26, 2016
PB - Springer
ER -