Name Resolution Based on Set of Attribute-Value Pairs of Real-World Information

Ryoichi KAWAHARA  Hiroshi SAITO  

Publication
IEICE TRANSACTIONS on Communications   Vol.E100-B   No.1   pp.110-121
Publication Date: 2017/01/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2016EBP3005
Type of Manuscript: PAPER
Category: Network
Keyword: 
real world information,  name resolution,  curse of dimensionality,  searching algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
It is expected that a large number of different objects, such as sensor devices and consumer electronics, will be connected to future networks. For such networks, we propose a name resolution method for directly specifying a condition on a set of attribute-value pairs of real-world information without needing prior knowledge of the uniquely assigned name of a target object, e.g., a URL. For name resolution, we need an algorithm to find the target object(s) satisfying a query condition on multiple attributes. To address the problem that multi-attribute searching algorithms may not work well when the number of attributes (i.e., dimensions) d increases, which is related to the curse of dimensionality, we also propose a probabilistic searching algorithm to reduce searching time at the expense of a small probability of false positives. With this algorithm, we choose permutation pattern(s) of d attributes to use the first K (K « d) ones to search objects so that they contain relevant attributes with a high probability. We argue that our algorithm can identify the target objects at a false positive rate less than 10-6 and a few percentages of tree-searching cost compared with a naive d-dimensional searching under a certain condition.