Merging multiple sorted lists in a distributed computing system
US11726743B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 11, 2022 |
| Grant date | Aug 15, 2023 |
| Priority date | — |
| Expiry date | Apr 11, 2042 |
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.