2020八月·粉身碎骨浑不怕

题记

千锤万凿出深山,烈火焚烧若等闲。
粉骨碎身浑不怕,要留清白在人间。

《石灰吟》于谦

计划

  • 继续阅读PAIP和Logic of Science
    • PAIP完成STUDENT
    • Logic of Science到第八章
  • 整理SIGMOD2020的论文,并选择2篇进行分析阅读
    • BinDex: A Two-Layered Index for Fast and Robust Scans
    • SuRF: Practical Range Query Filtering with Fast Succinct Tries (趁机研究下Trie和它的算法分析)
  • 希望可以把体重控制到78kg以下,并提升摔跤技术

总结(2020.08.31)

  • PAIP完成度很满意,跳过了一些无趣的章节,完成了微积分的程序。不过这些技术还都是解释器的技术。
  • Logic of Science后期花费的时间不够多,开始重头捋细节
  • 论文这两篇都看不下去,没有发现有趣的论文,也没有回顾经典的论文。这方面有所欠缺。
  • 体重别提了,我爸来北京后,饭局不断,9月背水一战,必须成功。。。。
  • 摔跤技术应该有提升,赢了苏正红和龙哥几下,不排除他们让我的,但是有进步。肘关节伤病实在让人烦。

Eliza in Erlang

Introduction

This is Chapter 5 of the book PAIP. It implemented an early-day algorithm to dialog with a machine. It had the appearance of AI, but actually it was just another interpreter: programmer designs some rules at first, and then eval the user’s input. The main topic is pattern-match programming.

Pattern-match is really my favorite language feature. Erlang and many functional programming languages (Oz, ML, …) support it quite well. C language offers switch statement which can only match constant expression in each clause. Different languages may have different scopes for pattern variables.

Continue reading →

GPS in Erlang

The book PAIP

GPS is the acronym for General Problem Solver. The book Norvig, Peter. Paradigms of artificial intelligence programming: case studies in Common LISP. Morgan Kaufmann, 1992 spent the whole Chapter 4 to show how you can program a GPS using common lisp and pointed out several “bugs” that you should pay attention to. This is a great book that I highly recommend it.

Since EOPL, I am convinced that Erlang is a very good language to implement other language or write AI paradigm program. My several projects are:

More details on Common Lisp implementation can be found in the open-source repo: https://github.com/norvig/paip-lisp.

Continue reading →

Volatile Functions in Query on Broadcast-like Relation in Greenplum

Some background knowledge

Greenplum is MPP database. The SQL query’s planning and executing model is a distributed computing model. Greenplum introduces the concept of locus to model a path’s data distribution.

  • Function scan of generate_series is General locus (because the information is complete  at every single place, but in Greenplum 5 this function is not treated as General, this may be the historical reason)
  • the scan path of a replicated table is segmenteGeneral locus (because data only stored in segments, not master, and the information is complete at every single segment)
  • ……

For more details, please refer to one of my talk Greenplum 查询优化器关键技术介绍.

Continue reading →

CM (count min) is not MC (min count)

Papers and stories

This month, my most spare time has been spent on the problem Cardinality Estimate. When I finished the analysis of hyperloglog (see the blog A Tour of Understanding Hyperloglog), I just remember a recent paper of SIGMOD2019: Approximate Distinct Counts for Billions of Datasets. Its idea is to combine CountMin and Hyperloglog. Before diving into that paper, I decide to study CountMin. Another paper on cardinality estimate survey is VLDB2017’s Cardinality Estimation: An Experimental Survey mentioned a method called MinCount.

CM sketch was introduced by the paper: An Improved Data Stream Summary: The Count-Min Sketch and its Applications. I do not want to dive into that paper, but just reword the proof here (maybe in a better way).

Continue reading →

2020六月·时穷节乃见 一一垂丹青

题记

天地有正气,杂然赋流形。下则为河岳,上则为日星。於人曰浩然,沛乎塞苍冥。

皇路当清夷,含和吐明庭。时穷节乃见,一一垂丹青。在齐太史简,在晋董狐笔。

在秦张良椎,在汉苏武节。为严将军头,为嵇侍中血。为张睢阳齿,为颜常山舌。

或为辽东帽,清操厉冰雪。或为出师表,鬼神泣壮烈。或为渡江楫,慷慨吞胡羯。

或为击贼笏,逆竖头破裂。是气所磅礴,凛烈万古存。当其贯日月,生死安足论。

地维赖以立,天柱赖以尊。三纲实系命,道义为之根。嗟予遘阳九,隶也实不力。

楚囚缨其冠,传车送穷北。鼎镬甘如饴,求之不可得。阴房阗鬼火,春院闭天黑。

牛骥同一皂,鸡栖凤凰食。一朝蒙雾露,分作沟中瘠。如此再寒暑,百疠自辟易。

哀哉沮洳场,为我安乐国。岂有他缪巧,阴阳不能贼。顾此耿耿存,仰视浮云白。

悠悠我心悲,苍天曷有极。哲人日已远,典刑在夙昔。风檐展书读,古道照颜色。

《正气歌》—— 文天祥
Continue reading →