debasishg

General Background and Overview

1. Probabilistic Data Structures for Web Analytics and Data Mining : A great overview of the space of probabilistic data structures and how they are used in approximation algorithm implementation.
2. Models and Issues in Data Stream Systems
3. Philippe Flajolet’s contribution to streaming algorithms : A presentation by Jérémie Lumbroso that visits some of the hostorical perspectives and how it all began with Flajolet
4. Approximate Frequency Counts over Data Streams by Gurmeet Singh Manku & Rajeev Motwani : One of the early papers on the subject.
5. [Methods for Finding Frequent Items in Data Streams](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.187.9800&rep=rep1&t

debasishg

#[derive(Debug)]
enum MyError {
    Io(std::io::Error),
    Parse(pest::error::Error<Rule>),
}

#[derive(Debug)]
struct StoreError(MyError);

impl std::fmt::Display for StoreError {

debasishg

Cache Oblivious and Cache Aware Data Structure and Algorithms

1. Cache-Oblivious Algorithms and Data Structures - Erik Demaine (One of the earliest papers in cache oblivious data structures and algorithms that introduces the cache oblivious model in detail and examines static and dynamic cache oblivious data structures built between 2000-2003)

2. Cache Oblivious B-Trees - Bender, Demaine, Farch-Colton (This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. One of the fundamental papers in the field where both search trees discussed match the optimal search bound of Θ(1+log (B+1)N) memory transfers)

3. Cache Oblivious Search Trees via Binary Trees of Small Height - Brodal, Fagerberg, Jacob (The data structure discussed in this paper works on the version of [2] but avoids the use o

debasishg

Basics

1. The Log-Structured Merge-Tree (LSM-Tree)
2. B-Tree vs Log-Structured Merge-Tree
3. Modern B-tree techniques
4. LSM-based Storage Techniques: A Survey

B-trees and CPU Caches

1. B-tree Indexes and CPU Caches by Goetz Graefe and Per-Åke Larson

debasishg

Trait Bounds

Trait bounds in Rust are really powerful and also offers lots of idiomatic ways to constrain your model. Bounds are for enforcing constraints even in other languages like Scala, but Rust offers them at a different level.

Here's one example from the book Rust for Rustaceans (a great book BTW).

Suppose you want to construct a HashMap<K, V, S>, whose keys are some generic type T, value is a usize, you can write bounds like T: Hash + Eq, S: BuildHasher + Default.

pub fn doit<T>(value: T)

debasishg

Abstraction and Parametricity implementing domain models in OCaml

One of my favorite comments on abstraction and parametricity ..

Parametricity can be thought of as the dual to abstraction. Where abstraction hides details about an implementation from the outside world, parametricity hides details about the outside world from an implementation.

When using OCaml as the implementation language, you abstract using ADTs (Abstract Data Types) and make your abstraction parametric using functors. And bind all of the algebras together using Modules.

Abstraction

debasishg

Algebraic Domain Modeling

When we talk about the algebra of an operation, we talk about the signature of the operation, and how, starting from the input, we can just "follow the types" to lead to the implementation of that operation.

Consider the following operation generateTrades as part of a domain service TradingService. The idea is to generate all trades that happened on the day (input to the operation) and executed by the user (input to the operation) in the back-office of a securities trading organization.

In the example below, note the following 2 principles that form the core of the algebraic modeling:

1. The sequence of steps mentioned in the specification of the method as comments and correspond one-to-one to the types of the operations used in implementing generateTrades. I have annotated the steps in the implementation below.
2. The implementation of generateTrades is completely decoupled from the implementation of the operations like queryExecutionsForDate, `getAccountNoF

debasishg

(* Modules - the signature of functions and types with no 
   implementation whatsoever. Pure interfaces. *)
module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

(* Note we don't specify any representation for the implementation of a 
   [heap]. Just the facts that define a heap - an ordered element, an 
   abstract type and a bunch of functions *)

debasishg

(* an abstract signature for instantiations of the existential quantifier *)
module type EXISTS =
sig
  (* the predicate *)
  type 'a phi

  (* the existential type *)
  type t

  (* the introduction rule *)

debasishg

package cqrs
package eventstore

import zio.*
import zio.prelude.*
import zio.prelude.fx.*

object BaseSyntax:

  type Program[S, R, E, A] = ZPure[Nothing, S, S, R, E, A]