cooccur

A fast CLI for indexing large TSV/CSV files and exploring exact co-occurrence relationships between column values — given filters on some columns, which values show up in the matching rows under the other columns, and how often?

It is field-agnostic: it does not care whether your columns are users, IPs, devices, hashes, or accounts. Build an inverted index once, then pivot, search, and aggregate over co-occurrence — useful for entity resolution, log and dataset exploration, and finding which values cluster together. Deterministic output, recorded provenance, a JSON API, and an optional in-memory daemon.

cargo build --release
./demo.sh          # build an index over the bundled sample and run a short tour

Core data model

• A category is a TSV column name.
• A node is (category, value).
• Each row is a hyperedge connecting all nodes it contains.
• Queries answer: given filters on some categories, what values appear in the matching rows under the remaining categories, and how often?

The index is built from three flat structures:

(category, value) → value_id         dictionary
value_id          → sorted [row_id]  inverted index (postings)
row_id × cat_id   → value_id         row store (flat matrix)

Pairwise adjacency between values is never precomputed.

---

Build

cargo build --release
# binary is target/release/cooccur

---

Commands

1. Build an index

cooccur build \
  --input data/sample.tsv \
  --index ./my_index

Multiple input files are merged under a union of all their column names:

cooccur build \
  --input file1.tsv \
  --input file2.tsv \
  --index ./my_index

--input also accepts a directory or a quoted glob pattern. Directory inputs include regular files from that directory's top level in sorted order:

cooccur build --input ./daily_tsv --index ./my_index
cooccur build --input "/path/to/tsv/stat_*.tsv" --index ./my_index

Duplicate column names within a single file's header are rejected with an error.

CSV input

Files with a .csv extension are parsed as RFC 4180 comma-separated values automatically. Use --input-format to force a format regardless of extension:

cooccur build --input data.tsv --input extra.csv --index ./my_index
cooccur build --input-format csv --input weird_extension.dat --index ./my_index

--input-format accepts auto (default), tsv, or csv.

Provenance

Every build records the source files' paths, SHA-256 hashes, row counts, formats, and timestamps in meta.json. Subsequent update calls append an update record. Use inspect (see below) to read provenance.

Index files written:

File	Contents
meta.json	Category names, row/value counts
values.bin	Dictionary: [cat_id u32][len u32][utf8 bytes] per value
row_store.bin	Flattened u32 matrix: row_id × num_categories
postings.bin	Concatenated u32 row-ID arrays
postings_offsets.bin	Per-value [byte_offset u64][count u32] pointers into postings.bin
lowercase_values.bin	Derived (category, lowercase value) → value_id[] map for case-insensitive predicates
trigram_values.bin	Derived (category, lowercase trigram) → value_id[] map for case-insensitive substring predicates

---

2. Query co-occurrences

Exact filters (legacy category=value syntax)

cooccur query \
  --index ./my_index \
  --filter ip=1.2.3.4

Expected output for the sample dataset:

Matched rows: 3

[user_id]
  u1  1
  u2  1
  u3  1

[email]
  a@example.com  1
  b@example.com  1
  c@example.com  1

[device_id]
  d1  2
  d2  1

Extended filter syntax: exact / substring / regex

Filters can optionally specify a match mode using category:mode:pattern:

# exact — same as category=value
--filter email:exact:a@example.com

# substring — match any dictionary value containing the string
--filter email:substring:example.com

# regex — match any dictionary value matching the pattern
--filter 'email:regex:.*@example\.com$'

Within a category, multiple filters are OR-ed:

cooccur query \
  --index ./my_index \
  --filter user_id=u1 \
  --filter user_id=u2
# → user_id ∈ {u1, u2}

Across categories they are AND-ed:

cooccur query \
  --index ./my_index \
  --filter 'email:substring:example.com' \
  --filter ip=1.2.3.4
# → (email matches "example.com") AND (ip = "1.2.3.4")

Safety limits for non-exact filters

--max-filter-values 10000   # abort if a filter resolves to more values (default: 10 000)
--max-rows-scan 1000000     # abort if matched row count exceeds this (default: 1 000 000)

If a substring or regex filter matches too many dictionary values the command aborts with a clear error:

Filter email:substring:. matched 52341 values, exceeding --max-filter-values=10000.
Please narrow the filter or increase the limit.

Show filter diagnostics

cooccur query \
  --index ./my_index \
  --filter 'email:substring:example.com' \
  --show-filter-matches

Prints how many dictionary values each filter matched (with up to 5 samples) before the co-occurrence results:

Filter matches:
  email substring "example.com": 2 values
    a@example.com
    b@example.com

Matched rows: 2
…

In --json mode this appears as a filter_matches key in the output object.

Note: category-less query filters are not supported

Query filters must always specify a category. For category-less discovery use search (see below), then feed the found values back as explicit filters.

Other query options

--top-k 100                       # max values per output category (default: 50)
--include-category email          # show only these output categories
--exclude-category raw            # suppress a category from output
--max-output-values-total 500     # cap total output values across all categories
--json                            # emit JSON (schema v1 envelope)

--max-output-values-total

Caps the total number of output values across all categories. Categories are filled in index order until the budget is exhausted; remaining categories are dropped. A WARNING: OUTPUT_TRUNCATED line (or warnings array in JSON) indicates truncation occurred.

JSON output (schema v1 envelope)

cooccur query --index ./my_index --filter ip=1.2.3.4 --json

{
  "schema_version": 1,
  "command": "query",
  "index": {"path": "./my_index", "format_version": 1, "num_rows": 3, ...},
  "request": {"filters": ["ip=1.2.3.4"], "top_k": 50, ...},
  "data": {
    "matched_rows": 3,
    "output_values_total": 6,
    "truncated": false,
    "results": {
      "user_id": [
        {"value": "u1", "count": 1},
        {"value": "u2", "count": 1},
        {"value": "u3", "count": 1}
      ],
      "device_id": [
        {"value": "d1", "count": 2},
        {"value": "d2", "count": 1}
      ]
    }
  },
  "warnings": [],
  "stats": {"elapsed_ms": 4.2}
}

All JSON output uses this schema-version-1 envelope. List orderings are deterministic — sorted by (category, value) unless a different sort is requested — so output is stable and diffable across runs.

---

3. Search the dictionary

Search within one category

# substring search
cooccur search --index ./my_index --category email --substring example.com

# exact lookup
cooccur search --index ./my_index --category user_id --exact u1

# regex
cooccur search --index ./my_index --category email --regex '.*@example\.com$'

# limit results
cooccur search --index ./my_index --category email --substring com --limit 20

Output is a plain list of matching values.

Search across all categories (omit --category)

If --category is omitted the dictionary is scanned across all categories and results are grouped by category name:

cooccur search --index ./my_index --substring example.com

Found 2 values

[email]
  a@example.com
  b@example.com

--limit applies to the total number of results across all categories.

Sort order

--sort category-value   # default: (category, value) — deterministic, diffable
--sort row-count-desc   # by row_count descending, then (category, value)

Search always collects all matches first, sorts, then applies --limit. This ensures the limit never affects which items appear — only how many are shown.

JSON output (schema v1 envelope)

cooccur search --index ./my_index --substring example.com --json

{
  "schema_version": 1,
  "command": "search",
  "data": {
    "matches": [
      {"category": "email", "value": "a@example.com", "row_count": 500},
      {"category": "email", "value": "b@example.com", "row_count": 300}
    ],
    "result_count": 2,
    "truncated": false
  },
  "warnings": [],
  "stats": {"elapsed_ms": 1.0}
}

row_count is the number of rows that contain that value.

---

4. Update an existing index

Append new TSV files to an existing index without re-building from scratch.

cooccur update \
  --index ./my_index \
  --input new_data.tsv

Multiple new files:

cooccur update \
  --index ./my_index \
  --input jan.tsv \
  --input feb.tsv

Schema evolution

• Same columns: new rows are appended directly.
• Subset of existing columns: missing columns are stored as NULL_VALUE (not shown in query output).
• New columns: the new categories are added to the index. All existing rows receive NULL_VALUE for the new columns. NULL_VALUE is never surfaced in query or search output.

Example: index built from a file with user_id, email; update adds a file with user_id, email, country:

cooccur update --index ./my_index --input with_country.tsv
# → category "country" is added
# → old rows: country = NULL (not shown)
# → new rows: country = real value

cooccur query --index ./my_index --filter country=US
# → only returns rows that have country=US

Atomic save

The update writes to a temporary directory (<index>.tmp_update), then rotates atomically:

<index>            → <index>.bak   (backed up)
<index>.tmp_update → <index>       (promoted)

If the write fails, the original index is untouched.

# keep backup (default)
cooccur update --index ./my_index --input new.tsv

# remove backup after success
cooccur update --index ./my_index --input new.tsv --no-backup

---

5. Inspect index metadata

Print category statistics and provenance information.

cooccur inspect --index ./my_index

Index: ./my_index
Rows: 100000  Categories: 4  Values: 25000

Built: 2024-01-15T10:00:01Z  Tool: cooccur 0.1.0
Sources (1):
  data.tsv  sha256=e3b0c44298fc1c14…  100000 rows  tsv  2024-01-15T10:00:00Z

[user_id]  1000 values  0 null rows
  alice    500
  bob      300
  … (1000 total values)

[email]  990 values  10 null rows
  …

Options:

--top-values-per-category 20  # (default: 10)
--no-top-values               # skip the per-category value listing
--no-provenance               # skip provenance section
--json                        # emit JSON (schema v1 envelope)

---

6. Explain a query (dry run)

Analyse filters and estimate matched rows without computing full aggregation.

cooccur explain-query \
  --index ./my_index \
  --filter 'email:substring:example.com' \
  --filter ip=1.2.3.4

Explaining query against ./my_index (100000 rows)

Filter 1: email:substring:example.com
  Matched values: 2
  Top sample values:
    a@example.com  (500 rows)
    b@example.com  (300 rows)

Filter 2: ip:exact:1.2.3.4
  Matched values: 1
  Top sample values:
    1.2.3.4  (800 rows)

Matched rows: 600 (exact)

No suggestions.

Options:

--max-filter-values 10000   # report would_exceed if filter expands beyond this (default: 10000)
--max-rows-scan 1000000     # report would_exceed if intersection is too large (default: 1000000)
--sample-values 5           # how many sample values to show per filter (default: 5)
--json                      # emit JSON (schema v1 envelope)

explain-query always computes the full row intersection so that matched_rows is exact. No aggregation is performed, so it is significantly cheaper than query for wide datasets.

---

Empty values vs. missing columns

Situation	Stored as
Tab-separated empty field \t\t	Empty string "" — a real value with its own value_id
Column absent from this file's header	NULL_VALUE — never shown in output

These are distinct. An empty-string value will appear in query aggregation counts; NULL_VALUE will not.

---

Limitations and future work

Scalability limits (PoC)

Dimension	PoC limit	Widening path
Rows	~4 billion (u32)	Widen RowId to u64; update binary formats
Unique values	~4 billion (u32)	Same as above
RAM during build	Full dictionary + postings in memory	External-sort (value_id, row_id) pairs; merge on disk
RAM during query	Full row_store + postings in memory	mmap row_store.bin; lazy-load postings by value_id
Update	Full index rewrite on every update	Segment-based immutable index (see below)
Substring/regex filter	Linear dictionary scan per category	Trigram index (see below)
Large non-exact filters	Can produce expensive OR sets	--max-filter-values guard + trigram index

Planned improvements

• Segment-based immutable index — write immutable "segments" on each update; merge offline. Eliminates full-rewrite cost and enables streaming ingestion.

• Memory-mapped row store — replace Vec<ValueId> with memmap2::Mmap so the OS pages in only touched rows during queries.

• RoaringBitmap / hybrid postings — posting lists shorter than ~128 entries remain plain Vec<RowId>; longer lists become RoaringBitmap for 4–10× compression and fast bitwise operations.

• Trigram index for substring/regex — index (category_id, trigram) → sorted Vec<ValueId>; replaces linear scans with O(k log n) candidate retrieval.

• External sort for large builds — emit (value_id, row_id) pairs to disk, external-sort, merge; keeps build RAM proportional to dictionary size rather than total data size.

• Delta + varint encoding for postings — typically 3–5× size reduction over raw u32 arrays.

• Galloping intersection — use exponential search when one posting list is much shorter than the other, reducing comparisons from O(|a|+|b|) to O(|a| log |b|).

---

License

MIT — see LICENSE.