efficient / surf Goto Github PK
View Code? Open in Web Editor NEWFirst Practical and General-purpose Range Filter
License: Other
First Practical and General-purpose Range Filter
License: Other
I saw a previous issue has been closed, citing assertions at the beginning of the functions. But those assertions are NOT sufficient.
Description of the problem:
potential buffer overrun in line 95 and 96 of bitvector.hpp
Line 95 in cbf2358
The assertion at beginning of the function (assert(pos <= num_bits_);) does NOT work, suppose there's a run of 0s longer than 128 near the end of the bit vector, when we enter the function the pos might as well within range, but the logic in the function will keep reading the next long until it runs over the buffer by exactly 8 bytes. The function will returns the wrong result because of this.
Have you conducted any experiments using both bloom filters and SuRF next to each other simultaneously (i.e. in one RocksDB instance) whereas bloom filters would be used for point queries and SuRF for range queries? How much would be the overhead of maintaing both in memory and from the time complexity point of view? Any measurements?
Thank you!
Slightly related: #3
I am trying to wrap SuRF lib with JNI. But I found a bug when testing serialize & deserialize function.
Then I modified the simple_example.cpp and the bug still happend.
Test code:
#include <iostream>
#include <vector>
#include "include/surf.hpp"
using namespace surf;
int main() {
std::vector<std::string> keys = {
"f",
"far",
"fast",
"s",
"top",
"toy",
"trie",
};
// basic surf
SuRF* surf = new SuRF(keys);
char* data = surf->serialize();
surf = SuRF::deSerialize(data);
std::cout << surf->lookupKey("f");
std::cout << surf->lookupKey("far");
std::cout << surf->lookupKey("fast");
std::cout << surf->lookupKey("s");
std::cout << surf->lookupKey("top");
std::cout << surf->lookupRange("a", true, "a", true);
std::cout << surf->lookupRange("fa", true, "fast", true);
std::cout << surf->lookupRange("st", true, "top", true);
std::cout << surf->lookupRange("fat", true, "trie", true);
std::cout << surf->lookupRange("st", true, "z", true);
return 0;
}
assert(pos <= num_bits_) in Bitvector::readBit fails. I'll attach the dataset, workload, and setup shortly.
Hi, If I want get the benchmark data(with RocksDB) In paper, How Can I benchmark in RocksDB?
Thanks.
can you give a detailed example?
I've observed multiple scenarios where SuRF has a non-0 false negative rate. I'll submit the dataset, queries, and setup for when this happens shortly.
I use 10000 key to build SuRF, and then lookup those key , but SuRF miss some key?
// test code
std::vector<std::string> keys;
for (int i = 0; i < 10000; i++) {
keys.push_back(std::to_string(i));
}
// basic surf
SuRF* surf = new SuRF(keys);
// use default dense-to-sparse ratio; specify suffix type and length
SuRF* surf_hash = new SuRF(keys, surf::kHash, 8, 0);
SuRF* surf_real = new SuRF(keys, surf::kReal, 0, 8);
// customize dense-to-sparse ratio; specify suffix type and length
SuRF* surf_mixed = new SuRF(keys, true, 16, surf::kMixed, 4, 4);
int n_error = 0;
int n_correct = 0;
for (int i = 0; i < 10000; i++) {
if (surf->lookupKey(std::to_string(i)))
n_correct++;
else
n_error++;
}
std::cout << "num:"<< n_error << ":" << n_correct << std::endl;
num:9:9991
Hi, I come here again...
Here, the most important feature range query :
Line 215 in e038235
And in the bench, there is a multi-thread work load test
SuRF/bench/workload_multi_thread.cpp
Line 28 in e038235
This lookUpRange function uses a private class variable iter_. It first calls iter_.clear(), which clear some variables, but do not new them. When multi-threads call this function, they will all modify this variable at the same time which could nullify the programming logic.
Perhaps it should new a iter every time when there is a call?
Thanks!
Line 246 in cbf2358
At the line referenced above, suppose we are at the very last node, whose label is legitimately '0xff', then readBit(pos + 1) would trigger assertion failure.
Trying to use deSerialize(serialize()) as a cloning function, but it doesn't work properly.
In the following code, I use deSerialize(serialize()) to make a copy of an instance, and then destroy the copy immediately, which crashes the program with a "double free or corruption (out); Signal: SIGABRT (Aborted)" error.
#include <iostream>
#include <vector>
#include "include/surf.hpp"
using namespace surf;
#include <iostream>
#include <vector>
#include <algorithm>
#include "include/surf.hpp"
#include <string>
#include <fstream>
using namespace surf;
using namespace std;
vector<string> read_dataset(const string& file_path) {
vector<string> dataset;
ifstream file(file_path);
cout << "INIT reading dataset file " << file_path << endl;
int id = 0;
while (!file.eof()) {
string line;
getline(file, line);
if(!line.empty()) {
dataset.push_back(line);
}
id++;
}
file.close();
cout << "END reading dataset file " << file_path << endl;
cout << "READ " << dataset.size() << " rows" << endl;
return dataset;
}
static vector<string> split(string str, const string& delim) {
vector<string> ret;
while (str.find(delim) != std::string::npos) {
if (str.find(delim) >= 1) {
ret.push_back(str.substr(0, str.find(delim)));
}
str = str.substr(str.find(delim) + delim.size(), str.size() - (str.find(delim) + delim.size()));
}
if (!str.empty()) {
ret.push_back(str);
}
return ret;
}
vector<pair<string, string> > read_workload(const string& file_path) {
vector<pair<string, string> > workload;
ifstream file(file_path);
cout << "INIT reading workload file " << file_path << endl;
int id = 0;
while (!file.eof()) {
string line;
getline(file, line);
assert(line.find(' ') != std::string::npos);
if (!line.empty()) {
vector<string> parts = split(line, " ");
assert(parts.size() == 2);
workload.emplace_back(parts[0], parts[1]);
}
id++;
}
file.close();
cout << "END reading workload file " << file_path << endl;
cout << "READ " << workload.size() << " rows" << endl;
return workload;
}
int surf_main() {
vector<string> dataset = read_dataset("dataset.txt");
sort(dataset.begin(), dataset.end());
vector<pair<string, string> > workload = read_workload("workload.txt");
surf::SuRF *surf_real = new surf::SuRF(dataset, surf::kReal, 0, 8);
surf::SuRF::deSerialize(surf_real->serialize())->destroy();
assert(false);
return 0;
}
Hi, I am trying to rewrite a java version of SuRF. However, I encountered several problems which all involved with index out of bound exception.
In bitvector.hpp
We initially define bits_=[numWords()];
However, here
Line 96 in c9c8986
Line 165 in c9c8986
Test Code:
#include
#include
#include "include/surf.hpp"
using namespace surf;
int main() {
std::vectorstd::string keys = {
"f",
"far",
"fast",
"s",
"top",
"toy",
"trie",
};
// basic surf
SuRF* surf = new SuRF(keys);
surf = SuRF::deSerialize(surf->serialize());
std::cout << "destory surf" << std::endl;
surf->destroy();
return 0;
}
Maybe the issue happens when destroy BitVectorRank:
void destroy()
{
delete[] bits_;
delete[] rank_lut_;
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.