Topic: external search and sort
Topic: search algorithms
Topic: database keys and indexing
Topic: btrees
Topic: string operations
 
Subtopic: search and sort algorithms
Quote: algorithms for string search and sort; radix quicksort and ternary search trees [»bentJL1_1997]
 Quote: survey of sorting in database systems; inmemory sorting, diskbased external sorting, implementation techniques [»graeG9_2006]
 Subtopic: duplicate detection
Quote: delete duplicates by multiple passes using hashing; linear average time; constant extra space [»teuhJ3_1991]
 Subtopic: quick sort
Quote: quicksort algorithm; recursively partitions data by key [»hoarCA1_1962]
 Quote: improve quicksort on long keys with codewords; count of equal bytes, first nonequal byte, record pointer [»baerJL5_1989]
 Quote: library qsorts can be easily driven to quadratic behavior; derived from 7th edition Unix or 1983 Berkeley functions [»bentJL11_1993]
 Quote: implement qsort with different medians depending on size; insertion sort, middle element, median of three, median of nine [»bentJL11_1993]
 Quote: tripartite partitioning in qsort is equivalent to the Dutch National Flag problem; place equal elements at either end [»bentJL11_1993]
 Quote: better swapping and other improvements to qsort is on average 2x faster than previous versions; up to 12x [»bentJL11_1993]
 Subtopic: sort algorithms
Quote: proportion extended sort (psort); faster than qsort; linear on already sorted input; O(n log n) comparisons [»chenJC7_2004]
 Quote: proportion extended sort based on a sorted subsequence followed by an unsorted subsequence; uses reference elements to identify nonrandom inputs [»chenJC7_2004]
 Quote: psort uses fewer comparisons than qsort; faster for sorted input, nearly sorted input, random input, and random binary [»chenJC7_2004]
 Subtopic: swap
Quote: provides a formula to check data size and alignment; works on many machines including Crays [»bentJL11_1993]
 Subtopic: hashbased sort
Quote: trie hash by sort on leading digits with split between buckets by a prefix; better than Btree, can 100% load for ordered insertion [»litwWA7_1991]
 Quote: linear probing sort for uniformly distributed elements; hash into range and shift as needed [»carlS2_1991]
 Quote: linear hashing with partial expansions and priority splitting; 80% storage utilization, 1 block access per search, and 8% overflow space [»manoY5_1994]
 Quote: use ngramhashandskip for matching keywords in a large dictionary of 10,000100,000 entries [»coheJD12_1998]
 Subtopic: nearly sorted lists
Quote: for nearly sorted lists, insertion sort is best for small or verynearly sorted lists; otherwise use Quickersort [»cookCR11_1980]
 Quote: for nearly sorted lists, separate into sorted and unsorted lists, then sort and merge [»cookCR11_1980]
 Subtopic: radix sort
Quote: radix sort by bytes is faster than Quicksort [»daviIJ12_1992]
 Quote: radix quicksort for strings skips over common prefixes; can be 4 times faster than qsort [»bentJ11_1998]
 Quote: use American flag radix sort when comparison is not unittime; best for heavyduty sorting of at least 10,000 keys [»mcilPM1_1993]
 Subtopic: history
Quote: first table in lexicographic order; reciprocals of numbers [»knutDE7_1972]
 Subtopic: avoid sorting
Quote: compare SQL queries across multiple vendors; avoid sorting by comparing row counts and column checksums [»slutD8_1998, OK]

Related Topics
Topic: external search and sort (23 items)
Topic: search algorithms (40 items)
Topic: database keys and indexing (18 items)
Topic: btrees (16 items)
Topic: string operations (20 items)
