Advanced Search
Japanese | English

naistar (NAIST Academic Repository) >
学術リポジトリ naistar / NAIST Academic Repository naistar >
テクニカルレポート / Technical Report >

Please use this identifier to cite or link to this item:

Title: A-tree : an index structure for high-dimensional spaces using ralative approximation
Authors: Sakurai, Yasushi
Yoshikawa, Masatoshi
Uemura, Shunsuke
Kojima, Haruhiko
サクライ, ヤスシ
ヨシカワ, マサトシ
ウエムラ, シュンスケ
コジマ, ハルヒコ
櫻井, 保志
吉川, 正俊
植村, 俊亮
児島, 治彦
Issue Date: Dec-2000
Publisher: Nara Institute of Science and Technology
Series/Report no.: Information Science Technical Report ~ TR2000011
Abstract: We propose a novel index structure, the A-tree (Approximation tree), for the similarity search of high-dimensional data. The basic idea of the A-tree is the introduction of Virtual Bounding Rectangles (VBRs) which contain and approximate MBRs or data objects. VBRs can be represented rather compactly, and thus affect the tree configuration both quantitatively and qualitatively. First, since tree nodes can contain a large number of VBR entries, fanout becomes large, which leads to fast search. More importantly, we have a free hand in arranging MBRs and VBRs in tree nodes. In the A-trees, a node contains an MBR and its children VBRs. Therefore, by fetching a node of an A-tree, we can obtain the information of the exact position of a parent MBR and the approximate position of its children. We have performed experiments using both synthetic and real data sets. For the real data sets, the A-tree outperforms the SR-tree and the VA-File in all dimensionalities up to 64 dimensions, which is the highest dimension in our experiments. The A-tree achieves 77.3%(77.7%) fewer page accesses than the SR-tree (the VA-File)for 64-dimensional real data.
ISSN: 0919-9527
Text Version: author
Appears in Collections:テクニカルレポート / Technical Report

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Copyright (c) 2007-2012 Nara Institute of Science and Technology All Rights Reserved.
DSpace Software Copyright © 2002-2010  Duraspace - Feedback