M-tree








M-trees are tree data structures that are similar to R-trees and B-trees. It is constructed using a metric and relies on the triangle inequality for efficient range and k-nearest neighbor (k-NN) queries.
While M-trees can perform well in many conditions, the tree can also have large overlap and there is no clear strategy on how to best avoid overlap. In addition, it can only be used for distance functions that satisfy the triangle inequality, while many advanced dissimilarity functions used in information retrieval do not satisfy this.[1]




Contents






  • 1 Overview


  • 2 M-Tree construction


    • 2.1 Components


    • 2.2 Insert


    • 2.3 Split




  • 3 M-Tree Queries


    • 3.1 Range Query


    • 3.2 k-NN queries




  • 4 See also


  • 5 References





Overview




2D M-Tree visualized using ELKI. Due to the axis scales, the spheres appear ellipsoidal. Every blue sphere (leaf) is contained in a red sphere (directory nodes). Leaves overlap, but not too much.


As in any Tree-based data structure, the M-Tree is composed of Nodes and Leaves. In each node there is a data object that identifies it uniquely and a pointer to a sub-tree where its children reside. Every leaf has several data objects. For each node there is a radius r{displaystyle r}r that defines a Ball in the desired metric space. Thus, every node n{displaystyle n}n and leaf l{displaystyle l}l residing in a particular node N{displaystyle N}N is at most distance r{displaystyle r}r from N{displaystyle N}N, and every node n{displaystyle n}n and leaf l{displaystyle l}l with node parent N{displaystyle N}N keep the distance from it.



M-Tree construction



Components


An M-Tree has these components and sub-components:



  1. Non-leaf nodes

    1. A set of routing objects NRO.

    2. Pointer to Node's parent object Op.



  2. Leaf nodes

    1. A set of objects NO.

    2. Pointer to Node's parent object Op.



  3. Routing Object

    1. (Feature value of) routing object Or.

    2. Covering radius r(Or).

    3. Pointer to covering tree T(Or).

    4. Distance of Or from its parent object d(Or,P(Or))



  4. Object

    1. (Feature value of the) object Oj.

    2. Object identifier oid(Oj).

    3. Distance of Oj from its parent object d(Oj,P(Oj))





Insert


The main idea is first to find a leaf node N where the new object O belongs. If N is not full then just attach it to N. If N is full then invoke a method to split N. The algorithm is as follows:



Algorithm Insert

  Input: Node N of M-Tree MT, Entry On{displaystyle O_{n}}O_{{n}}

  Output: A new instance of MT containing all entries in original MT plus On{displaystyle O_{n}}O_{{n}}



  Ne←N{displaystyle N_{e}gets N}{displaystyle N_{e}gets N}'s routing objects or objects

  if N is not a leaf then

  {

       /* Look for entries that the new object fits into */

       let Nin{displaystyle N_{in}}N_{{in}} be routing objects from Ne{displaystyle N_{e}}N_{{e}}'s set of routing objects NRO{displaystyle N_{RO}}N_{{RO}} such that d(Or,On)≤r(Or){displaystyle d(O_{r},O_{n})leq r(O_{r})}{displaystyle d(O_{r},O_{n})leq r(O_{r})}

       if Nin{displaystyle N_{in}}N_{{in}} is not empty then

       {

          /* If there are one or more entry, then look for an entry such that is closer to the new object */

          Or∗←minOr∈Nind(Or,On){displaystyle O_{r}^{*}gets min _{O_{r}in N_{in}}d(O_{r},O_{n})}{displaystyle O_{r}^{*}gets min _{O_{r}in N_{in}}d(O_{r},O_{n})}

       }

       else

       {

          /* If there are no such entry, then look for an object with minimal distance from */ 

          /* its covering radius's edge to the new object */

          Or∗←minOr∈Nind(Or,On)−r(Or){displaystyle O_{r}^{*}gets min _{O_{r}in N_{in}}d(O_{r},O_{n})-r(O_{r})}{displaystyle O_{r}^{*}gets min _{O_{r}in N_{in}}d(O_{r},O_{n})-r(O_{r})}

          /* Upgrade the new radii of the entry */

          r(Or∗)←d(Or∗,On){displaystyle r(O_{r}^{*})gets d(O_{r}^{*},O_{n})}{displaystyle r(O_{r}^{*})gets d(O_{r}^{*},O_{n})}

       }

       /* Continue inserting in the next level */

       return insert(T(Or∗),On{displaystyle T(O_{r}^{*}),O_{n}}{displaystyle T(O_{r}^{*}),O_{n}});

  else

  {

       /* If the node has capacity then just insert the new object */

       if N is not full then

       { store(N,On{displaystyle N,O_{n}}{displaystyle N,O_{n}}) }

       /* The node is at full capacity, then it is needed to do a new split in this level */

       else

       { split(N,On{displaystyle N,O_{n}}{displaystyle N,O_{n}}) }

  }


  • "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.

  • "return" terminates the algorithm and outputs the following value.




Split


If the split method arrives to the root of the tree, then it choose two routing objects from N, and creates two new nodes containing all the objects in original N, and store them into the new root. If split methods arrives to a node N that is not the root of the tree, the method choose two new routing objects from N, re-arrange every routing object in N in two new nodes N1{displaystyle N_{1}}N_{{1}} and N2{displaystyle N_{2}}N_{{2}}, and store these new nodes in the parent node Np{displaystyle N_{p}}N_{{p}} of original N. The split must be repeated if Np{displaystyle N_{p}}N_{{p}} has not enough capacity to store N2{displaystyle N_{2}}N_{{2}}. The algorithm is as follow:



Algorithm Split

  Input: Node N of M-Tree MT, Entry On{displaystyle O_{n}}O_{{n}}

  Output: A new instance of MT containing a new partition.



  /* The new routing objects are now all those in the node plus the new routing object */

  let be NN entries of N∪O{displaystyle Ncup O}Ncup O

  if N is not the root then

  {

     /*Get the parent node and the parent routing object*/

     let Op{displaystyle O_{p}}O_{{p}} be the parent routing object of N

     let Np{displaystyle N_{p}}N_{{p}} be the parent node of N

  }

  /* This node will contain part of the objects of the node to be split */

  Create a new node N'

  /* Promote two routing objects from the node to be split, to be new routing objects */

  Create new objects Op1{displaystyle O_{p1}}O_{{p1}} and Op2{displaystyle O_{p2}}O_{{p2}}.

  Promote(N,Op1,Op2{displaystyle N,O_{p1},O_{p2}}{displaystyle N,O_{p1},O_{p2}})

  /* Choose which objects from the node being split will act as new routing objects */

  Partition(N,Op1,Op2,N1,N2{displaystyle N,O_{p1},O_{p2},N_{1},N_{2}}{displaystyle N,O_{p1},O_{p2},N_{1},N_{2}})

  /* Store entries in each new routing object */

  Store N1{displaystyle N_{1}}N_{{1}}'s entries in N and N2{displaystyle N_{2}}N_{{2}}'s entries in N'

  if N is the current root then

  {

      /* Create a new node and set it as new root and store the new routing objects */

      Create a new root node Np{displaystyle N_{p}}N_{{p}}

      Store Op1{displaystyle O_{p1}}O_{{p1}} and Op2{displaystyle O_{p2}}O_{{p2}} in Np{displaystyle N_{p}}N_{{p}}

  }

  else

  {

      /* Now use the parent routing object to store one of the new objects */

      Replace entry Op{displaystyle O_{p}}O_{{p}} with entry Op1{displaystyle O_{p1}}O_{{p1}} in Np{displaystyle N_{p}}N_{{p}}

      if Np{displaystyle N_{p}}N_{{p}} is no full then

      {

          /* The second routing object is stored in the parent only if it has free capacity */

          Store Op2{displaystyle O_{p2}}O_{{p2}} in Np{displaystyle N_{p}}N_{{p}}

      }

      else

      {

           /*If there is no free capacity then split the level up*/

           split(Np,Op2{displaystyle N_{p},O_{p2}}{displaystyle N_{p},O_{p2}})

      }

  }


  • "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.

  • "return" terminates the algorithm and outputs the following value.




M-Tree Queries



Range Query


A range query is where a minimum similarity/maximum distance value is specified.
For a given query object Q∈D{displaystyle Qin D}{displaystyle Qin D} and a maximum search distance
r(Q){displaystyle r(Q)}r(Q), the range query range(Q, r(Q)) selects all the indexed objects Oj{displaystyle O_{j}}O_{j} such that d(Oj,Q)≤r(Q){displaystyle d(O_{j},Q)leq r(Q)}{displaystyle d(O_{j},Q)leq r(Q)}.[2]


Algorithm RangeSearch starts from the root node and recursively traverses all the paths which cannot be excluded from leading to qualifying objects.



Algorithm RangeSearch

Input: Node N of M-Tree MT,  Q: query object, r(Q){displaystyle r(Q)}r(Q): search radius



Output: all the DB objects such that d(Oj,Q)≤r(Q){displaystyle d(Oj,Q)leq r(Q)}{displaystyle d(Oj,Q)leq r(Q)}



{ 

  let Op{displaystyle O_{p}}O_{{p}} be the parent object of node N;



  if N is not a leaf then { 

    for each entry(Or{displaystyle O_{r}}O_{{r}}) in N do {

          if |d(Op,Q)−d(Or,Op)|≤r(Q)+r(Or){displaystyle |d(O_{p},Q)-d(O_{r},O_{p})|leq r(Q)+r(O_{r})}{displaystyle |d(O_{p},Q)-d(O_{r},O_{p})|leq r(Q)+r(O_{r})} then { 

            Compute d(Or,Q){displaystyle d(O_{r},Q)}d(O_{{r}},Q);

            if d(Or,Q)≤r(Q)+r(Or){displaystyle d(O_{r},Q)leq r(Q)+r(O_{r})}{displaystyle d(O_{r},Q)leq r(Q)+r(O_{r})} then

              RangeSearch(*ptr(T(Or{displaystyle T(O_{r}}{displaystyle T(O_{r}})),Q,r(Q){displaystyle r(Q)}r(Q)); 

          }

    }

  }

  else { 

    for each entry(Oj{displaystyle O_{j}}{displaystyle O_{j}}) in N do {

          if |d(Op,Q)−d(Oj,Op)|≤r(Q){displaystyle |d(O_{p},Q)-d(O_{j},O_{p})|leq r(Q)}{displaystyle |d(O_{p},Q)-d(O_{j},O_{p})|leq r(Q)} then { 

            Compute d(Oj,Q){displaystyle d(O_{j},Q)}d(O_{{j}},Q);

            if d(Oj,Q){displaystyle d(O_{j},Q)}d(O_{{j}},Q) ≤ r(Q){displaystyle r(Q)}r(Q) then

              add oid(Oj){displaystyle oid(O_{j})}oid(O_{{j}}) to the result;

          }

    }

  }

}


  • "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.

  • "return" terminates the algorithm and outputs the following value.





  • oid(Oj){displaystyle oid(O_{j})}oid(O_{{j}}) is the identifier of the object which resides on a separate data file.


  • T(Or){displaystyle T(O_{r})}T(O_{{r}}) is a sub-tree – the covering tree of Or{displaystyle O_{r}}O_{{r}}



k-NN queries


K Nearest Neighbor (k-NN) query takes the cardinality of the input set as an input parameter. For a given query object Q ∈ D and an
integer k ≥ 1, the k-NN query NN(Q, k) selects the k indexed objects which have the shortest distance from Q, according to the distance function d.
[2]



See also



  • Segment tree


  • Interval tree - A degenerate R-Tree for 1 dimension (usually time).

  • Bounding volume hierarchy

  • Spatial index

  • GiST



References





  1. ^ Ciaccia, Paolo; Patella, Marco; Zezula, Pavel (1997). "M-tree An Efficient Access Method for Similarity Search in Metric Spaces" (PDF). Proceedings of the 23rd VLDB Conference Athens, Greece, 1997. IBM Almaden Research Center: Very Large Databases Endowment Inc. pp. 426–435. p426. Retrieved 2010-09-07..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ ab P. Ciaccia; M. Patella; F. Rabitti; P. Zezula. "Indexing Metric Spaces with M-tree" (PDF). Department of Computer Science and Engineering. University of Bologna. p. 3. Retrieved 19 November 2013.










Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th
Read more

章鱼与海女图

Image
本条目 可参照英語維基百科相應條目来扩充 。 （2014/5/25） 若您熟悉来源语言和主题，请协助参考外语维基扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记 {{Translated page}} 标签。 本条目 需要擴充。 （2013年8月15日） 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 《 章鱼与海女 》（日语： 蛸と海女 ／ たことあま   Tako to ama ）是一幅由日本畫家葛饰北斋创作的浮世绘，出自1814年（文化4年）出版的艳本《喜能会之故真通》（日语： 喜能会之故真通 ／ きのえのこまつ   Kinoe no Komatsu ）。畫中有兩隻章鱼以觸手攻擊一名採珠的海女，並進行擬似戀獸癖的交媾行為。作品尺寸为6½" × 8¾" （16.51 cm × 22.23 cm）。 [1] 在此之前的类似作品还有北尾重政的艳本《謡曲色番組》及勝川春潮的艳本《艳本千夜多女志》等，有被北斋作为参考的可能性。 《章鱼与海女图》有不同英文翻译，一般称The Dream of the Fisherman's Wife，又作Girl Diver and Octopi、Diver and Two Octopi，Richard Douglas Lane称其为 Girl Diver and Octopi [2] ，Mathi Forrer 称其为 Pearl Diver and Two Octopi [3] ，Danielle Talerico 称其为 Diver and Two Octopi 。 [4] 目录 1 作品介绍 1.1 画中对话 1.2 解释 2 评价 3 影响 3.1 模仿作品 4 另见 5 参考来源 6 外部連結 作品介绍 画中对话 原文 译文 大蛸： いつぞハいつぞハとねらいすましてゐたかいがあつて、けふといふけふ、とうとうとらまへたア。てもむつくりとしたいいぼぼだ。いもよりハなをこうぶつだ。サアサア、すつてすつてすいつくして
Read more

Farm Security Administration

Image
Farm Security Administration Farm Security Administration logo Agency overview Formed September 1, 1937  ( 1937-09-01 ) Preceding agencies Resettlement Administration Federal Emergency Relief Administration Dissolved 1946 Superseding agency Farmers Home Administration Key documents Farm Security Act Bankhead-Jones Farm Tenant Act The Farm Security Administration ( FSA ) was a New Deal agency created in 1937 to combat rural poverty during the Great Depression in the United States. It succeeded the Resettlement Administration (1935–1937). [1] The FSA stressed "rural rehabilitation" efforts to improve the lifestyle of sharecroppers, tenants, very poor landowning farmers, and a program to purchase submarginal land owned by poor farmers and resettle them in group farms on land more suitable for efficient farming. Critics, including the Farm Bureau, strongly opposed the FSA as an experiment in collectivizing agriculture—that is, in bringing
Read more