Copy
Hisashi SUZUKI, Suguru ARIMOTO, "Dynamic Construction and Quick Search Algorithms of Binary Balanced Trees with a Fidelity Criterion" in IEICE TRANSACTIONS on Fundamentals,
vol. E74-A, no. 9, pp. 2483-2494, September 1991, doi: .
Abstract: This paper proposes () an algorithm that dynamically constructs an asymptotically-balanced binary tree to store successively-given keys without knowledge of the distribution of key occurence, and () another algorithm for quick key search over the constructed tree such that: If the tree has in memory at least a key that is inside the Δ-neighbor (in a Hamming space) of a reference key, then the algorithm can find one of such Δ-neighbor keys almost with probability 1. The memory capacity required to describe a tree in the tree construction algorithm is of order being proportional to the number l of keys already processed. For an independently and idenically distributed binary source of generating keys, the mean computation time required to update a tree for every key input can be of an order being a little higher than (log2l)2log2(log2l), and that required to search a Δ-neighbor key can be of an order being a little higher than (log2l)3.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_9_2483/_p
Copy
@ARTICLE{e74-a_9_2483,
author={Hisashi SUZUKI, Suguru ARIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Dynamic Construction and Quick Search Algorithms of Binary Balanced Trees with a Fidelity Criterion},
year={1991},
volume={E74-A},
number={9},
pages={2483-2494},
abstract={This paper proposes () an algorithm that dynamically constructs an asymptotically-balanced binary tree to store successively-given keys without knowledge of the distribution of key occurence, and () another algorithm for quick key search over the constructed tree such that: If the tree has in memory at least a key that is inside the Δ-neighbor (in a Hamming space) of a reference key, then the algorithm can find one of such Δ-neighbor keys almost with probability 1. The memory capacity required to describe a tree in the tree construction algorithm is of order being proportional to the number l of keys already processed. For an independently and idenically distributed binary source of generating keys, the mean computation time required to update a tree for every key input can be of an order being a little higher than (log2l)2log2(log2l), and that required to search a Δ-neighbor key can be of an order being a little higher than (log2l)3.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Dynamic Construction and Quick Search Algorithms of Binary Balanced Trees with a Fidelity Criterion
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2483
EP - 2494
AU - Hisashi SUZUKI
AU - Suguru ARIMOTO
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1991
AB - This paper proposes () an algorithm that dynamically constructs an asymptotically-balanced binary tree to store successively-given keys without knowledge of the distribution of key occurence, and () another algorithm for quick key search over the constructed tree such that: If the tree has in memory at least a key that is inside the Δ-neighbor (in a Hamming space) of a reference key, then the algorithm can find one of such Δ-neighbor keys almost with probability 1. The memory capacity required to describe a tree in the tree construction algorithm is of order being proportional to the number l of keys already processed. For an independently and idenically distributed binary source of generating keys, the mean computation time required to update a tree for every key input can be of an order being a little higher than (log2l)2log2(log2l), and that required to search a Δ-neighbor key can be of an order being a little higher than (log2l)3.
ER -
English
