Patent · US Active

Constant range minimum query

US10417208B2 · kind B2 · utility

0Cited by

0References

17Claims

0Family size

Assignee

SAP SE · DE

Inventors

Alejandro Lopez-Ortiz · Walldorf, DE
Daniela Maftuleac · Walldorf, DE
Alejandro Salinger · Berlin, DE
Jeffrey Pound · Kitchener, CA

Key dates

Filing date	Dec 15, 2016
Grant date	Sep 17, 2019
Priority date	—
Expiry date	Oct 16, 2037

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/2455
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

A plus-minus-one array in which adjacent entries vary by no more than positive one and no less than negative one is accessed. A range minimum query directory tree including blocks and subblocks of the plus-minus-one array is determined. Blocks are contained in the plus-minus-one array and subblocks are contained in the blocks. A data structure characterizing positions of minimum elements within the range minimum query directory tree is generated. The characterization includes positions of minimums within each subblock, between subblocks in a respective block, within each block, and between blocks. The data structure is stored. Related apparatus, systems, techniques and articles are also described.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.