[Feature] Implementing One-Dimensional BKD Tree for Numeric Range Query Optimization

[hanahmily]

Search before asking

• I had searched in the issues and found no similar feature requirement.

Description

I propose an enhancement to optimize the performance of numeric range queries in the Ice Segment Plugin for Bluge.

Currently, our performance on numeric range queries could be significantly improved. The existing data structure for our inverted index module needs to provide optimal efficiency for handling these queries.

Proposed Solution:

I propose implementing a one-dimensional BKD (Bounded K-Dimensional) tree for numeric types in the inverted index module. BKD trees are renowned for their effectiveness in managing multi-dimensional spatial data, and in a one-dimensional context, they can offer substantial advantages for numeric range queries.

The BKD tree would be incorporated as a dictionary implementation in Ice. Each node in the tree would store a term, and the corresponding postings lists would be stored in the leaves. This structure would enable us to quickly perform range queries by traversing the tree and accessing only the relevant nodes, which could dramatically enhance the performance of these queries.

Use case

No response

Related issues

No response

Are you willing to submit a pull request to implement this on your own?

• Yes I am willing to submit a pull request on my own!

Code of Conduct

• I agree to follow this project's Code of Conduct