Accession Number:

ADA106550

Title:

The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Robinson,John T.

Report Date:

1981-02-01

Pagination or Media Count:

24.0

Abstract:

The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By large it is meant that most of the index must be stored on secondary memory. By dynamic it is meant that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand. A new data structure, the K-D-B-tree, is presented as a solution to this problem. K-D-B-trees combine properties of K-D-trees and B-trees. It is expected that the multidimensional search efficiency of balanced K-D-trees and the IO efficiency of B-trees should both be approximated in the K-D-B-tree. Preliminary experimental results that tend to support this are reported. Author

Descriptors:

• *MATHEMATICAL MODELS
• *STOCHASTIC PROCESSES
• *DATA MANAGEMENT
• *INDEXES
• *INFORMATION THEORY
• DATA BASES
• DYNAMICS
• EFFICIENCY
• INPUT OUTPUT PROCESSING
• SEARCHING
• INFORMATION RETRIEVAL
• INTERROGATION

Subject Categories:

• Statistics and Probability
• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE