Data/hora: 25/05/2024 17:50:02

Biblioteca(s): | Embrapa Agricultura Digital.
Data corrente: | 30/09/1996
Data da última atualização: | 18/02/2011
Autoria: | NASCIMENTO, M. A.; DUNHAM, M. H.; KOURAMAJIAN, V.
Afiliação: | MARIO A. NASCIMENTO, CNPTIA; MARGARET H. DUNHAM, Southern Methodist University; VRAM KOURAMAJIAN, Wichita State University.
Título: | A mapping-based approach for range indexing.
Ano de publicação: | 1995
Fonte/Imprenta: | Dallas: Southern Methodist University, 1995.
Páginas: | 27 p.
Série: | (Technical Report, 95-CSE-14).
Idioma: | Inglês
Conteúdo: | In this paper we present an indexing structure for ranges. The main idea is to map a bounded range to a point in one-dimensional space, using a standard B+-tree to index such a point. The indexing structure is storage-wise efficient, requiring O(N), where N is the number of indexed ranges. Its maintainance is also efficient, requiring O(log N) accesses per update. We also show that it is able to efficaciously answer a number of different queries, requiring, for instance, O(log N + L) I/Os to answer an intersection type of query, where L is the length of the range given in the query. An analytical performance study is also presented. Finally, we point out two immediate applications of this indexing approach, which are (1) answering stabbing queries and (2) the indexing of a valid-time (historical) database.
Palavras-Chave: | Algoritmo; Árvore B+-; Bases de dados histórica; Indexação.
Thesaurus Nal: | Algorithms; Databases.
Categoria do assunto: | X Pesquisa, Tecnologia e Engenharia
Registro original: | Embrapa Agricultura Digital (CNPTIA)
Exemplares: | CNPTIA - (4304-1) - UPC - RT - PP -  -  - 1996.00006 - DIS