| |
|
|
|
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.; ELMASRI, R. |
|
Afiliação: |
MARIO A. NASCIMENTO, CNPTIA; MARGARET H. DUNHAM, Southern Methodist University; RAMEZ ELMASRI, University of Texas. |
|
Título: |
Performance of the MAP21 access structure for temporal ranges. |
|
Ano de publicação: |
1996 |
|
Fonte/Imprenta: |
Dallas: Southern Methodist University, 1996. |
|
Páginas: |
21 f. |
|
Série: |
(Technical Report, 96-CSE-02) |
|
Idioma: |
Inglês |
|
Conteúdo: |
This paper introduces MAP21, a mapping-based indexing approach for ranges. Although MAP21 can be used in many applications where ranges need to be indexed, we focus on the domain of temporal databases in particular. MAP21 allows proactive and retroactive updates, uses O (N) space, and has O(log N) update time and O(log N + L) query processing time. Here N is the number of indexed ranges and L is the length of the range given in the query's input. A simple extension to MAP21 allows it to index open-ended ranges as well. We present the structure of MAP21 and search algorithms, with correctness arguments, for range queries and also compare its performance against the Time Index. We show that MAP21 performs better than the Time Index in a majority of cases while it is always more efficient regarding space requirements and update time. |
|
Palavras-Chave: |
Bases de dados temporais; Indexação baseada em mapas. |
|
Thesaurus Nal: |
Computer science; Databases. |
|
Categoria do assunto: |
X Pesquisa, Tecnologia e Engenharia |
|
Marc: |
LEADER 01425nam a2200205 a 4500
001 1003676
005 2011-02-18
008 1996 bl uuuu t 00u1 u #d
100 1 $aNASCIMENTO, M. A.
245 $aPerformance of the MAP21 access structure for temporal ranges.
260 $aDallas: Southern Methodist University$c1996
300 $a21 f.
490 $a(Technical Report, 96-CSE-02)
520 $aThis paper introduces MAP21, a mapping-based indexing approach for ranges. Although MAP21 can be used in many applications where ranges need to be indexed, we focus on the domain of temporal databases in particular. MAP21 allows proactive and retroactive updates, uses O (N) space, and has O(log N) update time and O(log N + L) query processing time. Here N is the number of indexed ranges and L is the length of the range given in the query's input. A simple extension to MAP21 allows it to index open-ended ranges as well. We present the structure of MAP21 and search algorithms, with correctness arguments, for range queries and also compare its performance against the Time Index. We show that MAP21 performs better than the Time Index in a majority of cases while it is always more efficient regarding space requirements and update time.
650 $aComputer science
650 $aDatabases
653 $aBases de dados temporais
653 $aIndexação baseada em mapas
700 1 $aDUNHAM, M. H.
700 1 $aELMASRI, R.
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 : 4 | |
| Registros recuperados : 4 | |
|
| Nenhum registro encontrado para a expressão de busca informada. |
|
|
