Topic:
external search and sort
Topic:
search algorithms
Topic:
database keys and indexing
Topic:
b-trees
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; in-memory sorting, disk-based 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 non-random 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: hash-based sort
| Quote: trie hash by sort on leading digits with split between buckets by a prefix; better than B-tree, 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 n-gram-hash-and-skip for matching keywords in a large dictionary of 10,000-100,000 entries [»coheJD12_1998]
|
Subtopic: nearly sorted lists
| Quote: for nearly sorted lists, insertion sort is best for small or very-nearly sorted lists; otherwise use Quicker-sort [»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 unit-time; best for heavy-duty 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: b-trees (16 items)
Topic: string operations
(20 items)
|
