TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 12, No. 8, August 201 4, pp. 6332 ~ 6337   DOI: 10.115 9 1 /telkomni ka. v 12i8.585 4          6332     Re cei v ed Fe brua ry 24, 20 14; Re vised  Ma rch 26, 20 14; Accepted  April 15, 201 4  A Complete Lattice Lossless C o mpression Storage  Model       Zhi Huilai  Schoo l of Com puter Scie nce  and T e chno log y , He nan Po l y t e chn i c Univ ersi t y ,  Jiaoz uo He na n  P.R.China, + 8 6-03 91-3 9 8 7 7 1 1   email: zh ihu ila i @ 12 6.com       A b st r a ct   In this  pap er, a  co mpl e te  lattic e  loss less  co mpressi on stor a ge  mode l is  pr opos ed t o  i m prove th e   storage  efficie n cy. In ord e r to bu ild  the  pro pose d   mo del, f i rst all th e u p p e r an d l o w e r ir reduc ibl e  e l e m ents   of the co mpl e te lattice ar e id entifie d resp ectively, t hen  an i s omorp h ic  ma ppi ng for m  the  compl e te lattic e  to   a conc ept lattic e  is fou nde d, a nd fin a lly  a  ma trix is  used to  store the for m al co nt ext of the conc ept lattic e .   Co mp ared w i th  using a d j a cent  matrix, exa m p l e an d  an alysis  show  that the pr op osed  meth od can i m prov e  the storage  efficiency of co mp lete lattice.      Ke y w ords : Lat tice theory, co mp lete L a ttice, irreduc ib le el e m e n t, lossless  compressi on st orag e      Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Lattice de scri bes the pa rtial orde r relat i ons bet wee n  objects, an d  is widely used in  obje c t clu s tering and hi era r chi c al  stru ct ure an alysi s . In rece nt years, lattice theory, especi a lly  the complete  lattice the o ry, is used i n  many  fiel d s , such a s   grap h q ueryi ng [1], situat ion   hiera r chy ma nipulate [2],  metaboli c  pat hway a nalys i s  [3], set-val u ed varia b le re pre s entatio n [4],  and  so on. I n  theoretical  resea r ch, adjacen cy  ma trix as the  storage  model  is acce ptabl e.  Ho wever,  in  re al a ppli c ations the l a ttice   u s u a ll y  contai ns nume r ou s n ode s  a nd h a s a   compli cate d  stru cture. At t h is  ci rcumsta n ce,  adja c e n c y mat r ix a s   the sto r a ge  model  will  co st a   lot of stora g e  spa c e  and i s  not co ndu cive to lattice re trieval and l a ttice isomo r ph ism jud g ment .  Lattice sto r a ge is no lo n ger a in sig n ificant p r obl e m , but a key theoreti c al i s sue s  of pra c tica l   appli c ation va lue.  Formal  Concept Analysis  (FCA) after being prod uced by professor R.  Wille [5], its core  stru cture con c ept  l a ttice h a s attra c ted broa d  a ttenti on a nd  bein g  used i n  va rious field s . A s  its  uniqu e adva n tage s in da ta analysi s  a nd kno w ledg e system  de velopment, it has  be com e   a   means for ex ternal  recognition [6]. For  this reason, i n  th is  arti cle we will  propose a compl e te  lattice sto r ag e model ba se d on the theo ry of FCA.      2. Preliminaries  Before  pro c e eding,  we  bri e fly re call the  lattice te rmin ology a nd  propertie s [7], a s   well   a s   fundame n tal definition s  in FCA [8, 9].    Definition  2.1 .  Let  P be a   se t. An order o n   P is a  bin a ry  rel a tion    s u ch that, for all  ,, x yz P ,  (1)  x x ,  (2)  x y  and  yx  imply  x y ,  (3)  x y  and  yz  imply  x z .  These condi tions a r e  re ferre d to, re spe c tive ly, as reflexivity, anti-symm e t ry and   transitivity.  Definition 2.2 .  Let  P be an o r dere d  set an d let  , x yP . We say x is cove red  b y   y  (or y cov e r s x ), and  write  x y  or  yx , if  x y and  x zy implies  zx . More over,  x is  calle d the lower neig hbo r o f y and y is calle d the upp er nei g hbor of  x .  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Com p lete Lattice Lo ssl ess Com p ressio n Storage Mo del (Zhi  Huilai )   6333 Definition 2.3 .   Let  P be an  o r de red  set a n d  let  SP . An ele m ent  x P is an u pper  boun d of  S if  sx  for all  sS . An lowe r bo und i s  d u a lly. The set of all upp er  b ound s of  S  is  denote d  by  u S  and the set of all lowe r bou nds by  l S :  {| ( ) :} u Sx P s S s x   and  {| ( } : ) l Sx P s S s x  .  If  u S has a le ast  element  x , the n   x  is called th e least up per  boun d of  S . Dually, if  l S has a g r eate s t element  x , then  x  is call ed the gre a test lo wer b oun d of  S .  The lea s t upp er bo und of  S is also  called t he su pe rmum  of  S and is de n o ted by su p  S ; the greate s t lowe r bou nd  of  S is also  call ed the infimu m of  S and is d enoted by inf  S .  Notation 2.1. We write  x y in place of su p , x y  when it exists and  x y  in place o f   inf , x y when it exists. Similarly, we write  S  and  S  instea d of sup  S  and inf  S . I t  is   sometim e s  n e ce ssary to i ndicate that the join  or m e et is bei ng fo und in  a pa rticula r  o r de red  set   P , in which  case we write  P S  or  P S .  Definition 2.4.  Let  P be an no n-em pty orde red set.  (1) If  x y  and  x y  exis ts  for all  , x yP , th en  P is called a  lattice;  (2) If  S  and  S  exis ts  for all  SP , th en  P is  called a  c o mplete lattic e .   Definition 2.5.  Let  L  be a lattice. An eleme n ts  x L is join-irreduci b le if  (1)  0 x  (in ca se  L  has a  zero)  (2)  x ab   implies  x a  or  x b  for all  , ab L .  A meet-irredu cible el ement  is defined d u a lly.  Definition 2.6 .  Let  P be an ordere d  set an d  QP . Then  Q  is called join-dense in  P if for every element  aP there  is a sub s et  A  of  Q  such that  P aA . The dual  of join - den se is me e t -den se.   Definition  2.7 .  A context i s  a t r iple  ,, KG M I  where   G  and  M  are  sets and   I GM  . The eleme n ts of  G  and  M  are  calle d ob jects  and attributes  re spe c tively. As  usu a l, instea d of   , gm I  we write   gIm  and say ‘the  object g ha s  the attribute  m’.   Definition  2.8 .  Given a fo rmal context  ,, KG M I , the de rivatio n  functio n s  . f and  . g  are defin ed for  A G  and  B M  as  follows :    {| } : f Am M g A g I m  ; {| } : gB g G m B g I m  .  Definition 2.9 .  A formal concept of formal co ntext  ,, KG M I  is a pai r   , A B ,  whe r e  A G ,  B M ,   f AB , and  gB A .   A con c ept   , A B  is sub c on ce pt of  , CD  if  A C  (eq u ivalently,  DB ). In thi s   ca se,    , CD  is call ed a su pe rco n ce pt of  , A B . We write  ,, A BC D  and  define the   relation s  ,  , and   as u s ual.    The  set of all  con c e p ts  ordere d  by the   relation    forms a l a ttice, which i s   denot ed by    LK  and call ed th e con c e p t lattice of the co n t ext  K . The rel a tion define s   the coveri ng  graph   of   LK .              Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 8, August 2014:  633 2 –  6337   6334  3. Complete  Lattic e  Stor age Model Based on F C A   Definition 3. 1. Let   ,, KG M I  be a formal  con t ext, object  g  is call ed a full   attributes  obj ect, if and o n ly if  f gM . Dually, attribute  m  is called a la rgest commo n   attribute if and only if  gm G  [10].  Definition 3.2 .  Let   ,, KG M I  be a formal contex t, object  g  is  called a shaded  obje c t, if and only if the r e a r e a  se ri es of o b je cts  {} ii T g and  T is index set, that makes  () ( ) i iT f gf g . Dually, attri bute  m  is call e d  a shad ed  attribute, if a nd only if the r e a r e a  seri es of attri butes  {} ii T m  and  T is  index set, tha t  make s  () ( ) i iT gm gm .  Definition  3.3 .  Let   ,, KG M I  be a  f o rmal  contex t,  K  is  calle d a  pu rified fo rm al  context, if and only if there is no full attributes  o b je ct, no largest  comm on attri bute, no sh a ded  obje c t and no  shad ed attrib ute.  Definition 3.4 .   Let   ,, KG M I  be  a formal  co ntext, a con c e p t is called  a o b ject   c o nc ept if it  has  the form      ,  gf g f g ,  gG , and  g  is called its obj ect label;  a  con c e p t is  ca lled a  p r op ert y  con c e p t if i t  has that  ha s the  form     ,  gm f g m , mM ,  and  m  is called  its attribute la bel.  Propo sition  3 . 1. In a co m p lete lattice,  a join -irredu cible elem ent  has  only on e  lowe r  neigh bor, an d  a meet-irred ucibl e  eleme n t has only o ne upp er nei g hbor [7].   Theo rem 3.1.  Let   ,, KG M I  be a purified formal  context, a obj ect co ncept o f   K   must b e  a  joi n -irred uci b le  element, a nd  vice versa.  Dually, an attri bute  con c ept  of  K  m u s t  b e  a   meet-irre d u c i b le eleme n t, and vice versa.  Proof: Pro o f  by co ntra ctio n an d a s sum e  that  a o b je ct con c ept   , A B  is not a join- irre du cible el ement, then   , A B  has at le ast  two lower n e ighb ors, an d we d enote  all these   lo w e r  n e i g hbo r s  as    , tt tT AB , and  T is the index set. Since  , A B  is a object co nce p t, then it  must exist an  object  g  t hat  make s  f gB . By b a si c theorem  of conce p t lattice, we ha ve  () tt tT t T B Bf A    , and also  f AB ,  then we get  () t tT fA f A , w h ic h  mean s    , A B  is a sh ade d obje c t, and th is is  contradi ct  to the condit i on of the the o rem that  K  is not a   purified   cont ext. So the  assumptio n  f a ils, a n d   the  theo rem  hol ds. By  Dualit y Princi ple,  we   dire ctly get that an attribute  con c ept of  K  must be a me et-irredu cibl e element, and  vice versa.  Theo rem 3.2.  [7] Let  V be a  c o mplete lattic e , let  G  and  M  be sets a nd  assume t hat   there exi s t m appin g s  : GV  and   : M V  su ch t hat   () G  is join-dense in  V  and   () M  is me et-d ense in  V . Define I by  gI m G M   , for all  gG   mM . T h en  V is isom orphi c to con c ept lat t ice  ,, LG M I .  We d e fine       :,   g g fg fg  and    :, mg m f g m , then we   have     (( ( ) )   ) gI m g g m g f g g f g m g m g m    and th us we  have   gI m G M   , which   mean s  g and  m satisfy Theo re m 3.2. Moreo v er,  by Definition  3.4 we kno w  that   g  is a obje c t con c e p t, and  m  is an attri bute co ncept.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Com p lete Lattice Lo ssl ess Com p ressio n Storage Mo del (Zhi  Huilai )   6335 Acco rdi ng to  the above discu ssi on, g i ven a compl e te lattice  V , by using ma pping    g and   m , we ca n get a con c ept lattice  ,, LG M I  whi c h is i s omorphi c to the   c o mplete lattic e   V .   In the following Algorithm  1, by  labeling irre du cibl e element o n   V , we can  get the  obje c ts a n d  attribute s   containe d in  ,, LG M I , whi c h i s   corre s p ondin g  the el em ents  contai ned  in  G  and   M . More o v er, by u s in g  the  co nne cti on b e twe e n  join-i rre du cibl e ele m ent  and me et-irre duci b le el em ent whi c h i s   embodi ed in  V , we can get  the relation  I . So we  get  the context   ,, KG M I .  Algorithm 1: formal  context  acqui sition fo rm co mplete l a ttice   Input: c o mplete lattic e   V ;  Output: formal c ontext  K   Step 1: Traverse  com p let e  lattice   V upward fo rm it s  minimal  elem ent, if the  cu rre ntly  visited eleme n t has only o ne upp er nei g hbor, then la b e ling this el e m ent with a u n ique letter;   Step 2: Traverse  com p l e te lattice  V d o wn wa rd form its maximal element, if the  curre n tly visited eleme n t h a s only on e lowe r neig h b o r, then lab e l i ng this no de  with a uniqu e  digit;  Step 3: If m d i fferent digits  and n differe nt le tters are  use d , then establish a cont ext with   m r o ws  an d   n c o lu mns  an d s t or e  it  b y  usin g  a ma tr ix  {} ij m n Aa ,  and ea ch digi t  co rre sp ondi ng  to a row  while  each letter  correspon ding  to a column,  and initialize it to be a nil-matrix;  Step 4: T r ave r se  compl e te  lattice  V , for ea ch  nod e la bel ed by  a di git(assume  this  digit  is  i ), visit its upper  neig hbo rs u n til meet the maxima l e l ement. And i n  this process if there exi s t  an eleme n t labeled by a let t er(a ssume th is letter is  j ), then set the value of   ij a  to 1;   Step 5: Return  A .  Example 1. Let  V  be a complete and is shown in Figure  1. By using  Algorithm 1, firstly   we fin d  its  irre du cible  el ements,  whi c h i s   sh own  in Fi gure  2. Seconda ry, we g e t i t s   corre s p ondin g  formal co n t ext  K  that is  sho w n in Ta ble 1. And accordi ng to  K we get its  stora ge matri x   1 1 0 00 0 100 1 0 0 0011 0 1 1 0 0011 0 01 0 00111 10 10 10 0 0 1 1 10 10 0 0 0 1 1100 00 011 0 1 00 0 A              .          Figure 1. Co mplete Lattice  V   Figure 2. Irre duci b le Elem ents of  V   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 8, August 2014:  633 2 –  6337   6336 Table 1. Fo rmal Context K    a   bc de f   g h 1  *       *      2  *       *  *    3  * *        * *    4   *       *  *  *  5  *   *   *       6  * * *    *        7    * * *          8   *  *   *            If using  adj ce nt matrix to  s t ore complete  lattic e   V ， we mus t  es tablish  a  matrix  2 A  wi th   19 ro ws  an d 19 colu mn s, and  th e num ber  of  1   el em ents i s  twi c e  of the  numb e r  of  links bet wee n   the node s, i.e. 62.  The sto r ag e efficien cy co mpari s o n  bet wee n   1 A  and  2 A  is given is Tabl e 2.      Table 2. Storage Efficien cy Compa r iso n     size   non-zero eleme n t s  Percentage of th e  non-zero eleme n t s  1 A   88 26 40.6%   2 A   19 19   62 17.1%       Other than  saving storage  spa c e, our  method is  al so helpful to improve the e fficiency  for judgin g  complete latti ce isomo r phi sm. Com p let e  lattice iso m orp h ism ju dgment  can  be   conve r ted int o  grap h isom orphi sm jud g m ent, and this is se en a s  a NP - com p l e te probl em by a  majority of  schol ars [11].  If we jud g e  gra ph i s om orphi sm  by  perfo rming  row a nd  col u mn   excha nge of adja c ent matrix, at  the worst ca se, the total numbe r of exchan ge will rea c h  !! rc   times ( r  is the  numbe r of  rows, a s   c is the of col u m n s), a nd thi s  is mu ch g r eater tha n   expone ntial  time  com p lexity. Our method redu ce s th e scale of the stora ge ma trix, thus it can  improve the e fficiency of co mplete lattice  isomo r phi sm  judgment.       4. Conclusio n   Based  on Fo rmal Con c ept  Analysis, we pro p o s e a  compl e te lattice sto r a ge m e thod.   The propo se d method o n l y store s  irre duci b le elem ents, and th e relatio n shi p  betwe en th em.  Comp ared  wi th the a d ja ce ncy mat r ix st orag e  m e tho d , the p r op osed meth od  can imp r ove  the   stora ge effici ency.       Ackn o w l e dg ements    The wo rk prese n ted  in   this pape r  i s   su ppo rted b y   Do ctorial  Found ation o f   Hen an  Polytechni c University (B20 11-1 0 2 ) .       Referen ces   [1]    Yuan  Da yu,  Mi tra Prase n jit. L i nd e x : A l a ttice -base d  i nde x for gra p h  data b a ses. VL DB Jo urna l.  201 3;   22(2):2 29-2 52.    [2]    Ye J, Co yle  L, Dobso n  S, Ni xo n Pa dd y. R epr es entin g a n d  mani pu latin g  situatio n hi era r chies us in g   situatio n lattice s.  Revue d' Intelli ge nc e Artific i ell e . 200 8; 22( 5):647- 66 7.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Com p lete Lattice Lo ssl ess Com p ressio n Storage Mo del (Zhi  Huilai )   6337 [3]    Yaron A, B. Goldste i n, Ale x a nder Bockm a y r.  A Lattice-T heoretic F r ame w o r k for Metabolic P a th w a y  Anal ys is. Com putatio na l Met hods  in S y ste m s Biol og y. L e cture N o tes i n  Com puter S c ienc e. 20 13 ;   130:1 78- 191.   [4 ]    T h i e rry  De n oeu x ,  Zou l fi ca r  Yo u n e s , Fa h e d  Abd a l l a h .   R e p r e s e n t in g   u n c e r tai n ty  on se t-va l ued  varia b les us in g  beli e f function s. Artifici al Intel lige n ce. 2 010;  174( 7-8):47 9 -4 99.   [5]    Ganter, B., W ille, R.. Formal Conce p t Anal ys i s : Mathematica l  Found atio ns. Berlin: Spr i ng e r . 1999.   [6]    Poelm ans Jonas, Ignatov Dmitr y  I, Kuznet sov Sergei O. Formal conc ept analy sis in kno w ledge  process i ng: A surve y   on a p p l i c ations. E x pert  S y stem   w i th A pplic atio ns. 20 13; 40(1 6 ): 653 8-65 60.   [7]    V. K. Garg, N.  Mittal,   A. Se n. App lic ations  of l a ttice th eo r y  t o  d i strib u te d com puti ng.  ACM SIGACT   Notes. 200 3; 3 4 (3):40- 61.   [8]    R. Wille. C o n c ept lattices  a nd co nce p tual  kn o w l e d ge s y stems. C o mp uters & Math ematics  w i t h   Appl icatio ns. 1 992; 23( 6-9):4 93-5 15.   [9]    R. W ille.  Restr u cturin g L a ttic e  T heor y :  a n  A ppro a ch B a se d  on  Hi erarch ies  of C once p ts. I. Rival  (Ed.),  Ordered Sets, Reid el, Dor d re cht, Boston (19 82), pp. 44 5-47 0.  [10]    W enxue H o n g , Jing yi ng Ma o, Jianp in g Yu, Lins ong  J i a. T he comp lete d e finiti ons of attributes a n d   abstract descri p tion of attribut e f eatures of the formal co ntext. ICIC  Expr ess Letters. 20 13; 7(3):99 7 - 100 3.  [11]   Karp R M. Red u cibi lit y   amo n g  combin atoria l prob lems. Ne w  York: Plenum  Press, 1972 ．     Evaluation Warning : The document was created with Spire.PDF for Python.