I'm trying to find a tool (database system, library, etc.) which can help me with a variation of the inverted index/posting list intersection problem. The variation is that a record matches only if a given term_i appears at least n_i times. My first attempt in sqlite doesn't work because the queries take too long. I need some solid suggestions on what I should try next.
I have a large (1-2 million) set of records. Each record has a set of features. Each feature has a count. These can be represented as:
0 CHEMBL500223 0:28,1:62,2:13,...,134,135,136 1 CHEMBL500234 0:4,1:32,2:5,3:6,4:17,5:3,...,466:3,467,468:2 2 CHEMBL500730 1:45,2:18,4:44,6:25,9:39,...,567,568 ...
This means that record 0 (which has the name CHEMBL500223) contains 28 instances of feature 0, 62 instances of feature 1, 13 of feature 2, and on up to 1 count of features 136.
Record 2 contains no instances of feature 0, but does contain 45 instances of feature 1, etc.
I'm doing a subset query. When a query comes in, I determine its features and respective counts. I want to find all records which have at least that many of each feature.
For example, if the query has 10 instances of feature 1 and 20 instances of feature 2 then only record 0 (CHEMBL500223) of these three would match.
I set this up with sqlite:
CREATE TABLE Features ( mol_id INTEGER, feature_id INTEGER, count INTEGER ); CREATE INDEX Features_by_feature_and_count ON Features (feature_id, count);
I loaded my data set (1.1 million records, 562 million features, and 6GB of database using 6 GB of cache) and executed the query:
SELECT mol_id FROM Features WHERE feature_id = 0 and count >= 10 INTERSECT SELECT mol_id FROM Features WHERE feature_id = 1 AND count >= 20)
That takes 20 seconds, from a hot cache.
I was hoping that it could be done in subsecond time. More specifically, I only need the first 100 in a subsecond, but LIMIT 100 doesn't make the search time any shorter.
Conceptually this should be fast, for a tool dedicated to this task.
So I wrote some Python code to manage a set of inverted indices, with counts. (FWIW, I can assume that count <= 255). This is basically a set of array.array instances, storing 4 4-byte document identifiers followed by 4 1-byte counts, with Python code to find the intersection using a an exponential/galloping search.
This works, though because I'm using pure Python, it takes a a couple of seconds to do the intersections of my ~100 index queries. There's much more work to make this be fast C code, and I know this is a mature field with lots of techniques I don't know anything about, so I'm hoping to build on the work of others.
Can you recommend a tool or library I can use for this?
I don't mean "should investigate." The short list includes Lucene, Postgresql, MondoDB, and Cassandra. But a cursory (~1 hour) investigation of each one failed to tell me how appropriate it was to use those tools for my task, and it's a bit discouraging that after a day of looking at difference libraries, I haven't found something which meets what I thought would be a pretty common need.
I would also love it if someone had example code for Lucene (or other system) which did this sort of task, or had enough experience in one of these tools to point out that it's not possible.