https://github.com/learnedsystems/RadixSpline Skip to content Sign up * Why GitHub? Features - + Mobile - + Actions - + Codespaces - + Packages - + Security - + Code review - + Project management - + Integrations - + GitHub Sponsors - + Customer stories - + Security - * Team * Enterprise * Explore + Explore GitHub - Learn & contribute + Topics - + Collections - + Trending - + Learning Lab - + Open source guides - Connect with others + The ReadME Project - + Events - + Community forum - + GitHub Education - + GitHub Stars program - * Marketplace * Pricing Plans - + Compare plans - + Contact Sales - + Nonprofit - + Education - [ ] [search-key] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this organization All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} learnedsystems / RadixSpline * Watch 6 * Star 62 * Fork 7 A Single-Pass Learned Index MIT License 62 stars 7 forks Star Watch * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Security * Insights master 1 branch 0 tags Go to file Code Clone HTTPS GitHub CLI [https://github.com/l] Use Git or checkout with SVN using the web URL. [gh repo clone learne] Work fast with our official CLI. Learn more. * Open with GitHub Desktop * Download ZIP Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Go back Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Go back Launching Xcode If nothing happens, download Xcode and try again. Go back Launching Visual Studio If nothing happens, download the GitHub extension for Visual Studio and try again. Go back Latest commit @andreaskipf andreaskipf Update configs ... 7f8b538 Jul 22, 2020 Update configs 7f8b538 Git stats * 9 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .github/workflows fixed runner Jun 19, 2020 cmake_modules Initial commit Jun 19, 2020 include/rs improved radix table size Jul 8, 2020 test improved radix table size Jul 8, 2020 .gitignore Initial commit Jun 19, 2020 CMakeLists.txt added simple benchmark Jul 8, 2020 LICENSE Initial commit Jun 19, 2020 README.md fixed runner Jun 19, 2020 bench.cc Update configs Jul 22, 2020 example.cc Initial commit Jun 19, 2020 View code README.md RadixSpline: A Single-Pass Learned Index [badge] A read-only learned index structure that can be built in a single pass over sorted data. Can be used as a drop-in replacement for std::multimap. Currently limited to uint32_t and uint64_t data types. Build mkdir -p build cd build cmake -DCMAKE_BUILD_TYPE=Release .. make ./example ./tester Examples Using rs::Builder to index sorted data in one pass, without copying the data: // Create random keys. vector keys(1e6); generate(keys.begin(), keys.end(), rand); keys.push_back(8128); sort(keys.begin(), keys.end()); // Build RadixSpline. uint64_t min = keys.front(); uint64_t max = keys.back(); rs::Builder rsb(min, max); for (const auto& key : keys) rsb.AddKey(key); rs::RadixSpline rs = rsb.Finalize(); // Search using RadixSpline. rs::SearchBound bound = rs.GetSearchBound(8128); cout << "The search key is in the range: [" << bound.begin << ", " << bound.end << ")" << endl; auto start = begin(keys) + bound.begin, last = begin(keys) + bound.end; cout << "The key is at position: " << std::lower_bound(start, last, 8128) - begin(keys) << endl; Using rs::MultiMap to index unsorted data, which internally creates a sorted copy: vector> data = {{1ull, 'a'}, {12ull, 'b'}, {7ull, 'c'}, // Unsorted. {42ull, 'd'}}; rs::MultiMap map(begin(data), end(data)); cout << "find(7): '" << map.find(7)->second << "'" << endl; cout << "lower_bound(3): '" << map.lower_bound(3)->second << "'" << endl; Cite Please cite our aiDM@SIGMOD 2020 paper if you use this code in your own work: @inproceedings{radixspline, author = {Andreas Kipf and Ryan Marcus and Alexander van Renen and Mihail Stoian and Alfons Kemper and Tim Kraska and Thomas Neumann}, title = {{RadixSpline}: a single-pass learned index}, booktitle = {Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD 2020, Portland, Oregon, USA, June 19, 2020}, pages = {5:1--5:5}, year = {2020}, url = {https://doi.org/10.1145/3401071.3401659}, doi = {10.1145/3401071.3401659}, timestamp = {Mon, 08 Jun 2020 19:13:59 +0200}, biburl = {https://dblp.org/rec/conf/sigmod/KipfMRSKK020.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } About A Single-Pass Learned Index Topics learned-index radix-structure linear-spline Resources Readme License MIT License Releases No releases published Packages 0 No packages published Contributors 2 * @alexandervanrenen alexandervanrenen Alexander van Renen * @andreaskipf andreaskipf Andreas Kipf Languages * C++ 95.2% * CMake 4.8% * (c) 2021 GitHub, Inc. * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.