Outlinepapersectionsection.titletitlesectionsection“experiments"exp"intro"Igorithmtitleexptitleorithmtproof"A(k)-index""1-indexaboutproofaboutuses
Outline paper section title algorithm “1-index” proof section title “A(k)-index” proof uses algorithm section “experiments” about about title section title “intro” exp exp
1-lndex: Definition Constructed by using bisimilarityDefinition based on stabilityPartition data nodes into index nodesdnode (v) and inode (I[vl)I[ul is v's index parent if u is y's parentAn inode is stable if all of its dnodes have theI[u]same index parentsuIn a 1-index, all inodes are stableI[≥]V
1-Index: Definition ⚫ Constructed by using bisimilarity ⚫ Definition based on stability ⚫ Partition data nodes into index nodes ⚫ dnode (v) and inode (I[v]) ⚫ I[u] is v’s index parent if u is v’s parent ⚫ An inode is stable if all of its dnodes have the same index parents ⚫ In a 1-index, all inodes are stable v I[v] u I[u]
1-lndex: Examplepaperpapersectionsectiontitlesection2,4,8,13sectionsectionexpexptitlealgorithmexptitlegorithm15,163,5,9,146,10algtitletiteproofabout17,18proofproofaboutaboutusesproof/paper/section/algorithmusesdata graph1-index
1-Index: Example paper 2,4,8,13 section 3,5,9,14 title 6,10 algorithm proof proof uses 15,16 17,18 about exp 1-index paper section title algorithm proof section title proof uses algorithm section about about title section title exp exp data graph /paper/section/algorithm
1-Index: Qualitypaper Assigning dnodes thatare bisimilar intosection2,42,4,8(8313different inodesdoes not affectexpcorrectness,titlealgorithm15,16 but does affect efficiency3,5,9,146,10The quality of an indexproof17,18# inodes- 1 X 100%aboutproof# inodes intheminimum1-indexusesIdeal: quality = 0%
1-Index: Quality ⚫ Assigning dnodes that are bisimilar into different inodes ⚫ does not affect correctness, ⚫ but does affect efficiency ⚫ The quality of an index # inodes # inodes in the minimum 1-index − 1 X 100% paper 2,4,8,13 section 3,5,9,14 title 6,10 algorithm proof proof uses 15,16 17,18 about exp 2,4 8,13 Ideal: quality = 0%