Method for sorting data using common prefix bytes
US7680791B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 18, 2005 |
| Grant date | Mar 16, 2010 |
| Priority date | — |
| Expiry date | Nov 28, 2025 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Several techniques for sorting item are described, generally referred to as (1) common prefix skipping quicksort; (2) key substring caching; and (3) adaptive quicksort. With common prefix skipping quicksort, common prefix bytes among all key values for a partition are computed while performing a quicksort partitioning operation, and the known common bytes are skipped when comparing two key values in a recursive partitioning operation. With key substring caching, each item is represented in a cached array comprising a particular number of bytes for respective portions of key values (“key substring”), where the key substring cache is updated contain bytes beyond the known number of common prefix bytes. An adaptive quicksort routine is a hybrid of a quicksort function and most significant digit radix sort function, where the functions are mutually recursive.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.