~/talk

Index Searching with Regular Expressions

on YouTube 35m
TalkinRussianat HighLoad++ 2012 · 2012-10-22..10-23· [databases]

speaker

name:Aleksandr Korotkov
links:none on file

resources

video:https://youtu.be/BQJ6w620OV8
slides:none on file

summary

Describes building an index to speed up regex search over large text collections by combining finite automata with inverted-index techniques. Explains using automaton-based filtering (NFA/DFA), extracting fixed substrings or k-grams from patterns to query an inverted index, and then verifying matches to reduce full-regex evaluations.

AI-written summary · about

chapters (14)

  1. 0:00Introduction
  2. 1:30Regex and finite automata
  3. 4:17Regex search problem
  4. 6:45Inverted indexes and n-grams
  5. 9:40Regex to logical expressions
  6. 12:10Yandex Fast Text Express
  7. 14:24Google Search approach
  8. 17:54Speaker's method: automaton and trigrams
  9. 22:12Method comparison
  10. 24:24Performance tests
  11. 25:50Problems and limitations
  12. 27:24SQL integration
  13. 30:00Optimization and future work
  14. 32:16Q&A

related talks

~/search
type to search 6,249 conferences, 138,987 speakers and 185,172 talks
~/help
cmdctrl k
search every conference, speaker and series
/
focus the filter search
h
home
c
conferences
s
speakers
e
series
t
light / dark — the status bar button does the same
?
this help
esc
close this, then clear every filter — or just the search, while you are typing in it

Ignored while you are typing. Pages without a filter rail have no search to focus.