Merging multiple sorted lists in a distributed computing system
US11301210B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 28, 2020 |
| Grant date | Apr 12, 2022 |
| Priority date | — |
| Expiry date | Oct 14, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2471
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A technique is described for merging multiple lists of ordinal elements such as keys into a sorted output. In an example embodiment, a merge window is defined, based on the bounds of the multiple lists of ordinal elements, that is representative of a portion of an overall element space associated with the multiple lists. Lists of elements to be sorted can be placed into one of at least two different heaps based on whether they overlap the merge window. For example, lists that overlap the merge window may be placed into an active or “hot” heap, while lists that do not overlap the merge window may be placed into a separate inactive or “cold” heap. A sorted output can then be generated by iteratively processing the active heap. As the processing of the active heap progresses, the merge window advances, and lists may move between the active and inactive heaps.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.