Group: algorithms
Group: information retrieval
Topic: adaptive hash table
Topic: approximate string matching and pattern matching with errors
Topic: btrees
Topic: collection class
Topic: external search and sort
Topic: hash table and hash functions
Topic: pattern matching
Topic: pattern specification
Topic: perfect hash table
Topic: searching compressed data
Topic: sort algorithms
Topic: string operations
Topic: suffix trie and suffix array
 
Subtopic: string search/sort
Quote: algorithms for string search and sort; radix quicksort and ternary search trees [»bentJL1_1997]
 Quote: backtracking is rarely a problem so KMP search is similar to naive search for most files [»fenwP7_2001]
 Quote: average case for 2 string matching algorithms, BoyerMooreHorspool faster than hardware character match for most pattern lengths [»baezRA8_1989]
 Quote: Boyer and Moore's string matching algorithm is more efficient than Knuth et al and Karp and Rabin [»daviG6_1986]
 Quote: speed up the BoyerMoore and reverse factor algorithms by remembering the last matched segment; for binary alphabets Turbo_RF is fastest [»crocM10_1994]
 Quote: using a pattern shift table, can search for substrings faster than the BoyerMoore algorithm [»sundDM8_1990]
 Quote: fast string searching by variants of BoyerMoore; toolkit for skip loop, match and shift components [»humeA11_1991]
 Quote: BoyerMoore string matching requires roughly 3n comparisons and less than 4n comparisons [»coleR10_1994]
 Quote: simple code for an efficient version of BoyerMooreHorspool string matching algorithm [»baezRA8_1989]
 Quote: stringmatching variant combines KnuthMorrisPratt (fewer comparisons) and BoyerMooreHorspool (better in worst case and preprocessing)
 Subtopic: regular expression search
Quote: sublinear search algorithm for regular expressions on preprocessed text; uses a Patricia tree for the index [»baezRA11_1996]
 Quote: identify search records by shortestsubstrings of regular expressions; e.g., all blocks [»clarCL5_1997]
 Quote: the leftmost longest match rule does not work for regular expressions in structured text [»clarCL5_1997]
 Quote: use the leftmost shortest match rule for regular expressions in structured text without predefined retrieval units [»clarCL5_1997]
 Quote: skip text runs during regular expression searching by recognizing shorter, reverse prefixes; performance similar to DFA [»navaG7_1999]
 Quote: first solution for regular expression searching in compressed text; faster than decompression plus search [»navaG7_2001]
 Subtopic: longestmatch search
Quote: compared longest match search for ZivLempel compression; lists for each character, best overall [»bellT7_1993]
 Quote: a maximal repeating pattern is as long as possible or occurs independently; use position trees for quadratic algorithm [»siocAC10_1991]
 Subtopic: bitparallel search
Quote: for patterns that fit in a computer word, fast, bitparallel string matching based on the ShiftOr algorithm; optimal average and worst case running times; variation for ShiftAdd algorithm and Hamming distance [»fredK11_2005]
 Subtopic: repeated search
Quote: use diagrams, filters, and preprocessing for fast, frequent searches; much faster with initialization overhead of 510 conventional searches [»fenwP7_2001]
 Subtopic: search UI
Quote: the right mouse button indicates arguments to a generalized search facility that locates files, file locations, and text [»pikeR1_1994]
 Subtopic: priority queue
Quote: constanttime insertion and findmin for priority queues; black box trades delete time for insert time [»alstS7_2005]
 Quote: simple, optimal, external sort using sampling and a priority queue; exactly two reads and writes per record [»leuFC2_2000]
 Subtopic: multidimensional search
Quote: skip quadtrees and octrees for multidimensional data; efficient insert, delete, location, approximate range, approximate nearest neighbor; logarithmicheight search and update [»eppsD6_2005]
 Subtopic: selfadjusting trees
Quote: a retrieval in a splay tree moves the retrieved node to the root, halves the length of the access path, and slightly increases other access paths [»tarjRE3_1987]
 Quote: conjecture that splay trees are optimal for binary search under amortized costs [»tarjRE3_1987]
 Quote: a median split tree is a balanced tree with the most frequent key at the root [»shelBA11_1978]
 Quote: selfadjusting algorithm for searching a linear dictionary list; online, fast successful and unsuccessful search, two extra bits per key [»huiLC11_1993]
 Subtopic: binary vs. selfadjusting
Quote: selfadjusting binary search trees are slower than AVL or binary trees; by CPU time, binary trees are often best [»bellJ4_1993]
 Subtopic: ternary search
Quote: ternary search trees better than binary trees, tries, and hashing; dynamic, fast operations including unsuccessful search and sort [»bentJ4_1998]
 Subtopic: randomized trees
Quote: randomized binary search trees based on size of subtrees; O(log n); access by rank [»martC3_1998]
 Subtopic: suffix search
Quote: with suffix trie, search time independent of text length [»nelsMR8_1996]
 Quote: use compressed suffix arrays and trees to search for short strings in O(1) time with O(n) space [»grosR5_2000]
 Quote: simple, space efficient suffix trees using balanced parentheses; O(n lg n) space and O(m) search [»munrJI5_2001]
 Subtopic: skip list
Quote: skip list of nodes with k forwarding pointers; levels chosen randomly then never changes; simple updates [»pughW6_1990]
 Quote: skip list is a randomized data structure for balanced trees; simple and space efficient (1.5 pointers per node) [»pughW6_1990]
 Quote: skip quadtrees and octrees for multidimensional data; efficient insert, delete, location, approximate range, approximate nearest neighbor; logarithmicheight search and update [»eppsD6_2005]
 Subtopic: Burrows Wheeler Transform
Quote: Burrows Wheeler Transform reversibly reorders data; models data by the string following a character [»nelsMR9_1996]
 Quote: use BurrowsWheeler blocksorted data for dynamic searching; compressed, rapid searches; groups similar substrings together [»willK12_2003]
 Subtopic: benchmarks
Quote: for search, speed and character comparisons may not be related; e.g., diagram search is 386x better by comparisons and 240x to 13x better by speed [»fenwP7_2001a]

Related Topics
Group: algorithms (6 topics, 94 quotes)
Group: information retrieval (25 topics, 674 quotes)
Topic: adaptive hash table (19 items)
Topic: approximate string matching and pattern matching with errors (19 items)
Topic: btrees (16 items)
Topic: collection class (11 items)
Topic: external search and sort (23 items)
Topic: hash table and hash functions (41 items)
Topic: pattern matching (42 items)
Topic: pattern specification (15 items)
Topic: perfect hash table (9 items)
Topic: searching compressed data (9 items)
Topic: sort algorithms (24 items)
Topic: string operations (20 items)
Topic: suffix trie and suffix array (20 items)
