Multidimensional B-trees for associative searching in database systems

Peter Scheuermann; Mohamed Ouksel

doi:10.1016/0306-4379(82)90024-2

Multidimensional B-trees for associative searching in database systems

Peter Scheuermann^*, Mohamed Ouksel

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

51 Scopus citations

Abstract

A new method for multiple attribute indexing, the Multidimensional B-Tree (MBDT), is developed. This method is well suited for dynamic databases, since it handles several types of associative queries efficiently and requires low-cost maintenance. Algorithms and search strategies for exact match, partial match, and range queries are presented and statistical procedures are given to estimate the average and worst case retrieval times. The applicability of our organization to practical databases is discussed and analytical tradeoffs with regard to index organizations based on k-d trees are established.

Original language	English (US)
Pages (from-to)	123-137
Number of pages	15
Journal	Information Systems
Volume	7
Issue number	2
DOIs	https://doi.org/10.1016/0306-4379(82)90024-2
State	Published - 1982

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture

Access to Document

10.1016/0306-4379(82)90024-2

Cite this

@article{5d0129a173414d4299f787afd2d0bc8c,

title = "Multidimensional B-trees for associative searching in database systems",

abstract = "A new method for multiple attribute indexing, the Multidimensional B-Tree (MBDT), is developed. This method is well suited for dynamic databases, since it handles several types of associative queries efficiently and requires low-cost maintenance. Algorithms and search strategies for exact match, partial match, and range queries are presented and statistical procedures are given to estimate the average and worst case retrieval times. The applicability of our organization to practical databases is discussed and analytical tradeoffs with regard to index organizations based on k-d trees are established.",

author = "Peter Scheuermann and Mohamed Ouksel",

note = "Funding Information: tThe work of this author was supported in part by the Algerian government.",

year = "1982",

doi = "10.1016/0306-4379(82)90024-2",

language = "English (US)",

volume = "7",

pages = "123--137",

journal = "Information Systems",

issn = "0306-4379",

publisher = "Elsevier Ltd",

number = "2",

}

TY - JOUR

T1 - Multidimensional B-trees for associative searching in database systems

AU - Scheuermann, Peter

AU - Ouksel, Mohamed

N1 - Funding Information: tThe work of this author was supported in part by the Algerian government.

PY - 1982

Y1 - 1982

N2 - A new method for multiple attribute indexing, the Multidimensional B-Tree (MBDT), is developed. This method is well suited for dynamic databases, since it handles several types of associative queries efficiently and requires low-cost maintenance. Algorithms and search strategies for exact match, partial match, and range queries are presented and statistical procedures are given to estimate the average and worst case retrieval times. The applicability of our organization to practical databases is discussed and analytical tradeoffs with regard to index organizations based on k-d trees are established.

AB - A new method for multiple attribute indexing, the Multidimensional B-Tree (MBDT), is developed. This method is well suited for dynamic databases, since it handles several types of associative queries efficiently and requires low-cost maintenance. Algorithms and search strategies for exact match, partial match, and range queries are presented and statistical procedures are given to estimate the average and worst case retrieval times. The applicability of our organization to practical databases is discussed and analytical tradeoffs with regard to index organizations based on k-d trees are established.

UR - http://www.scopus.com/inward/record.url?scp=0020277962&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020277962&partnerID=8YFLogxK

U2 - 10.1016/0306-4379(82)90024-2

DO - 10.1016/0306-4379(82)90024-2

M3 - Article

AN - SCOPUS:0020277962

SN - 0306-4379

VL - 7

SP - 123

EP - 137

JO - Information Systems

JF - Information Systems

IS - 2

ER -

Multidimensional B-trees for associative searching in database systems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this