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.
Ryoichi KAWAHARA
NTT Corporation
Hiroshi SAITO
NTT Corporation
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Ryoichi KAWAHARA, Hiroshi SAITO, "Name Resolution Based on Set of Attribute-Value Pairs of Real-World Information" in IEICE TRANSACTIONS on Communications,
vol. E100-B, no. 1, pp. 110-121, January 2017, doi: 10.1587/transcom.2016EBP3005.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2016EBP3005/_p
Copy
@ARTICLE{e100-b_1_110,
author={Ryoichi KAWAHARA, Hiroshi SAITO, },
journal={IEICE TRANSACTIONS on Communications},
title={Name Resolution Based on Set of Attribute-Value Pairs of Real-World Information},
year={2017},
volume={E100-B},
number={1},
pages={110-121},
abstract={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.},
keywords={},
doi={10.1587/transcom.2016EBP3005},
ISSN={1745-1345},
month={January},}
Copy
TY - JOUR
TI - Name Resolution Based on Set of Attribute-Value Pairs of Real-World Information
T2 - IEICE TRANSACTIONS on Communications
SP - 110
EP - 121
AU - Ryoichi KAWAHARA
AU - Hiroshi SAITO
PY - 2017
DO - 10.1587/transcom.2016EBP3005
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E100-B
IS - 1
JA - IEICE TRANSACTIONS on Communications
Y1 - January 2017
AB - 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.
ER -