Mining Precision Interface From Query Logs》是SIGMOD2019所接收到的papers當中的一篇。

花了大概4天時間閱讀，全英文的paper讀起來還是有點吃力的，不過好在大部分還是能看懂。下面寫寫自己的學習筆記：

摘要（Abstract）

摘要其實就能概括整個文章所要解決的問題或者提出的一種新技術：可視化交互工具讓數據分析越來越有效，并且對普通大眾也更加的友好。但現有的界面大部分都是針對特定任務的界面，沒有針對每個用戶每個任務的交互界面。作者提出了一種基于查詢日志生成定制界面的一種方法。這種方法經過實驗，可以改進現有界面的交互設計，并且與手工制作的界面可以媲美。

1 介紹

此部分開始引入，即提出問題的背景，介紹了一些現有的交互界面，例如用戶可以通過使用Google的股票走勢可視化交互界面的時間過濾器了解一段范圍內的股票趨勢。但相同的界面對市場分析員分析數據就不適合。總之，此段說明數據分析背景下交互界面的重要性。交互界面的有效性取決于該構成界面的程序集合（程序集合也就是可以改變查詢操作的相關程序的集合）是否與用戶想要表達的查詢操作匹配。

設計界面有兩個傳統上由專家解決的挑戰：一是確定與給定任務相關的程序集，二是開發能表達該任務的交互界面。作者舉例Tableau可視化數據分析工具，軟件開發者花費大力氣開發的工具卻不是對每種任務都有效。接著引出作者在此方面的嘗試：提出用query logs作為生成交互界面的API，因為很多數據處理系統可以自動捕獲logs。然后作者又舉了兩個關于用從logs生成界面的實例。

?基于上面所述，作者提出本文主題：精確界面，即一種可以從query logs自動生成對確定任務的交互界面的工具，它以logs作為輸入，生成一組web交互應用程序來表達logs中的查詢。它通過把queries轉換成語法樹，利用樹的結構的變化，把相同的變化映射成界面中的組件。

?要開發這樣的精確界面工具，作者提出了三個挑戰：

（1）要為queries和interfaces建立統一的數學模型，這種模型的適用范圍要廣，支持用戶首選項，并且操作性要好

（2）要找到一種可以識別和過濾出 有意義的樹結構改變 的方法，因為并不是所有的結構變化都是有意義的，若把所有結構變化都映射到交互界面會導致界面不可用。

（3）要定義約束和啟發式規則來快速找到good solution和縮小 size of logs，因為對query logs中的查詢可以生成交互界面的解空間是以指數級增長的。

?

針對上面的三個挑戰，作者提出如下解決方案：

（1）將問題形式化，問題定義對任何語法定義良好的語言和交互組件都是通用的。

（2）提出一種叫做PILANG的語言來確定重要的結構變化。這可以幫助生成交互圖。交互圖中每個頂點都是一個query，每條標記的邊都是用PILANG語句標識的結構變化。

（3）把界面構建問題映射成交互圖的邊的生成問題，用啟發式算法快速解決問題

（4）最后對該工具進行評估，該生成工具表現優秀

?

2 概述

本部分概述精確界面的建立過程以及在后序過程過程中要設法解決的技術挑戰。

選用query logs作為API的原因：因為logs詳細的記錄了分析人員實際執行的分析操作（也就是分析時用到的查詢操作），并且logs能從很多源頭獲得。而且現代數據處理引擎已經應用這種 log 機制來進行恢復和調試，這種方式在現代工業和研究中也非常普遍。

作者把生成界面問題分解完成兩個子任務：

（1）找到不同查詢語句 形成的語法樹 之間的結構變化

（2）把這些變化映射到界面中去

解決這個問題很困難，原因有：用戶交互可能表達的范圍不受限（不同用戶使用不同的查詢語句，千差萬別），很容易導致不可用的界面。針對問題，作者提出解決方案：

① 限制語法樹結構變化的復雜性，提供簡單的機制來指定 有意義的結構變化

② 系統要很容易適應新的編程語言和新的交互組件（例如變成了觸屏）

基于上面這些內容，作者把精確界面生成過程分為三個步驟：

（1）Representation Canonicalizer：把查詢語句序列 轉換成 規范化的語法樹（AST）結構

（2）Interaction Miner & Distiler：基于有序樹匹配算法識別 AST之間的結構變化，然后形成交互圖，使用PILANG來簡化圖，指定重要的結構改變。

（3）Interaction Mapper：把交互圖中的邊的集合 映射到界面中的交互組件。因為問題是NP困難，采用啟發式算法找最優解，然后將生成的界面 組合成一個 web交互應用程序。

作者進行了一些假設：

（1）假設知道每種語言的語法，有可以將 程序源代碼 變成 AST的分析器，有將 AST 解析為 源代碼的解析器，以及 可以知道哪些結點是集合 哪些是文本的 結點類型注釋

（2）核心假設：假設query logs中大多數語法變化是增量的，因此可將 查詢結構變化 映射到 交互界面的組件

（3）不存在邏輯依賴

（4）最后，設定兩個函數exec（）和render（）；exec（）函數執行生成查詢AST，render（）函數將SQL查詢日志可視化輸出?

?

3 對交互進行建模

本部分描述query logs和交互的形式化模型，其要點是把交互（不同的查詢語句）建模成樹型的轉換，因為這可以把結構差異和用戶操作界面的組件直接聯系起來。AST - >? weidget。下面進行建模：

?

（1）輸入部分：query logs plog被建模為 ：

為了支持多種編程語言，依賴語言的語法和解析結構，不依賴語義

?

（2）將一個 通過分析器（）抽象成語法樹AST，假設樹中每個結點都有自己的 ，一系列屬性，和一個有序的孩子結點列表。此外，還假設存在一個表來表示? 葉子結點映射到基本數據類型的方法 ；結點類型就是子表達式列表的結點類型。如圖：

?

（3）假定邏輯表達式被規范化為合取范式，將ANDs of? ORs 化為一個邏輯表達式列表 而不是復雜的二叉樹結構。這減少了向邏輯表達式中添加表示式時? 可能導致的 樹對齊錯誤 問題。

?

接下來就是找成對AST樹之間的差異，作者使用了快速有序樹匹配算法，當匹配兩個樹之間的節點時，它保留了祖先和從左到右的兄弟關系。算法流程如下：

（1）先計算出兩棵樹的先序遍歷序列

（2）當一對結點匹配時，繼續進行下一對結點的匹配；如果不匹配，則回溯到最近匹配的一對結點然后嘗試與其他候選結點進行匹配。這個結點的復雜度是

：樹的大小

：葉子的數量

：樹的深度

?

?

將一個查詢集合中所有成對AST樹之間的差異 組成一個差異表 ，通過將 ， 設置為null，可以表示AST的增加和刪除

：對? 的外鍵引用

：兩棵子樹唯一的不同路徑

，：不同的兩棵子樹

?

交互建模：

交互（此處的交互可以說是用戶使用界面時可以進行選擇的地方）是對 中記錄的一種抽象，這些記錄表示在查詢結構更改時 改變所在的位置和示例。因此，為交互 建立樹轉換函數：

此函數的意思：這個交互 ? 通過 在兩棵子樹結構開始變化的結點處 用一棵新子樹替換，來把查詢 的AST樹轉成另一個查詢 的AST樹

然后這個差異表 就可以組成一個交互圖，每個結點是一個查詢 ，邊 是由交互（兩棵不同AST樹之間的變化） 標識的。

?

界面的閉包：給定一個交互界面，：初始查詢的AST樹，：一系列交互組件。

用中的每個小組件 持續的 把當前查詢轉換成下一查詢 。

通過把所有組件的可能組成序列 應用到其初始查詢，形成界面閉包 （所有能由初始查詢轉換而成的 最終查詢的界面集），這些操作由 函數和 函數執行。

把小部件 看成 小部件類型 的一個實例。一個部件類型 包括一個值域 ? 和 一個代價函數 ，它衡量 對給定的域 ，該部件類型是否合適的程度。

一個小部件 是部件類型 的一個實例，它由一個確定的域? ?? 以及 一個用小部件的狀態來修改程序的規范來確定。 這個規范通過一個交互（查詢結構的變化） 和 一個模板函數 （這個 就是變化發生處的子樹）確定。

模板函數將元素 映射到子樹 ，子樹 可以作為交互的參數進行傳遞。

讓 為當前小部件的狀態，然后應用此部件到當前的查詢等價于：

因為精確界面的操作是在語法層面進行操作，某些AST轉換的組合可能會導致不可用的查詢（語義不正確）。

針對這種情況，作者提出了兩種解決方案：（1）在 中有預見性地執行查詢（2）在可視化界面上不允許出現能轉換出這些AST的操作

?

還有一個問題：很多界面可以表示相同的查詢，為了對界面進行排序，以選出最優的界面，需要定義一個代價函數來評價這些界面。為了靈活地支持 對界面從不同方面進行度量，允許開發人員對部件類型指定多個代價函數。

部件類型 的代價函數定義為：??

其中： ：開發人員為第? 個組件類型定義的代價函數； ：該代價函數的權重

?

對于界面 ，通過衡量 部件的代價函數的和 來估計界面的復雜性：。

在許多情況下，用一個界面表示所有的查詢并不是最優方法。例如，假設一個查詢日志中只有兩個查詢 {} ，但這兩個查詢彼此有很大的差異。有兩種方法：（1）生成一個復雜界面， 就是表達 之間復雜轉換的小部件。（2）分別生成兩個界面 ，分別表達不同的查詢。

為了能夠支持這種復雜性，作者建立界面集 ，界面集的復雜性由每個界面的代價和來估計：，是每個新界面的常量代價。作者還建立了界面閉包的閉包來表示界面閉包的集合：

?

有了上述定義，就可以定義最終要解決的問題了：

PROBLEM1：給定一個查詢日志 ，一個評價查詢覆蓋率的閾值 ，和每個代價函數的權重 ，生成最優界面集合 ：

• is minimal

本文的目標是：找到一個界面最小結合，它的閉包中包含給定比例 的查詢

作者又重述解決問題的兩個步驟并給出了解決思路：

（1）分析日志，識別有意義的結構變化；如果直接用 表，會導致復雜的界面生成，因此作者用PILANG語句進行過濾。

（2）將結構變化部分映射到界面的部件：通過確定每個部件的 來映射。后續作者提出一種把界面生成問題建模成子集覆蓋問題進行求解的方法。

?

小結：

本文作者希望開發一種針對特定任務能夠生成精確可視化交互界面的工具。該工具通過分析查詢日志 生成交互界面。查詢日志記錄著分析人員的操作，從中發現查詢語句之間的變化（變化就是一種交互），將這種變化建模為語法樹之間結構的變化。通過將變化映射到界面的相關部件，實現可視化界面操作，方便分析人員操作。

是第二遍看文章，讀的過程中會發現很多第一遍沒有注意到的東西。所以，好的文章值得多讀幾遍~

?

2019.8.18

文中出現的綠色字體是今天對這篇文章的新的理解

?

?

?

總結

以上是生活随笔為你收集整理的Mining Precision Interface From Query Logs -- 学习笔记（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。