| |
|
|
|
Registro Completo |
|
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 |
|
Marc: |
LEADER 01419nam a2200229 a 4500
001 1003669
005 2011-02-18
008 1995 bl uuuu t 00u1 u #d
100 1 $aNASCIMENTO, M. A.
245 $aA mapping-based approach for range indexing.
260 $aDallas: Southern Methodist University$c1995
300 $a27 p.
490 $a(Technical Report, 95-CSE-14).
520 $aIn 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.
650 $aAlgorithms
650 $aDatabases
653 $aAlgoritmo
653 $aÁrvore B+-
653 $aBases de dados histórica
653 $aIndexação
700 1 $aDUNHAM, M. H.
700 1 $aKOURAMAJIAN, V.
Download
Esconder MarcMostrar Marc Completo |
|
Registro original: |
Embrapa Agricultura Digital (CNPTIA) |
|
|
Biblioteca |
ID |
Origem |
Tipo/Formato |
Classificação |
Cutter |
Registro |
Volume |
Status |
URL |
Voltar
|
|
|
| Registros recuperados : 55 | |
| Registros recuperados : 55 | |
|
| Nenhum registro encontrado para a expressão de busca informada. |
|
|
