Posts

TelegraphCQ: Continuous Dataflow Processing for an Uncertain World (2003)

Stonebraker and Çetintemel presented “One Size Fits All” in 2005. The phrase refers to the fact that various data-centric applications use traditional DMBMS architectures to store data regardless of the characteristics and requirements of the data. In the paper, they argued that this approach was no longer applicable, with examples of streaing processing. TelegraphCQ, presented in 2003, is the first generation of databases for streamingffff data from the early 2000s.

March 22, 2024

LLaMA Open and Efficient Foundation Language Models (2023)

Scaling Laws for Neural Language Models refers to empirical observations that model test performance has a power-law relationship with each of the three scale factors: the number of model parameters, the dataset size in tokens, and the amount of compute used for training, when not bottlenecked by the other two. Hoffmann et al. (2022) investigated the bottleneck and found that, given a fixed FLOPs budget, the number of model parameters and the training tokens should be scaled equally to minimize pre-training loss. They trained a predicted compute-optimal model, Chinchilla, with 80B parameters, at the same compute budget as Gopher (280B) and with 4 times more data. Chinchilla outperformed Gopher and GPT-3 (175B) on a large range of downstream evaluation tasks.

#Large Language Model

March 14, 2024

Apache Calcite a Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources

Michael StonebrakerとUğur Çetintemel presented One Size Fits All in 2005. The title refers to the fact that traditional RDBMS had been used to implement a variety of data-centric applications. Tn the paper, they argued that the phrase was no longer applicable and predicted the rise of domain-specific database engines. Indeed, organizations leverage various domain-specific database engines such as column stores and text search engines today.

#Apache Calcite

March 10, 2024

Mining Association Rules Between Sets of Items in Large Databases (1993)

Mining Association Rules between Sets of Items in Large Databases presents one of the earliest approaches for association rules mining. An association rule is an implication of the form \(X \Rightarrow I_j\) where \(X\) is a set of some items, and \(I_j\) is an item that is not in \(X\). For instance, if transactions buying bread and butter also buy milk, that forms an association rule. The paper introduces a method to find association rules and measure confidence and support factors from transactions. The confidence factor measures how many transactions that satisfy \(X\) also satisfy \(I_j\). The support factor of an association rule is defined to be the fraction of transactions that contain the union of items in the rule. The support factor implies statistical significance of the association rule.

#Association Rule Mining

March 2, 2024

Poly-Encoders: Architectures and Pre-Training Strategies for Fast and Accurate Multi-Sentence Scoring (2019)

For tasks matching input sequences with labels, current state-of-the-art approaches focus on using BERT models for pre-training. Two common encoding approaches are Cross-encoders (Wolf et al.), which concatenate input sequences and candidate labels into a single vector, and produce candidate-sensitive embeddings, and Bi-encoders (Mazaré et al.), which encode input sequences and candidate labels separately. In Bi-encoders, the score is the dot-product of the two embeddings. While Cross-encoders are more accurate than Bi-encoders, Bi-encoders are faster.

#Transformer

February 24, 2024

THE DESIGN OF POSTGRES (1986)

The preliminary design of POSTGRES was presented in The Design of Postgres. According to Brief History of Postgres, the data model, rules, and storage system were separately described in different papers: The Postgres Data Model, The Design of the Postgres Rule System, and The Design of the Postgres Storage System.

POSTGRES is the successor to the INGRES relational database system. The main design goals of POSTGRES were to support complex objects, simplify the DBMS code for crash recovery, and utilize optical disks while making as few changes as possible to the relational model.

February 17, 2024

Retrieval Augmented Generation for Knowledge Intensive NLP Tasks (2021)

While large pre-trained language models (LLMs) can implicitly store factual knowledge in their parameters, their ability to access explicit encyclopedic and commonsense is knowledge still limited. Retrieval Augmented Generation (RAG) is a method to improve language generation by providing external explicit knowledge to LLMs.

#Retrieval Augmented Generation

January 27, 2024

Sorting networks and their applications (1968)

A sorting network is a network of comparison elements with 2 indegree and 2 outdegree that sorts a list in ascending or descending order. A comparison element receives two numbers and outputs the smaller one to one output and the larger one to the other output. Odd-even merging networks and Bitonic sorters are sorting networks proposed in Sorting networks and their applications. They can sort \(2^p\) elements with \(\ln (\frac{1}{2})p(p+1)\) steps. Their processing is independent of the values and is easy to run on the GPU because it does not change the output location in memory based on input data values.

#Sorting Algorithm

January 14, 2024

Billion Scale Similarity Search With GPUs (2017)

The paper Billion-scale-similarity search with GPUs presents an approximate nearest-neighbor search method that uses GPUs and combines the IVFADC indexing structure with Batcher’s bitonic sorting network. The authors have implemented this method in a library called faiss.

#Approximate Nearest Neighbors

January 1, 2024

Conflict-free Replicated Data Types (2011)

In a distributed system with replicated objects distributed across processes interconnected by an asynchronous network, updating a replica without synchronization can lead to conflicts when the update is sent to other replicas. Conflict-free Replicated Data Types (CRDTs) are data structures whose states form a join semilattice and monotonically non-decreasing across updates. The replicas of CRDTs that have delivered the same updates eventually reach the same state if clents stop submitting updates.

#Conflict-Free Replicated Data Types

December 31, 2023