Visualization of Lattice Structure
Lattice is a special form of graph with a start node and a terminal node, and data are encoded on the paths from the start to the terminal. The key feature of lattice is common edges, which are the edges shared by multiple data-encoding paths. Lattice is widely used in the fields of speech recognition, natural language processing and bioinformatics, as common edges can be applied to compress data, to speed-up algorithms, and to discover common structures within the data. In this paper, we focus on visualization of the lattice structure, with emphasis on the common edges. In particular, we aim to build a system, which takes any lattice as input, displays the lattice structure effectively, and supports various interactions for users to either explore or edit the lattice. With such system, we wish to gain some intuition about how to build the optimal lattice from raw data, which is still an unsolved problem.
Software
Try it online here.
Short Notes about using our System
1) The first button in the tool box (on top left) is an undo button.
2) The second button in the tool box is a toggle button to change between the exploration mode and editing mode.
3) In editing mode (when the second button is in white), you can select nodes and edges and use the rest of the tool box to change the lattice structure.
One operation can be done without the buttons, which is insertion of new nodes. User can insert new nodes by dragging mouse around an existing edge, and helper information will be shown in the content box in the top right.
Relatively Longer Tutorial
1) Move mouse over edge "i", notice all the highlighted paths, and the data shown in the top right content window.
2) Move mouse over to any data piece in the content window, notice the highlighted corresponding paths.
3) Drag any node of interest and release slowly to set it fixed.
4) Drag on the background to move the entire lattice.
5) Click on edge "i". Now we ignore rest of the graph which does not contain "i".
6) Click on the very top button in the tool box on the top left side. We just undo the last operation of filtering out the graph nont containing "i".
7) Click on the second button in the tool box to enter the edit mode.
8) Drag mouse around the edge "have" to insert a new node on that edge. Notice that there is a vertical line in the content window, which indicates where to put the new node. Let's insert it between "ha" and "ve".
9) Do the same thing to the edge "hate" with split between "ha" and "te".
10) Now we have two edges with the same content "ha". Click on the two nodes inserted, they should be colored in orange to indicate the selection. Now, click on the 4th button in the toolbox to merge the two nodes.
11) Now the two edges share the same start/end node. Select the two edges, and click on the 4th button to merge the two edges.
12) Click on the node between "i" and "ha". Click on the 3rd button to remove the node.
13) Select the 3 edges resulted from the node removal, and click on the 4th button to merge them. Now, we have a more compressed lattice!
Materials
