lucene
RoaringBitmap
Our great sponsors
lucene | RoaringBitmap | |
---|---|---|
11 | 24 | |
2,358 | 3,388 | |
4.0% | 1.4% | |
9.8 | 8.5 | |
about 13 hours ago | 5 days ago | |
Java | Java | |
Apache License 2.0 | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
lucene
-
Building an efficient sparse keyword index in Python
First, a review of the landscape. As said in the introduction, there aren't a ton of good options. Apache Lucene is by far the best traditional search index from a speed, performance and functionality standpoint. It's the base for Elasticsearch/OpenSearch and many other projects. But it requires Java.
-
Java Panama Vector API Integrated with Apache Lucene
https://github.com/apache/lucene/issues/10047
2. The Panama Vector API allows CPU's that support it to accelerate vector operations: https://openjdk.org/jeps/438
So this allows fast ANN on Lucene for semantic search!
How did people do this before Lucene supported it? Only through entirely different tools?
-
What Is a Vector Database
Are they forking Lucene or somehow getting the Lucene devs to increase that limit? Because this PR has been open for over a year now: https://github.com/apache/lucene/issues/11507
- An alternative to Elasticsearch that runs on a few MBs of RAM
- Lucene 9.4 (optionally) uses Panama's mapped MemorySegments when JDK 19 is detected
-
A primer on Roaring bitmaps: what they are and how they work
Lucene's adaptation of Roaring uses the complement idea on a block-wise basis:
https://github.com/apache/lucene/blob/84cae4f27cfd3feb3bb42d...
-
How are documents stored in Elasticsearch?
Like someone said, it's in locations as specified in the path.data. Depending on sharing and replication, it could be on more than one host. Elastic uses Apache Lucene to store documents, since it's open source, that rabbit hole will welcome research :-)
- panama/foreign status update
-
Amazon Elasticsearch Service Is Now Amazon OpenSearch Service
It is pretty clear to me that Elastic is planning to build their ANN features differently than OpenDistro's k-NN implementation, or other plugins modules that extend Easticsearch in similar ways. They now will build on the Apache Lucene capabilities that were collaboratively built "upstream" by a number of individuals, some that work for Amazon and some that work for Elastic.
From the linked issue, it seemed that they were originally planning to develop this as a proprietary feature of Elasticsearch, without contributing the functionality to Apache Lucene, but then changed direction when the Apache Lucene developers (some of which are currently employed to do such work by Amazon) started to build its approximate nearest neighbor (ANN) vector search capabilities. [1]
It's great to see folks that work for Elastic collaborating and building on what is in Apache Lucene to extend the utility of ANN with Hierarchical Navigable Small World Graphs (HNSW) [2]! From this, I think it should be possible to implement an Open Source version of the functionality with a compatible API, if that is something that OpenSearch users seek.
[1] https://issues.apache.org/jira/browse/LUCENE-9004
[2] https://github.com/apache/lucene/pull/250
RoaringBitmap
-
Iterating over Bit Sets Quickly
I was recently reading about Roaring https://roaringbitmap.org/ which is a highly optimized compressed bitset implementation. I reccomend reading about it if you are interested in this sort of thing. The talk at https://roaringbitmap.org/talks/ is especially good.
- Roaring Bitmaps
- Roaring bitmaps are compressed bitmaps, can be 100x faster
-
What feature would you like to remove in C++26?
However, I would love compressed (not just packed) bitsets too, which is something different to me. I would make it another class with a similar interface, based on something like roaring. It doesn't need to be in the standard, but it would be nice if the API was a such that one could easily swap implementations.
-
Jaccard Index
As an aside if you find yourself having to compute them on the fly, know that the Roaring Bitmaps libraries is the way to go [1]. The bitmaps are compressed, and can be streamed directly into SIMD computations (batching XORs and popcnts 256 bits wide!). The Jaccard index is just intersection_len / union_len [2] away
[1] https://roaringbitmap.org/
[2] https://roaringbitmap.readthedocs.io/en/latest/#roaringbitma...
-
Looking for fast, space-efficient key-lookup
Use a two stage approach, with a bloom/cuckoo filter stored as a https://roaringbitmap.org/ in memory. Then a secondary key/value store on disk (bolt or anything else).
-
BitSet Vs BigInteger
As an aside, if you're dealing with large bit sets, you might also want to evaluate Roaring Bitmaps.
-
Negative Incentives in Academic Research
Sidetracking a bit the conversation. What a coincidence that the author (Lemire) is also represented on Today's #1 "Ask HN: What are some cool but obscure data structures you know about?" as he is the main contributor of RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap and one of the main authors of the data structure.
- Ask HN: What are some 'cool' but obscure data structures you know about?
- Roaring bitmaps: A better compressed bitset
What are some alternatives?
pisa - PISA: Performant Indexes and Search for Academia
HyperMinHash-java - Union, intersection, and set cardinality in loglog space
Typesense - Open Source alternative to Algolia + Pinecone and an Easier-to-Use alternative to ElasticSearch ⚡ 🔍 ✨ Fast, typo tolerant, in-memory fuzzy Search Engine for building delightful search experiences
CQEngine - Ultra-fast SQL-like queries on Java collections
OpenSearch - 🔎 Open source distributed and RESTful search engine.
Primes - Prime Number Projects in C#/C++/Python
Apache Solr - Apache Lucene and Solr open-source search software
Feign - Feign makes writing java http clients easier
resin - Vector space search engine. Available as a HTTP service or as an embedded library.
maven-compiler-plugin - Apache Maven Compiler Plugin
liqe - Lightweight and performant Lucene-like parser, serializer and search engine.
alexandria - Full text search engine powering Alexandria.org - the open search engine.