Clarification on Error Bound Ranges for Present and Absent Keys

[min-guk]

Hello there! I want to express my admiration for the excellent thesis you've put together. Your work is truly insightful and contributes greatly to the field. Also, I appreciate the kind and helpful response you provided to my previous question. I hope you won't mind if I ask for your guidance once more.

I've been looking into the code and noticed something interesting. When a key is present, the error bound seems to be defined as [p-e, p+e+2). On the other hand, if the key isn't present, the error bound appears to be guaranteed as [p-e, p+e+3).

You mentioned in your comments that the range is guaranteed to contain a key that is not less than lookup key if key is not present. However, I was wondering if it might actually guaranteed to contain a key that is less than lookup key.

I hope you don't mind me seeking some clarification on this topic. Would it be more accurate to define the error bound range that includes the start and excludes the end as [p-e, p+e+3) regardless of whether the key exists or not? I'd really appreciate your thoughts on this.

Additionally, I've included a modified version of your example code below to help illustrate my question.

I hope you'll find my observations helpful, and if my findings do turn out to be accurate, would you be open to receiving a pull request for your repository? I'd be more than happy to contribute in a way that respects your work and intentions. Please let me know if this would be acceptable to you, and once again, thank you for your valuable insights and assistance.

[Test Code]

#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <random>
#include <unordered_set>
#include "pgm/pgm_index.hpp"

template <class KeyType>
std::vector<KeyType> CreateUniqueRandomKeys(size_t seed, size_t num_keys) {
  std::unordered_set<KeyType> keys;
  keys.reserve(num_keys);
  std::mt19937 g(seed);
  std::uniform_int_distribution<KeyType> d(std::numeric_limits<KeyType>::min(),
                                           std::numeric_limits<KeyType>::max());
  while (keys.size() < num_keys) keys.insert(d(g));
  std::vector<KeyType> sorted_keys(keys.begin(), keys.end());
  std::sort(sorted_keys.begin(), sorted_keys.end());
  return sorted_keys;
}

int main() {
    const auto keys = CreateUniqueRandomKeys<uint64_t>(42, 1000);
    const auto lookup_keys = CreateUniqueRandomKeys<uint64_t>(815, 1000);

    // Construct the PGM-index
    const int epsilon = 4; // space-time trade-off parameter
    pgm::PGMIndex<uint64_t, epsilon> index(keys);

    for (const auto& key : lookup_keys) {
        pgm::ApproxPos bound = index.search(key);
        const auto pgm_it = std::lower_bound(keys.begin() + bound.lo, keys.begin() + bound.hi, key);
        const auto std_it = std::lower_bound(keys.begin(), keys.end(), key);

        // Check if key is not present.
        if (*std_it != key){
            // Check if lowerbound of lookup key is p+e+2.
            if ((pgm_it == keys.begin() + bound.hi) && (std_it != keys.end())){
                std::cout << "[p+e+1 key]  value: " << *(keys.begin() + bound.hi - 1) << " lower_bound pos: " << bound.hi - 1 << std::endl;
                std::cout << "[lookup key] value: " << key << " lower_bound pos: " << std_it - keys.begin()<< std::endl;
                std::cout << "[p+e+2 key]  value: " << *(keys.begin() + bound.hi) << " lower_bound pos: " << bound.hi<< std::endl << std::endl;
            }
        }
    }
    return 0;
}

[Result]

g++ examples/simple.cpp -std=c++17 -I./include -o simple -fopenmp
./simple
[p+e+1 key]  value: 8746963316584524687 lower_bound pos: 484
[lookup key] value: 8747272492531411863 lower_bound pos: 485
[p+e+2 key]  value: 8781579887036780598 lower_bound pos: 485

[p+e+1 key]  value: 9697272242467760156 lower_bound pos: 535
[lookup key] value: 9699555025101314499 lower_bound pos: 536
[p+e+2 key]  value: 9734367273811274964 lower_bound pos: 536

[gvinciguerra]

Hi, and thanks again! In the example *std_it == *pgm_it so the correct key has been found. I updated the documentation so that it reflects the meaning of the returned range. Thanks

[min-guk]

I'm glad that my opinion is reflected in this repository. Have a good day!