kd-tree(1975)资源-CSDN文库

kd-tree

需积分: 9 141 浏览量 2010-04-29 17:44:54 上传评论收藏 940KB PDF 举报

资源推荐

资源详情

资源评论

1975 ACM Student Award

Paper: Second Place

Multidimensional

Binary Search Trees

Used for Associative

Searching

Jon Louis Bentley

Stanford University

This paper develops the multidimensional binary

search tree (or k-d tree, where k is the dimensionality

of the search space) as a data structure for storage of

information to be retrieved by associative searches. The

k-d tree is defined and examples are given. It is shown to

be quite efficient in its storage requirements. A signifi-

cant advantage of this structure is that a single data

structure can handle many types of queries very effici-

ently. Various utility algorithms are developed; their

proven average running times in an n record file are : in-

sertion, O(log n); deletion of the root, 0 (n (k--1)/k) ; dele-

tion of a random node, O(log n); and optimization (guar-

antees logarithmic performance of searches), 0 (n log n).

Search algorithms are given for partial match queries

with t keys specified [proven maximum running time

of O (n (k-t)/k) ] and for nearest neighbor queries [em-

pirically observed average running time of O(log n). ]

These performances far surpass the best currently known

algorithms for these tasks. An algorithm is presented to

handle any general intersection query. The main focus

of this paper is theoretical. It is felt, however, that k-d

trees could be quite useful in many applications, and ex-

amples of potential uses are given.

Key Words and Phrases: associative retrieval, binary

search trees, key, attribute, information retrieval

system, nearest neighbor queries, partial match queries,

intersection queries, binary tree insertion

CR Categories: 3.63, 3.70, 3.74, 4.49

General permission to republish, but not for profit, all or part

of this material is granted provided that ACM's copyright notice

is given and that reference is made to the publication, to its date

of issue, and to the fact that reprinting privileges were granted

by permission of the Association for Computing Machinery.

This paper was

awarded Second Place in ACM's 1975 George

E. Forsythe Student Paper Competition.

Author's present address: Department of Computer Science,

University of North Carolina at Chapel Hill, Chapel Hill, NC 27514.

509

1. Introduction

The problem of associative retrieval (often referred

to as

retrieval by secondary key)

centers around a file F

which is a collection of records. Each record R of F is

an ordered k-tuple

(Vo, vl, ...,

Vk_l) of values which

are the

keys,

attributes,

of the record. A retrieval of

records from F is initiated at the request of the user,

which could be either mechanical or human. A retrieval

request is called a

query

of the file, and specifies certain

conditions to be satisfied by the keys of the records it re-

quests to be retrieved from F. An information retrieval

system must be capable of initiating an appropriate

search upon the arrival of a query to that system. If a

query is allowed to specify conditions dealing with a

multiplicity of the keys, the searches performed by the

system are considered associative. If the user of the sys-

tem is restricted to specifying conditions for only one

of the keys, the resulting search is not considered to be

associative (in that case only one of the keys is consid-

ered to be "the key" and the remaining attributes are

referred to as "data").

Numerous methods exist for building an informa-

tion retrieval system capable of handling such associa-

tive queries. Among these are inverted files, methods of

compounding attributes, superimposed coding systems,

and combinatorial hashing. Knuth [5] discusses these

ideas in detail. McCreight [6] has proposed that the

keys be "shuffled" together bitwise; then unidimensional

retrieval algorithms could be used to answer certain

queries. Rivest investigated in his thesis [7] the use of

binary search tries (see [5] for a detailed discussion of

tries) to store records when they are composed of binary

keys. Finkel and Bentley [3] discuss a data structure,

quad trees, that stores the records of the file in a tree

whose nodes have out-degree of 2k; theirs was the first

general approach to use a tree structure. None of the

above approaches seem to provide a "perfect" environ-

ment for associative retrieval. Each of them falls short

in some very important way, either in having only a

small class of queries easily performed, large running

time, large space requirements, horrible worst cases, or

some other adverse properties.

This paper presents a new type of data structure for

associative searching, called the multidimensional bi-

nary search tree or k-d tree, which is defined in Section

2. In Section 3 an efficient insertion algorithm is given

and analyzed. Many types of associative searches are

discussed in Section 4, and the k-d tree is shown to

perform quite well in all of them. Its worst case per-

formance in partial match searches is analyzed and is

shown to equal the best previously attained average

performance. A search algorithm is presented that can

answer any intersection query. An algorithm given

seems to solve the nearest neighbor problem in logarith-

mic time; its running time is much less than any other

known method. In Section 5 deletion is shown to be

possible in k-d trees, and it is analyzed. Section 6 dis-

Communications September 1975

of Volume 18

the ACM Number 9

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余8页未读，立即下载

评论收藏

内容反馈

freetoday1

粉丝: 0
资源: 2

kd-tree(1975)

在工具栏上添加通用控件

KD-Tree 开源实现以及 OpenCV KD-Tree 使用

kd-tree的基本教程PDF

KD-tree详细权威资料

KD-Tree源代码

KD-Tree C++程序

kd-tree算法 matlab

基于KD-Tree实现的近似查询处理AQP问题python源码(课程大作业).zip

Real-Time KD-Tree Construction on Graphics Hardware

kd-tree c++ 实现

基于c的kd-tree实现方法.zip

KD-Tree 介绍教程

二维点云配准+kd-tree相结合+三角剖分

通过matlab建立Kd-tree并进行k-NN查询

kd-Tree源码（c++）

kd-Tree c++实现（kd树）

sift+kd-tree

KD-tree test

一种基于OpenCL的KD-Tree构造的并行优化算法

Kd-tree改进后的BBF算法

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）