JP5965353B2 - Address resolution system and method - Google Patents

Description

  The present invention relates to an address resolution system and method, and in particular, in an information communication network, specifies an object (refers to a home appliance or a terminal having a communication function) connected to the network by specifying some conditions, and performs communication. An address resolution system and method for enabling

  In a conventional information communication network, a communication target is specified by an address in a logical space. This is a telephone number for fixed telephones and an IP address for the Internet, and these correspond to locations on the network, so communication is possible by connecting to that location.

  On the other hand, mobile phone numbers and Internet URLs can be interpreted as higher logical addresses or names. In other words, they indicate the logical position of the communication partner and information, but do not indicate the connection position on the network, so the connection position on the network is determined by LR (location register) in the former and DNS (domain name server) in the latter. Conversion to the indicated address (so-called name resolution) is required. In the latter case, the IP address after conversion from the URL is used for connection (for example, see Non-Patent Documents 1 and 2).

Supervised by Hideaki Yumi, Future Netto Technology Series Ubiquitous Network Technology, Telecommunications Association, 2003. http://www.nic.ad.jp/en/newsletter/No22/080.html

  By the way, when a very large number of objects are connected to the network in the future, instead of communicating after the user knows the name uniquely assigned to each object, for example, the user User communication requirements such as communication with a person riding a bicycle that has been lost before or communication with a sensor whose temperature is 20 degrees or higher in a certain time zone (search conditions for various attributes) It is assumed that you want to be able to communicate by specifying the object by directly specifying (combination).

  However, in the existing system, the user knows the name uniquely assigned to each object, and performs communication by designating the name. For example, in the case of a mobile phone, communication is performed by the user specifying a telephone number. For this reason, it is difficult to realize the use form as described above.

  In addition, attributes (value information and IP addresses) are managed for each object, and objects that satisfy the conditions specified by the attributes (value combinations) are examined one by one, and objects that satisfy the conditions are identified. Although the method of specifying the IP address is also conceivable, there is a problem that all objects need to be searched, and the number of objects and attributes becomes enormous.

  The present invention has been made in view of the above points, and by specifying conditions for various attributes (location, terminal type, etc.) of an object, an object that matches the conditions can be identified without performing an all-object search. An object of the present invention is to provide an address resolution system and method capable of specifying the IP address of the object.

In order to solve the above-described problem, according to one aspect, an object connected to an information communication network has values for a plurality of attributes, and an object is searched by specifying a condition by combining the values of the attributes. An address resolution system for identifying the address of the object,
It has a resolver and an object management server
The resolver is
Get the registration request including the address and multi-attribute information of each object, using the value of the hierarchy of attributes included in the registration request, the attribute _{i = i 1, i 2,} ..., i k, ..., and i _K , The attribute i _k has values up to the hierarchy m _k, and the value x _{i, m} in the hierarchy m of the attribute i is used as the name of the object

という値の組から構成されるobjectベクトルを生成し、該objectのアドレスと共に前記object管理サーバに送出する名前付与手段と、
取得した検索要求に含まれる各属性に関する条件が指定された属性の階層の値を用いてクエリベクトルを生成して、前記object管理サーバに送出するクエリベクトル生成手段と、
を有し、
前記object管理サーバは、
各属性と該属性の値の階層に対し、該属性と該属性の値の階層を組み合わせ、階層毎にobjectを管理するためのノードを有するツリーである組み合わせ管理ツリーを格納したobjectデータベースと、
前記リゾルバから前記objectベクトルを取得し、前記組み合わせ管理ツリーを参照して、該objectベクトルに基づいて該組み合わせ管理ツリーのノードに対応付けてobjectのアドレスを登録するobject登録手段と、
前記リゾルバから前記クエリベクトルを取得し、該クエリベクトルに基づいて、前記組み合わせ管理ツリーを参照して、該組み合わせ管理ツリーのノードに登録されているobjectのアドレスを取得するobject検索手段と、を有するアドレス解決システムを提供される。

A name assigning means for generating an object vector composed of a set of values and sending it to the object management server together with the address of the object;
A query vector generation means for generating a query vector using a value of an attribute hierarchy in which a condition relating to each attribute included in the obtained search request is specified, and sending the query vector to the object management server;
Have
The object management server
An object database storing a combination management tree, which is a tree having nodes for managing objects for each hierarchy, by combining the attribute and the attribute value hierarchy for each attribute and the attribute value hierarchy;
Object registration means for acquiring the object vector from the resolver, referring to the combination management tree, and registering an object address in association with a node of the combination management tree based on the object vector;
Object search means for acquiring the query vector from the resolver, referring to the combination management tree based on the query vector, and acquiring an address of an object registered in a node of the combination management tree; Provided address resolution system.

  As described above, according to the present invention, by specifying a condition for various attributes (location, terminal type, etc.) of an object, an object that matches the condition can be identified without performing an all-object search. It is possible to provide name resolution that can specify the IP address of the server.

1 is a basic configuration example of an IP network to which the present invention is applied. It is a structural example of the resolver of this invention. It is a structural example of the object management server of this invention. It is an example of the combination management tree in the 1st Embodiment of this invention. It is a flowchart at the time of the naming assignment and registration in the 1st Embodiment of this invention. It is a flowchart at the time of the search (name resolution) in the 1st Embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 1 is a basic configuration example of an IP network to which the present invention is applied.

  In the system shown in the figure, an object 10, a resolver 20, and an object management server 30 are connected to an IP network 1. In the figure, the IP network 1 is described as an example, but another network using a logical address other than the IP address may be used (that is, the logical address indicates a position on the network and If a logical address is designated, another network may be used as long as data and packets can be transferred to a desired destination). Here, the object 10 has multi-attribute information (location, terminal type, time, etc.) in addition to the ID and IP address for identifying the object.

  The resolver 20 includes a registration / search request receiving unit 21 and an object name assignment / query vector generation unit 22, and the object name assignment / query vector generation unit 22 is connected to the object management server 30.

  The object management server 30 includes an object / query vector reception unit 31, an object registration / search unit 32, an object database 33, and a tree construction unit 34, and the object / query vector reception unit 31 is connected to the resolver 20.

  An embodiment of the present invention will be described below based on the above configuration.

[First Embodiment]
In the present embodiment, a description will be given of processing for searching for the management server 30 by specifying an attribute value, tree structure, registration of an object IP address, and a value for the attribute.

  An object 10 connected to the information communication network 1 (for example, a home appliance having a communication function, a terminal, a sensor, etc., and having an IP address) has a value (for example, time or place) Time = 2013/1/31, place = Tokyo / Musashino City, etc.). Here, it is assumed that the value for each attribute has a hierarchical structure. For example, it is assumed that the value for the attribute “location” is composed of two layers of prefectures / municipalities, and as a specific value, for example, an object has a value of “Tokyo / Musashino City”. . In this way, a hierarchical structure is defined for values for attributes. It is assumed that object10 has values for some of these attributes.

  The registration / search request receiving unit 21 of the resolver 20 receives a registration request packet including attributes, values for attributes, and a hierarchical structure from the object 10, and the object name assignment / query vector generation unit 22 sets pairs of values for the attributes and attributes. Is assigned as the name of the object (hereinafter referred to as “name assignment”).

  In the object database 33 of the object management server 30, for each attribute and value hierarchy defined above, a combination of the attribute and value hierarchy is expressed and held in a tree structure. This tree is called a “combination management tree”. The tree construction unit 34 of the object management server 30 registers the combination management tree, the attribute, and the value of the attribute in the object database 33 in association with each other. This process is called “indexing”.

  At the time of a search, values for some attributes are specified in the object 10, a set of these attributes and attribute values is input, and a search request including a value specified by the object 10 is performed in the registration / search request receiving unit 21 of the resolver 20. The packet is received, the object name assignment / query vector generation unit 22 generates a query vector based on the value of the search request packet, sends it to the object management server 30, and the object registration / search unit 32 of the object management server 30 The object database 33 is searched, and as a result, the address of a specific object is notified to the object 10 via the resolver 20. This process is called “name resolution”.

  As described above, in the present invention, a pair of attributes and attribute values and a tree structure are managed in the object database 33, and an object satisfying a condition specified by the pair of attributes and attribute values is searched along the tree. This makes it possible to specify objects without searching all objects.

<Indexing>
A specific configuration method (indexing) of the above combination management tree is shown below.

  The tree construction unit 34 generates a combination management tree described below in advance and stores it in the object database 33.

  The process of the tree construction unit 34 will be described below.

As a hierarchical structure of the value of the attribute i (d from i = 1), 1 L _{i, 1} types as tier value, L _{i, 2} types as values from 1 to 2 tier, 1 from M _i tier It is assumed that the value can take Li and _Mi values. In addition, a set of values that can be taken in the hierarchies 1 to m of the attribute i is U _{i, m} . At this time, the tree construction unit 34 configures the combination management tree as follows.

In the first hierarchy of the combination management tree, a node in charge of each value x _{i, 1} ∈U _{i, 1} in the first hierarchy for the attribute i is prepared. (Hereinafter, for example _, the node in charge of the value x _{i, 1} may be referred to as the node x _{i, 1.} ) That is, for the attribute i, the number of pattern patterns L _{i, 1 that} can be taken in the first layer Prepare a node. For all attributes i = 1 to d

個のノードとなる。

Nodes.

Next, in the second level of the tree, the nodes x _{i, 1 in} the first level of the tree (for example, if attribute i is a place name, x _{i, 1} = Tokyo) are the values up to the second level of attribute i. Is a child node with x _{i, 1} / x _{i, 2} ∈U _{i, 2} (eg, x _{i, 1} / x _{i, 2} = Tokyo / Musashino City) and the first layer of attribute j (> i) A child node whose value is x _{j, 1} ∈ U _{j, 1} is generated. In other words, under the node x _{i, 1} , besides the child node with the same attribute i,

個の子ノードが生成される。ツリーの３階層目には、２階層目のノードがノードx _i,1/x _i,2の配下にノードx _i,1/x _i,2/x _i,3および属性j (j>i)の1階層目の値がx _j,1であるノードが子ノードとして生成され、かつ２階層目のノードがノードx _i,1/x _j,1の配下には属性jの2階層目までの値がx _j,1/x _j,2となるノード、および属性k (k>j）の1階層目の値がx_k,1となる子ノードが生成される。

Child nodes are created. The 3 tier tree, second tier nodes node x _{i, 1} / x _i, node ₂ under _{x i, 1 / x i,} 2 / x i, 3 , and attribute j (j> i) A node whose value in the first layer is x _{j, 1} is generated as a child node, and nodes in the second layer are subordinate to node x _{i, 1} / x _{j, 1} up to the second layer of attribute j A node whose value is x _{j, 1} / x _{j, 2} and a child node whose value of the first hierarchy of the attribute k (k> j) is x _{k, 1} are generated.

  By repeatedly performing the above, a combination management tree is formed, and each node manages an object having a value that it is responsible for.

  The above combination management tree node may be one node or a group of several nodes on one physical server, and such servers may be geographically distributed.

  The indexing procedure will be described in detail using a specific example.

  As an example, consider two attributes: attribute 1 = location name and attribute 2 = terminal type name. Also, the place name is assumed to be composed of two layers, such as a prefecture name / city name. The terminal type name is also assumed to be composed of two layers of a major classification name / small classification name. Examples of values of major classification names are OA equipment, home appliances, sensors, etc. As an example of the value of the minor classification name, it is assumed that a printer, a server, etc. exist under the major classification name = OA, and a refrigerator, a TV, an air conditioner, etc. exist under the household appliance.

FIG. 4 shows a combination management tree configured according to the procedure of the present invention. The configuration of this figure will be described.
・ First layer:
(1) In the dotted line frame on the left, L _1,1 (= 47) values (namely, Hokkaido, Okinawa, etc.) of the first place name (namely, prefecture name) are listed.

(2) In the dotted frame on the right side, L _2,1 values (namely, OA equipment, home appliances, etc.) of the terminal type name first layer (namely, major classification name) are listed.

・ Second level:
(1) In the dotted frame on the left side, the values (such as Sapporo city) of the second place name (that is, the city name) are listed under the parent node having the value of the first place name. Therefore, within this frame is, L _{1, 2} or set of Government names are listed.

(2) The value of the first layer of the terminal type name is listed in the middle dotted frame. Therefore, in this frame, a set of L _1,1 * L _2,1 prefecture / terminal classification major classification names is listed.

(3) In the dotted line frame on the right side, the values (namely, printers, servers, etc.) of the terminal type name second level (namely, minor classification name) are listed. Therefore, in this frame, a set of L _2,2 terminal type major classification / minor classification names is listed.

・ 3rd layer:
(1) Values in the first layer of the terminal type name are listed in the dotted frame on the left side. Therefore, in this frame, a set of L _1,2 * L _2,1 prefecture name, municipality name, and terminal type major classification name is listed.

(2) Values in the second layer of the terminal type name are listed in the dotted frame on the right side. Therefore, in this frame, a set of L _1,1 * L _2,2 prefecture names / terminal type major classification names / terminal type minor classification names is listed.

-4th layer: Terminal type name 2nd layer values are listed. Therefore, in this frame, a set of L _1,2 * L _2,2 prefecture names, municipalities, terminal type major classification names, and terminal classification minor classification names is listed.

  As described above, by registering a pair of an attribute and an attribute value in the tree of the object database 33 of the object management server 30, it is possible to cope with any condition designation by a combination of the attribute and attribute value hierarchy. Therefore, it is possible to specify an object that satisfies the condition by specifying a node that satisfies the condition specification along the tree and retrieving the object managed by the node at the time of search.

  Next, a specific example of storing an object in the combination management tree in the object database 33 will be described using the example of FIG.

  As an example, consider the case of object = {location = Hokkaido / Sapporo, terminal type = OA / server}.

  Two types of object storage methods are considered.

  As the procedure (1), first, registration is made with the “Hokkaido” node in the left frame line of the first layer of the tree and the “OA” node in the right frame line. Next, in the second layer, registration is made with the “Sapporo” node in the left frame, the “OA” node in the middle frame, and the “server” in the right frame. In the third layer, registration is made in the “OA” node in the left frame and the “server” in the right frame. In the fourth layer, registration is made in the “server” node. That is, a total of 8 nodes are registered.

  As the procedure (2), registration is made only to the “server” node in the fourth hierarchy traced to Hokkaido / Sapporo / OA / server.

<Registration process>
The object name assignment and registration process in the object database 33 will be described below.

  In the following description, it is assumed that a combination management tree is stored in the object database 33 in advance.

  FIG. 5 is a flowchart at the time of registration in the first embodiment of the present invention.

  Step 101) When the object 10 is connected to the network 1, the object 10 transmits an object registration request packet to the registration / search request receiving unit 21 in the resolver 20. At that time, the object's own IP address (= IP # A), objectID, and multi-attribute information are notified.

  Step 102) When the registration request packet from the object 10 arrives at the registration / search request receiving unit 21 of the resolver 20, various information of the object 10 is read out and notified to the object name assignment / query vector generation unit 22. The object name assignment / query vector generation unit 22 generates a name vector V of the object from the multi-attribute information (name assignment).

  The specific procedure is as follows.

object10 attribute i is i = i ₁ with the _{value, i 2, ..., i k} , ..., and i _K, assumed to have a value up to hierarchical m _k th for the attribute i _k, in the hierarchy m attributes i An object vector that is the name of the object using the values x _{i, m}

を生成する。

Is generated.

  The set of the generated vector V and IP # A is notified to the object management server 30.

Step 103) When the object / query vector receiving unit 31 in the object management server 30 receives the set of the object vector V and IP # A, it notifies the object registration / search unit 32 of it. The object registration / search unit 32 registers in the object database 33 by the following procedure (1) or (2).
(1) The object is registered in all nodes in charge of the value designated by V along the tree of the object database 33.
(2) From the root of the object database 33 tree,

の順に辿っていき、到達した最後のノードのみに該objectを登録する。
以下に、図４を用いてobject登録時の処理を具体的に示す。

The object is registered only in the last node reached.
Hereinafter, the processing at the time of object registration will be specifically described with reference to FIG.

  For example, consider registration of V = {place name: Hokkaido / Sapporo, terminal type name: OA / printer}.

In the case of the procedure (1), the “Hokkaido” node in the left frame of the first layer of the tree in FIG. 4, the “OA” node in the right frame of the first layer, and the “Sapporo” in the left frame of the second layer. Node, “OA” node in the middle border of the second hierarchy, “Printer” node in the right border of the second hierarchy, “OA” node in the left border of the third hierarchy, and in the right border of the third hierarchy Register the object in a total of 8 nodes, the “Printer” node and the “Printer” node in the 4th layer frame.
In the case of step (2), the object is registered only in the “printer” node in the 4th layer frame.
<Search process>
Hereinafter, processing at the time of object search (name resolution) will be described.

  FIG. 6 is a flowchart at the time of search (name resolution) in the first embodiment of the present invention.

  Step 201) The user transmits information (for example, {location name = Hokkaido, terminal type name = OA}) in which conditions are specified for each attribute from the terminal to the resolver 20 as a search request packet.

  Step 202) When the search request packet is received by the registration / search request receiving unit 21 in the resolver 20, the condition designation for each attribute is read out and notified to the object name assignment / query vector generation unit 22. The object name assignment / query vector generation unit 22 generates a query vector q according to the following procedure.

Search attribute i ₁ which is the condition specified _{at, i 2, ..., i k} , ..., for i _K, a value for m _k from the hierarchy 1 is specified for each i _k. A query vector using the values of each hierarchy where these values are specified

を生成し、object管理サーバ３０へ通知する。

Is generated and notified to the object management server 30.

Step 203) When the query vector q is received by the object / query vector receiving unit 31 in the object management server 30, the object registration / search unit 32 is notified of it. The object registration / search unit 32 searches the object database 33 by the following procedure (1) or (2).
(1) In the combination management tree of the object database 33, from root,

と辿って行き、最後に到達したノードで管理しているobjectを読み出す。
(2) object登録・検索部３２は、objectデータベース３３から、ツリーに沿ってqで指定された値を担当するノードを全て訪問し、それらノードを頂点とした部分木に属する全てのノードで管理しているobjectを読み出す。
ステップ２０４）object登録・検索部３２は、以上の(1)または(2)の手順で特定されたobjectの集合に対し、該objectのIPアドレスをリゾルバ２０に通知する。

And read the object managed by the last node reached.
(2) The object registration / search unit 32 visits all the nodes in charge of the value specified by q along the tree from the object database 33, and manages them at all nodes belonging to the subtree with those nodes as vertices. Reads the object being used.
Step 204) The object registration / retrieval unit 32 notifies the resolver 20 of the IP address of the object for the set of objects specified by the above procedure (1) or (2).

  If the object specified is registered in all nodes in charge of the value specified by V using the method (1) above during the registration process, the object is searched using the method (1) at the time of search. In addition, when an object is registered in only one node using the method (2) described above during the registration process, the object is searched using the method (2) during the search.

  The processing at the time of object search will be specifically shown below using FIG.

  For example, consider a condition specification for {place name = Hokkaido} only.

  In the case of the procedure (1), the object managed by the “Hokkaido” node in the left frame of the first layer of the tree of FIG. 4 may be read.

  In the case of the procedure (2), all nodes belonging to the subtree having the “Hokkaido” node as a vertex are accessed, and objects managed by those nodes are read.

  As another example, consider a condition designation of {place name = Hokkaido, terminal type name = OA}.

  In the case of the procedure (1), the object managed by the “OA” node in the frame line at the center of the second hierarchy of the tree in FIG. 4 may be read.

  In the case of the procedure of (2), in the tree of FIG. 4, Hokkaido / OA (= in the middle frame of the second hierarchy) and Hokkaido / (no municipality designation) / OA / (= 2 Hokkaido in the second hierarchy) All the municipalities nodes in the list are accessed, and all nodes belonging to the subtree having the subordinate “OA” nodes as vertices are accessed, and objects managed by these nodes are read.

[Second Embodiment]
In this embodiment, when an object search is performed, if a corresponding node is specified in the combination management tree as in the first embodiment, combination management is performed on the object (set) managed by the node. The objects to be communicated are narrowed down by specifying a condition related to an attribute (referred to as a secondary attribute) other than an attribute managed by the tree (referred to as a primary attribute).

  For example, if an object has a value for an attribute whose attribute value is not represented in a hierarchical structure (such as a sensor temperature or terminal size that has a continuous value), such an attribute If you want to specify an object by specifying the condition for (for example, temperature ≧ 20 degrees), first specify the set of objects by specifying the condition for the set of hierarchies managed there using the combination management tree, From the set, further narrow down to objects that satisfy the temperature ≧ 20 degrees. Alternatively, in the combination management tree described in the present invention, only attributes that are highly likely to be specified are used, and a set of corresponding objects is first extracted from the combination of these attributes and the attribute values, and the other attributes are then extracted. The specified condition may be a secondary attribute.

  In the present embodiment, the processing of step 203 in FIG. 6 is different. Hereinafter, this will be described as step 203 ′.

In the present embodiment, it is assumed that the node that manages the object 10 holds not only the primary attribute information used when configuring the combination management tree but also the secondary attribute information. Further, it is assumed that conditions for primary attributes and secondary attributes are specified at the time of retrieval, and the specified conditions are notified to the object / query vector receiving unit 31 in the object management server 30 via the resolver 20. It is assumed that the query vector is configured by specifying conditions for the primary attribute.
Step 203 ′) When the query vector q is received by the object / query vector receiving unit 31 in the object management server 30, it is notified to the object registration / search unit 32. The object registration / search unit 32 searches the object database 33 by the following procedure (1) or (2).
(1) In the combination management tree of the object database 33, from root,

と辿って行き、最後に到達したノードで管理しているobjectを読み出す。
(2) objectデータベース３３の組み合わせ管理ツリーに沿ってqで指定された値を担当するノードを全て訪問し、それらノードを頂点とした部分木に属する全てのノードで管理しているobjectを読み出す。

And read the object managed by the last node reached.
(2) Visits all the nodes in charge of the value specified by q along the combination management tree of the object database 33, and reads out the objects managed by all the nodes belonging to the subtree with those nodes as vertices.

  The object to be specified is narrowed down by specifying a condition regarding the secondary attribute for the set of objects specified in the above procedure.

  As a specific example, in each node of the object database, R-tree (Non-patent document 3: A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” ACM SIGMOD 1984., non-patent document) 4: L. Arge et al., “The Priority R-tree: a practically efficient and worst-case optimal R-tree,” SIGMOD 2004.) and KD-tree (Non-Patent Document 5: http: //en.wikipedia Assume that the value of each object is managed by a tree-type data structure called (.org / wiki / K-d_tree). For example, it is assumed that there are an attribute called temperature and an attribute called terminal size as secondary attributes. At that time, the object is mapped on the two-dimensional space. The two-dimensional space is divided into a plurality of areas, and a tree structure is constructed in which each node under the root takes charge of each area, and further the area is divided and its child nodes take charge. At the time of retrieval, in this example, a range is specified for each of the first dimension and the second dimension, and an object that satisfies the condition is identified by tracing a node that overlaps the range.

  In this way, the secondary attribute is also searched, and the object specified as a result is read.

[Third Embodiment]
In the first embodiment, in the first layer of the combination management tree, the values of the first layer for each attribute i are listed and the nodes for each are generated, but in this embodiment, instead of doing so In addition, the combination management tree is configured in the following procedure.

  First, it is assumed that prioritization is performed among attributes, and the attributes are rearranged in descending order of priority. That is, attribute i has higher priority than attribute j (j> i). Only the value of the first layer of attribute 1 is listed in the first layer of the tree. In the second layer of the tree, the values of the second layer of attribute 1 or the values of the first layer of attribute 2 are listed, and the values of the first layer after attribute 3 are not included. In the third level of the tree, list the value of the third level of attribute 1, the value of the first or second level of attribute 2, or the value of the first level of attribute 3, and the first level after attribute 4 Does not include eye values.

  The above is repeated and the combination management tree is configured.

  At the time of object search, in the first embodiment, the presence / absence of condition designation can be selected for an arbitrary attribute. On the other hand, here, conditions are designated for attributes 1 to J, and the search procedure is the first. It is the same as the method of the embodiment.

  In the case of the example of FIG. 4, for example, attribute 1 = location name and attribute 2 = terminal type name are set, condition specification is required for the location name at the time of search, and whether or not condition specification is specified can be selected for the terminal type name. In that case, the nodes in the right frame of the first hierarchy and the nodes in the right frame of the second hierarchy in FIG. 4 are not necessary. By doing so, the number of nodes to be managed can be reduced.

  As described above in the first to third embodiments, according to the present invention, all objects are searched by specifying conditions for various attributes (location, terminal type, etc.) of the object. It is possible to identify an object that matches a condition and provide name resolution that can identify the IP address of the object.

A numerical example is shown. It is assumed that there are two attributes i (i = 1, 2), both have values of two layers, and _{Li, 1} = 2 = ⁴ in the first layer, and _{Li, 2} = 2 ^{10 in the} second layer Suppose we have street values. Assume that the combination management tree of FIG. 4 is configured for these attribute sets. In addition to these two attributes, each object has eight secondary attributes (each attribute has a continuous value as a value). Further, the object number N = 2 ^28. Each object is assumed to have a uniformly distributed value for any attribute.

  Examples 1 and 2 are shown below as search examples.

Example 1)
If the search condition is specified up to the second hierarchy for attribute 1 and up to the second hierarchy for attribute 2, only the search cost for tracing the tree in FIG. It is possible to narrow down to N × (1/2 ¹⁰ ) ² = 256 objects from N = 2 ²⁸ (about 270 million) objects.

Example 2)
Suppose that you want to specify conditions only for the first layer of attribute 1 and further narrow down objects by specifying a range for secondary attributes. For secondary attributes, each object has a value according to a uniform distribution between 0 and 1 for each attribute. Further, the search condition for the secondary attribute is assumed to specify a range with a range length of 0.5 for each attribute. In this case, the object is narrowed down to N × 1/16 = 2 ²⁴ (= N ′) by the search with the attribute 1. Next, it is assumed that a range designation search is performed using a tree structure such as kd-tree for the search with the secondary attribute. If a range with a range length of 0.5 is specified for each of the eight attributes, the number of objects is narrowed down to N ′ × (0.5) ⁸ = 2 ¹⁶ (about 65,000). Regarding the calculation amount of the secondary attribute search (range designation search), the calculation amount is evaluated for each of the method (1) and the method (2) described in the method of the first embodiment of the present invention.

  In the case of the method (1), N ′ objects exist at the node located in the first layer of the attribute 1 of the combination management tree. The amount of calculation when a search by range specification is performed for the N ′ objects is evaluated as follows.

As a tree for range specified, each node has two ^eight child nodes, if each child node is responsible for sub-areas of one obtained by dividing the area of the 8-dimensional space in which the parent node is responsible to 1/2 ⁸ To do. At this time, if the range specified by the search condition and a part of the assigned range of the child node overlap, it is necessary to search further after the child node, so the number of nodes that partially overlap is evaluated as the amount of calculation. (It was normalized by the total number of objects N). At this time, in the case of the method (1), the calculation amount was 9.10e-05.
In the case of the method (2), a range-specific search is performed on objects managed by each of ¹⁶ leaf nodes 2 of the tree under the first node of attribute 1 that satisfies the condition as a vertex. It will be. In this case, there are N ′ / 2 ¹⁶ = 256 objects for each leaf node. The value calculated by multiplying the calculation amount per leaf node by 2 ¹⁶ was the total calculation amount, and the calculation amount was 3.91e-03.

  As described above, it can be seen that the amount of calculation can be made smaller than the entire object search. In particular, the method (1) is considered to be more effective when the number of objects N ′ specified by the first condition specification is large as in Example 2 and the search is performed with the secondary attribute.

  The operation of each component of the resolver 20 and the object management server 30 is constructed as a program and installed and executed on a computer used as the resolver and object management server, or distributed via a network. Is possible.

  The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.

1 IP network 10 object
20 Resolver 21 Registration / Search Request Reception Unit 22 Object Name Assignment / Query Vector Generation Unit 30 Object Management Server 31 Object / Query Vector Reception Unit 32 Object Registration / Search Unit 33 Object Database 34 Tree Construction Unit

Claims (7)

This is an address resolution system in which an object connected to an information communication network has values for a plurality of attributes, and an object is searched by specifying a condition by a combination of the attribute values to identify the address of the object. And
It has a resolver and an object management server
The resolver is
Get the registration request including the address and multi-attribute information of each object, using the value of the hierarchy of attributes included in the registration request, the attribute _{i = i 1, i 2,} ..., i k, ..., and i _K , The attribute i _k has values up to the hierarchy m _k, and the value x _{i, m} in the hierarchy m of the attribute i is used as the name of the object

A name assigning means for generating an object vector composed of a set of values and sending it to the object management server together with the address of the object;
A query vector generation means for generating a query vector using a value of an attribute hierarchy in which a condition relating to each attribute included in the obtained search request is specified, and sending the query vector to the object management server;
Have
The object management server
An object database storing a combination management tree, which is a tree having nodes for managing objects for each hierarchy, by combining the attribute and the attribute value hierarchy for each attribute and the attribute value hierarchy;
Object registration means for acquiring the object vector from the resolver, referring to the combination management tree based on the object vector, and registering an object address in association with a node of the combination management tree;
Object search means for acquiring the query vector from the resolver, referring to the combination management tree based on the query vector, and acquiring an address of an object corresponding to a node of the combination management tree;
An address resolution system comprising: The object registration means
Means for registering the address of the object in all nodes in charge of the value designated by the name vector along the combination management tree;
Or
From the root of the combination management tree,

2. The address resolution system according to claim 1, further comprising: means for registering the address of the object only in the last node that has been reached. The object search means includes
In the combination management tree, from root

Means to read the object managed by the node that has reached the last,
Or
Means for reading all objects managed by the nodes belonging to the subtree having the nodes as vertices, visiting all the nodes in charge of the values specified by the query vector along the combination management tree;
The address resolution system according to claim 1, comprising: The object search means includes
When the node of the combination management tree also holds information on attributes (secondary attributes) other than the attributes (primary attributes) used when constructing the combination management tree,
Based on the query vector related to the primary attribute obtained from the resolver, from the root of the combination management tree

Means for reading the object managed by the node that has arrived last, and checking whether the object satisfies the condition relating to the secondary attribute acquired from the resolver,
Or
Based on the query vector related to the primary attribute acquired from the resolver, all nodes that are in charge of the value specified by the query vector are visited along the combination management tree, and the subtree having those nodes as vertices Means for reading an object managed by a node belonging to, and checking whether the object satisfies a condition relating to the secondary attribute acquired from the resolver;
The address resolution system according to claim 1, comprising: The combination management tree is
As a hierarchical structure of the value of the attribute i (d from i = 1), 1 L _{i, 1} types as tier value, L _{i, 2} types as values from 1 to 2 tier, 1 from M _i tier It is assumed that L _{i, Mi} values can be taken as values, and a set of values that can be taken in layers 1 to m of the attribute i is U _{i, m} ,
In the first hierarchy, prepare a node in charge of each value x _{i, 1} ∈ U _{i, 1} in the first hierarchy for the attribute i,
In the second layer, the node x _{i, 1} in the first layer is the parent, and the child nodes whose values up to the second layer of the attribute i are x _{i, 1} / x _{i, 2} ∈U _{i, 2} , and Generate a child node whose value of the first layer of attribute j (> i) is x _{j, 1} ∈U _{j, 1} ,
3 The tier, the second tier of nodes node x _{i, 1} / x _i, node ₂ under _{x i, 1 / x i,} 2 / x i, 3 and attribute j for (j> i) A node whose value in the first hierarchy is x _{j, 1} is generated as a child node, and the nodes in the second hierarchy are subordinate to the node x _{i, 1} / x _{j, 1} , up to the second hierarchy of attribute j _First generated by repeating the process of generating a node whose value is x _{j, 1} / x _{j, 2} and a child node whose value of the first layer of the attribute k (k> j) is x _k, 1 The address resolution system according to claim 1, further comprising a combination management tree generation unit. The combination management tree is
Prioritize among attributes, sort attributes in descending order of priority,
In the first layer, list only the values of the first layer of attribute 1,
In the second layer, list the values of the second layer of attribute 1 or the values of the first layer of attribute 2, and do not include the values of the first layer after attribute 3,
In the third hierarchy, list the values of the third hierarchy of attribute 1, the values of the first or second hierarchy of attribute 2, or the values of the first hierarchy of attribute 3, and the first hierarchy after attribute 4 The address resolution system according to claim 1, further comprising second combination management tree generation means that does not include a value and that is generated by repeatedly performing processing. This is an address resolution method in which an object connected to an information communication network has values for a plurality of attributes, and an object is searched by specifying a condition by a combination of the attribute values, and the address of the object is specified. And
In a system that has a resolver and an object management server,
The object management server combines the attribute and the attribute value hierarchy for each attribute and the attribute value hierarchy, and stores a combination management tree that is a tree having nodes for managing objects for each hierarchy. has an object database,
In the resolver,
Get the registration request including the address and multi-attribute information of each object, using the value of the hierarchy of attributes included in the registration request, the attribute _{i = i 1, i 2,} ..., i k, ..., and i _K , The attribute i _k has values up to the hierarchy m _k, and the value x _{i, m} in the hierarchy m of the attribute i is used as the name of the object

A naming step for generating an object vector composed of a set of values and sending the object vector together with the address of the object to the object management server;
In the object management server,
An object registration step of acquiring the object vector from the resolver, referring to the combination management tree based on the object vector, and registering an object address in association with a node of the combination management tree;
Registration process,
In the resolver,
A query vector generation step of generating a query vector using a value of an attribute hierarchy in which a condition relating to each attribute included in the acquired search request is specified, and sending the query vector to the object management server;
In the object management server,
An object search step of acquiring the query vector from the resolver, referring to the combination management tree based on the query vector, and acquiring an address of an object corresponding to a node of the combination management tree;
A search process that performs
An address resolution method comprising:

Images