File PGMIndex.h

↰ Parent directory (ADS/search)

The piecewise geometric model index of Ferragina and Vinciguerra, beyond the book: a learned index on a sorted array of arithmetic keys, which finds the place of the first item not smaller than a key [see File StaticSearch.h for the static B+-tree] in a space that depends on the regularity of the keys rather than on their number.

Definition (ADS/search/PGMIndex.h)

Detailed Description

The items A[ 0 .. n ) are the points :math:` ( A[ i ] , i ) ` of the plane, a repeated key standing for its first place. An :math:` epsilon -approximation is a sequence of segments, each a line :math: f( x ) = a + b ( x - k_s ) ` over a range of keys from its first key :math:` k_s , such that :math: | f( A[ i ] ) - i | le epsilon ` for every key of its range; the segments are those of the optimal approximation, the fewest possible, built in one pass in O( n ) time by the algorithm of O’Rourke as engineered by Xie et al.: the lines through the points of the range with error at most :math:` epsilon ` are those between the line of least slope and the line of largest slope that the convex hulls of the points moved up and down by :math:` epsilon ` admit, the two hulls updated by a new point in amortized O( 1 ), and a range ends when a point leaves no line. The segment keeps the line of the average of the two extreme slopes through the point where they cross (any line of slope between them through that point stays within the error), its slope made not negative so that the prediction never decreases. The first keys of the segments are themselves approximated, with an error :math:` epsilon_r , by the segments of a level above, and so on up to a single segment: for m segments at the level below, a level has at most :math: m / ( 2 epsilon_r ) ` of them (a segment of the optimal approximation covers at least :math:` 2 epsilon ` points, since the horizontal line through the middle of any :math:` 2 epsilon ` consecutive ranks is within the error), the levels are :math:` 1 + lceil log_{2 epsilon_r} m rceil ` at most, and the index takes 28 bytes per segment (its first key, the two doubles of its line and its first place), m at most :math:` n / ( 2 epsilon ) ` and much fewer on regular keys.

A search starts from the segment at the top, and at each level the prediction of its line, clamped to the range of the segment, is the place of the next segment within :math:` pm ( epsilon_r + 1 ) ` places (one more for the rounding of the line in double), found by a binary search with no branch of the last first key not larger than the key; at the last level the prediction is the place of the answer within :math:` pm ( epsilon + 2 ) , whose lines of cache are all prefetched at once, so that their misses overlap, and searched in the same way: :math: O( log epsilon_r log_{2 epsilon_r} m + log epsilon ) ` time. The items are a copy on huge pages [see File HugePageAllocator.h], so that the window of a search costs no miss of the TLB of its own. On repeated keys, whose places a line cannot all approximate, the search goes on past the window by galloping. The keys are mapped to integers of 64 bits in the same order (the signed by flipping the top bit, the floating by their bits), so that the hulls are kept with exact products of 128 bits.

The contracts [see File Contract.h]: the keys sorted, an audit; :math:` epsilon ge 1 , :math: epsilon_r ge 1 `; each result r is such that the items before r are smaller than the key and those from r on are not, a postcondition. The functions are defined in PGMIndex.tpp.

  1. Ferragina, G. Vinciguerra, The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds, Proceedings of the VLDB Endowment 13(8), 1162-1175, 2020, doi:10.14778/3389133.3389135

  1. O’Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM 24(9), 574-578, 1981, doi:10.1145/358746.358758

  1. Xie, C. Pang, X. Zhou, X. Zhang, K. Deng, Maximum error-bounded piecewise linear representation for online stream approximation, The VLDB Journal 23(6), 915-937, 2014, doi:10.1007/s00778-014-0355-0

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes