This seems like something that could be verified through ZK proofs. The data to search could be represented by a public merkle root, and the searching/indexing given the user query could be programmed in a ZKVM like RISC0[1].
The concept of a ZK VM is that it is able to prove arbitrary code. Risc0 and the more recent SP1[1] both compile arbitrary Rust programs into ZK circuits for generating and verifying execution proofs.