Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
186 lines (141 sloc) 18.5 KB



Order Preserving Codes

Other Order-Preserving Structures:

Fat binary search and monotone minimal perfect hashing

Formal Concept Analysis

Incremental Computation

Weighted Datalog and Generalized Annotated Programs

Stable Models

Top-Down Evaluation


*-Semirings and C-Semirings/ω-continuous semirings

[21:27] nwf:	 Paper dump:
[21:27] nwf: is a decent overview, though a little dated
[21:28] nwf: ties a lot of this in to NLP parsing, if you're curious
[21:28] nwf: I have just skimmed and has some nice examples
[21:30] nwf: has some more graph-based examples

Provenance semirings and x-fast trees

Consistency and distribution

Latch-free architecture

Persistence and Versioning


Packed Memory Arrays

Encoding functions with static support, Monotone Minimal Perfect Hashing and Bloomier Filters

Cache-Oblivious Databases

String Dictionaries

Logging and Metrics

  • The log-structured merge tree by O'Neil, Cheng, Gawlick and O'Neil provides great throughput for inserts in exchange for high read latency for write-mostly workloads.

Compressed Search

We could store full-text-indices on some columns as a BWT transformed version of the leave chunk, then perform compressed-search techniques on top to permit efficient operations on them without paying for full decompression.

At ~4 meg leaves this actually fits pretty well with bzip2 window sizes.

Wavelet Trees and Succinct Data Structures

Compressed Computation

Batched buffer management

Succinct Tree Representations

Scheduling and Work-Stealing

Data Sets (for future demo / benchmarking)

Bloom Filters