Asignatura de
Estructuras de Datos Multidimensionales
Concepto
y Definición
Asignatura de carácter avanzado en la que se
estudia el diseño y la implementación de las estructuras de datos
multidimensionales más importantes, con un orden creciente de complicación, que
se aplican para conducir conjuntamente con sus procedimientos de manipulación a
la satisfacción de las peticiones asociativas. No se restringe a sólo una
presentación de cada una de las estructuras, ni de sus procesos de
mantenimiento, sino que además se desea transmitir al discente ideas de
discusión y de comparación de sus realizaciones. Esta presentación ha de
parecer al alumno no como un producto acabado impermeable, duro y frío sino más
bien, como una aproximación, aunque no total, de su realidad evolutiva.
Objetivos
didácticos
El alumno conocedor de las estructuras monodimensionales, cursadas anteriormente, ha visto que el micromundo de las peticiones de información en tales tipos
de estructuras es restringido. Sólo es capaz de dilucidar si un determinado
valor de clave se encuentra o no en la base de datos; todo lo más, recuperar un
conjunto de valores de clave acotados por unos límites, realizando búsquedas
que se denominan no-asociativas. Es muy importante que el alumno absorba una
visión general del estado actual de la materia, de forma que sea capaz de
proponer variadas y certeras clasificaciones de las estructuras estudiadas, en
función de diversos parámetros aplicables. Ya sea dentro de una familia de
estructuras, o bien en el ámbito general, deberá aprender la forma de
establecer las adecuadas comparaciones y valoraciones de los métodos estudiados
respecto al espacio de almacenamiento utilizado y el tiempo aplicado a la
contestación de las peticiones multidimensionales planteables.
Debe hacerse especial hincapié en la relativización de estos valores ante la
diversidad de los tipos de peticiones y de los grados de dinamicidad
solicitables. Por último, es fundamental posibilitar
la participación activa del alumno en el proceso de sedimentación de los
conocimientos. Para ello se pretende conseguir que el discente plantee, teórica
y prácticamente, las variaciones aplicables a las diversas estructuras
presentadas, y desarrolle los procesos de resolución de peticiones y de
mantenimiento más adecuados para cada posible modificación sugerida. Asimismo,
realizará las valoraciones pertinentes, tanto teóricas como empíricas, de los
parámetros adecuados a la estructura, en un proceso que traerá como
consecuencia una mejor comprensión y clasificación del nuevo método de
indización dentro del esquema general presentado.
Sistema
de Evaluación
Se valorará la realización y presentación de
trabajos teóricos y prácticos. Al mismo tiempo se tendrá en cuenta la
asistencia y activa participación en las clases. Por último, se realizará una
prueba escrita, a fin de curso, que ponga de manifiesto la asimilación y
aprovechamiento adecuados de los conocimientos detallados en el temario.
Programa
de la asignatura
Tema
0.- Estructuras de datos multidimensionales. Objetivos, Programa,
Justificación del contenido. Diapositivas.
Módulo 1.- Perspectiva Monodimensional.
Métodos
separativos.
Tema 1.- Ficheros invertidos y multilistas. Diapositivas.
Tema 2.- Ordenación multiclave.
Diapositivas.
Métodos integrados secuenciales.
Tema 3.- Códigos superpuestos. Diapositivas.
Métodos integrados arbóreos con agregación de claves.
Tema 4.- Indices
combinados. Diapositivas.
Tema 5.- Multiclaves
fundidas en monoclave. Diapositivas.
Módulo 2.- Integración arbórea.
Claves
independientes.
Tema 6.- Árbol Cuaternario. Diapositivas.
Tema 7.- Árbol de múltiples claves (Árbol mc). Diapositivas.
Tema 8.- Árbol binario k-dimensional (Árbol
kd). Diapositivas.
Tema 9.- Árbol de división binaria
k-dimensional con expresión de zona discriminadora (Árbol bd).
Diapositivas.
Tema 10.- Árbol k-dimensional equilibrado en altura
(Árbol kdea). Diapositivas.
Tema 11.- Árbol Quintario.
Diapositivas.
Tema 12.- Árbol b multidimensional (Árbol bm). Diapositivas.
Tema 13.- Árbol b con división del tipo árbol kd (Árbol kdb).
Propiedad del espacio de las claves.
Tema 14.- Árbol de Burkhard
y Keller (Árbol bk). Diapositivas.
Módulo 3.- Acceso directo.
Dispersión
con agregación de claves.
Extensibles.
Tema 15.- Búsquedas parciales basadas en la
dispersión extensible. Diapositivas.
Lineales.
Tema 16.- Búsquedas parciales basadas en la
dispersión lineal. Diapositivas.
Dispersión con claves independientes.
Extensibles.
Tema 17.- Dispersión extensible multidimensional.
Diapositivas.
Lineales.
Tema 18.- Dispersión lineal multidimensional. Diapositivas.
Tema 19.- Dispersión digital multidimensional. Diapositivas.
Organización enrejada.
Tema 20.- Organización enrejada. Diapositivas.
Documentación
Elaborada en el seno del GIED: Estructuras de
Datos Multidimensionales, 470 páginas. Publicado en pdf
(06/03/2003)
Módulo 1.- Perspectiva Monodimensional.
Módulo 2.- Integración arbórea (I).
Módulo 2.- Integración arbórea (II).
Bibliografía
de consulta
[BB76] BENTLEY, J.L.; BURKHARD, W.A.:
"Heuristics for Partial-Match Retrieval Database Design". Information Processing Letters, Vol. 4, 5, 132/135, (1976).
[BE] BECKLEY, D.A.; EVENS, M.W.;
RAMAN, V.K.: "An Experiment with Balanced and Unbalanced K-D Trees for
Associative Retrieval". Report Inst. Techn.
Chicago, 1/28.
[BE75] BENTLEY, J.L.: "Multidemensional Binary Search Trees Used for Associative
Searching". Communications of the ACM, Vol. 18, 9,
509/516, (1975).
[BE79] BENTLEY, J.L.:
"Multidimensional Binary Search Trees in Database Applications". IEEE Transactions on Software Engineering, Vol. SE-5, 4, 333/340,
(1979).
[BE85a] BECKLEY, D.A.; EVENS, M.W.;
RAMAN, V.K.: "Multikey Retrieval from K-D Trees
and Quad-Trees". AT&T Bell Laboratories Naperville, Ill, Go 566, 1/29,
(1985).
[BE85b] BECKLEY, D.A.; EVENS, M.W.;
RAMAN, V.K.: "Empirical Comparison of Associative File
Structures". Foundations of Data Organization,
Proceedings of the International Conference, Kyoto-Japon,
315/319, (1985).
[BF79] BENTLEY, J.L.; FRIEDMAN, J.H.:
"Data structures for range searching". Computing
Surveys, Vol. 11, 4, 397/409, (1979).
[BK73] BURKHARD, W.A.; KELLER, R.M.:
"Some Approaches to Best-Match File Searching". Communications
of the ACM, Vol. 16, 4, 230/236, Abril (1973).
[BM80] BENTLEY, J.L.; MAURER, H.A.:
"Efficient Worst-Case Data Structures for Range Searching". Acta Informatica, 13, 155/168, (1980).
[BS75] BENTLY, J.L.; STANAT, D.F.:
"Analysis of Range Searches in Quad Trees". Information
Processing Letters, Vol. 3, 6, 170/173, Julio (1975).
[BW80] BENTLEY, J.L.; WOOD, D.:
"An Optimal Worst Case Algorithm for Reporting Intersections of
Rectangles". IEEE Transactions on Computers, Vol. C-29,
7. 571/577, (1980).
[CA75] CARDENAS, A.F.: "Analysis
and Performance of Inverted Database Structures". Communications
of the ACM, Vol. 18, 5, 253/262, (1975).
[CF81] CHANG, J.; FU, K.:
"Extended K-D Tree Database Organization: A Dynamic Multiattribute
Clustering Method". IEEE Transactions on Software
Engineering, Vol. SE-7, 3, 284/290, (1981).
[CH88] CHAZELLE, B.: "A
Functional Approach to Data Structures and its Use in Multidimensional
Searching". SIAM J. Comput, Vol. 17, 3, 427/462,
(1988).
[CL90] CUNTO, W.; LAU, G.; FLAJOLET,
P.: "Analysis of KDT-Trees: KD-Trees Improved by Local Reorganisations".
Submitted to J. of Algorithms, 1/12, (1990).
[CO85] COLOMB, R.M.: "Use of
Superimposed Code Words for Partial Match Data Retrieval". The Australian Computer Journal, Vol. 17, 4, 181/188, (1985).
[CS75] CARDENAS, A.F.; SAGAMANG, J.P.:
"Doubly-chained tree data base organisation --
analysis and design strategies". The Computer Journal,
Vol. 20, 1, 15/26, (1975).
[CY78] CLAYBROOK, B.G.; YANG, C.-S.:
"Efficient Algorithms for Answering Queries with Unsorted Multilists". Inform. Systems, Vol.
3, 93/97, Pergamon Press, (1978).
[DE80] DELANNOY, C.: "Un algorithme rapide de recherche de plus proches voisins". R.A.I.R.O. Informatique-Computer Science, Vol. 14, 3, 275/286, (1980).
[DL76] DOBKIN, D.; LIPTON, R.J.:
"Multidimensional Searching Problems". Siam J. Comput.,
Vol. 5, 2, 181/186, (1976).
[DS84] DANDAMUDI, S.P.; SORENSON,
P.G.: "Algortihms for the BD Tree
Structure". Tech. Rep. 84-11, Department of Computational Science,
University of Saskatchewan, Saskatoon, Canadá,
(1984).
[DS85] DANDAMUDI, S.P.; SORENSON,
P.G.: "An Empirical Performance Comparison of Some Variations of the K-D
Tree and BD Tree". International Journal of Computer and information
Sciences, Vol. 14, 3, 134/158, (1985).
[DS88a] DIAZ, M.; SANTANA, O.;
RODRIGUEZ, G.; MARTIN, M.: "Reorganizaciones
locales en el árbol K-D-B. Su eficiencia en situaciones
dinámicas". Actas de la XIV Conferencia Latinoamericana de Informática,
Buenos Aires, Argentina, Vol. I, 17/32, Septiembre, (1988).
[DS88b] DIAZ, M.; SANTANA, O.;
RODRIGUEZ, G.; RODRIGUEZ, N.: "Efecto de la distancia en la eficiencia de
la búsqueda de los m-vecinos más próximos en el árbol de Burkhard-Keller".
Report interno Departamento de Informática y
Sistemas, Universidad de Las Palmas de G.C., 1/13, Diciembre, (1988).
[EA81]
EASTMAN, C.M.: "Optimal Bucket Size for Nearest Neighbour
Searching in K-D Trees". Information Processing Letters,
Vol. 12, 4, 165/167, (1981).
[EA87] EASTMAN, C.M.: "Optimal
Bucket Size for Multiattribute Retrieval in
Partitioned Files". Inf. Systems, Vol. 12, 4, 375/383,
(1987).
[EW80] EASTMAN, C.M.; WEISS, S.F.:
"A Tree Algorithm for Nearest Neighbour
Searching in Document Retrieval Systems". Report Dept. Math., Florida
State University, 131/149, (1980).
[EW82] EASTMAN, C.M.; WEISS, S.F.:
"Tree Structures for High Dimensionality Nearest Neighbour Searching". Inform. Systems,
Vol. 7, 2, 115/122, (1982).
[EZ82] EASTMAN, C.M.; ZEMANKOVA, M.:
"Partially Specified Nearest Neighbour Searches
Using K-D Trees". Information Processing Letters, Vol.
15, 2, 53/56, (1982).
[FA79] FAGIN, R.; NIEVERGELT, J.;
PIPPENGER, N.; STRONG H.: "Extendible hashing-A fast Access method for
dynamic files". ACM TODS 4(3):315/344, (1979).
[FA86] FALOUTSOS, C.: "Multiattribute Hashing Using Gray Codes". SIGMOD Rec.,
Vol. 15, 2, 227/238, (1986).
[FB74] FINKEL, R.A.; BENTLEY, J.L.:
"Quad Trees A Data Structure for Retrieval on Composite Keys". Acta Informatica, 4, 1/9, Springer Verlag,
(1974).
[FB77] FRIEDMAN, J.H; BENTLEY, J.L.;
FINKEL, R.A.: "An Algorithm for Finding Best Matches in Logarithmic
Expected Time". ACM Transactions on Mathematical
Software, Vol. 3, 3, 209/226, Septiembre, (1977).
[FB87] FONTAYNE, Y.D.; BOWMAN, R.J.:
"The Multiple Storage Radix Hash Tree: An Improved Region Query Data
Structure". IEEE International Conference on Computer-Aided Design:
ICCAD-87, Digest of Technical Papers, 302/305, (1987).
[FN75] FUKUNAGA, K.; NARENDRA, P.M.:
"A Branch and Bound Algorithm for Computing K-Nearest Neighbours".
IEEE Transactions on Computers, 750/753, Julio (1975).
[FP86] FLAJOLET, P.; PUECH, C.:
"Partial Match Retrieval of Multidimensional Data". J. Assoc. Comput. Mach., Vol. 33, 2, 371/407,
(1986).
[GK80] GÜTING, H.; KRIEGEL, H.P.:
"Multidimensional B-Tree: An Efficient Dynamic File Structure for Exact
Match Queries". Forschungsbericht NR: 105, 1/18,
(1980).
[GL78] GABBE, J.D.; LONDON, T.B.;
MILLER, R.; BEYER, J.D.: "Applications of Superimposed Conding
to Partial-Match Retrieval". IEEE, 464/469, (1978).
[HI85] HINRICHS, K.:
"Implementation of the Grid File: Design Concepts and Experience". Bit, 25, 569/592, (1985).
[HN83] HINRICHS, K.; NIEVERGELT, J.:
"The Grid File: A Data Structure Designed to Support Proximity Queries on
Spatial Objects". Institut fur Informatik, ETH, CM-8092 Zurich, 100/113, (1983).
[HO87] HOUTHEYS, P.: "Box Sort, a
Multidimensional Binary Sorting Method for Rectangular Boxes, Used for Quick
Range Searching". Vis. Comput., Vol. 3, 4,
236/249, (1987).
[HU85] HUANG, S.S.:
"Multidimensional Extendible Hashing for Partial-Match Queries". International Journal of Computer and Information Sciences, Vol.
14, 2, 73/81, Abril (1985).
[HY82] HOSHI, M.; YUBA, T.: "A
Counter Example to a Monotonicity Property of K-D
Trees". Information Processing Letters, Vol. 15, 4,
169/173, (1982).
[IN72] INGLIS, J.: "Inverted
Indexes and Multi-List Structures". The Computer Journal, Vol. 17, 1, 59/63, (1972).
[KO76] KOLLIAS, J.G.: "The
Selection of Secondary File Organizations". Management Datamatics, Vol. 5, 6, 241/250, (1976).
[KO79] KOLLIAS, J.G.: "A
Heuristic Approach for Determining the Optimal Degree of File Inversion".
Inform. Systems, Vol. 4, 307/318, (1979).
[KO80] KOCHIN, Y.Y.:
"Organization of Inverted Search in Dynamic Files". Management Information
Systems, 723/727, Translated from Avtomatika i Telemekhanika, 5, 164/171, Mayo
(1980).
[KR84] KRIEGEL, H.P.:
"Performance Comparison of Index Structures for Multi-Key Retrieval".
ACM, 186/196, (1984).
[KS77] KASHYAP, R.L.; SUBAS, S.K.C.;
BING YAO, S.: "Analysis of the Multiple-Attribute-Tree Data-Base
Organization". IEEE Transactions on Software
Engineering, Vol. SE-3, 6, 451/467, (1977).
[LR82] LLOYD, J.W.; RAMAMOHANARAO, K.:
"Partial-Match Retrieval for Dynamic Files". Bit,
22, 150/168, (1982).
[LT76] LEE, R.C.T.; TSENG, S.H.:
"Multy-Key Sorting". Policy Analysis and Informations Systems, 1/20,
(1976).
[LU70] LUM, V.Y.:
"Multi-Attribute Retrieval with Combined Indexes". Communications
of the ACM, Vol. 13, 11, 660/665, (1970).
[LU78] LUEKER, G.S.: "A Data
Structure for Orthogonal Range Queries". IEEE, 28/34,
(1978).
[LW80] LEE, D.T.; WONG, C.K.: "Quintary Trees: A File Structure for Multidimensional
Database Systems". ACM Transactions on Database Systems,
Vol. 5, 3, 339/353, (1980).
[LY76] LIOU, J.H.; YAO, S.B.:
"Multi-Dimensional Clustering for Database Organizations". Inform. Systems, Vol. 2, 187/198, (1976).
[MC85] McCREIGHT,
E.M.: "Priority Search Trees". SIAM J. Comput.,
Vol. 14, 2, 257/276, (1985).
[ME78] MERRETT, T.H.:
"Multidimensional Paging for Efficient Database Querying". School of Computer Science, McGill University Montreal, Canada,
277/289, (1978).
[MS86] MURPHY, O.J.; SELKOW, S.M.:
"The Efficiency of Using K-D Trees for Finding Nearest
Neighbours in Discrete Space". Inf. Process. Lett.,
Vol. 23, 4, 215/218, (1986).
[MT77] MUTH, F.; THARP, A.:
"Correcting Human Error in Alphanumeric Terminal Input". Information Processing & Management, Vol. 13, 329/337, (1977).
[NH81] NIEVERGELT, J.; HINTERBERGER,
H.; SEVCIK, K.C.: "The Grid File: An Adaptable, Symmetric Multi-Key File
Structure". Eidgenössische Technische
Hochschuke, Zurich, Institut
fur Informatik, 1/47, (1981).
[NK82] NEVALAINEN, O.; KATAJAINEN, J.:
"Experiments with a Closest Point Algorithm in Hamming Space". Angewandte Informatik, 5,
277/282, (1982).
[OL82] OVERMANNS, M.H.; LEEUWEN J.V.:
"Dynamic Multi-Dimensional Data Structures Based on Quad and K-D
Trees". Acta Informatica, 267/285, (1982).
[OM87] OOI, B.C.; MCDONNELL, K.J.;
SACKS-DAVIS, R.: "Spatial KD-Tree: An Indexing Mechanism for Spatial
Database". Proceedings of COMPSAC-87, The
Eleventh Annual International Computer Software and Applications Conference,
433/438, (1987).
[OS81] OUKSEL, M.; SCHEUERMANN, P.:
"Multidimensional B-Trees: Analysis of Dynamic Behavior". Bit, 21, 401/418, (1981).
[OS83a] OUKSEL, M.; SCHEUERMANN, P.:
"Storage Mappings for Multidimensional Linear Dynamic Hashing". ACM, 90/105, (1983).
[OS83b] OHSAWA, Y.; SAKAUCHI, M.:
"The BD-Tree. A New N-Dimensional Data Structure with
Highly Efficient Dynamic Characteristics". IFIP
Conf. Information Processing, Paris, 539/544, (1983).
[OT85] OTOO, E.J.: "A
Multidimensional Digital Hashing Scheme for Files With
Composite Keys". ACM, 214/229, (1985).
[RE85] REGNIER, M.: "Analysis of
Grid File Algorithms". INRIA, Report 369, 1/24, Marzo
(1985).
[RI85] RAO, S.V.N.; IYENGAR, S.S.;
MADHAVAN, C.E.V.: "A Comparative Study of Multiple Attribute Tree and
Inverted File Structures for Large Bibliographic Files". Information Processing & Management, Vol. 21, 5, 433/442,
(1985).
[RO79] ROBERTS, C.S.:
"Partial-Match Retrieval Via the Method of
Superimposed Codes". Proceedings of the IEEE, Vol. 67,
12, 1624/1642, (1979).
[RO81] ROBINSON, J.T.: "The K-D-B
Tree: A Search Structure for Large Multidimensional Dynamic Indexes". Departament of
Computer Science, Carnegie-Mellow Universiy,
Pittsburg, Pennsylvania 15213, 1/21, (1981).
[RS84] RAMAMOHANARAO, K.; SACKS-DAVIS,
R.: "Recursive Linear Hashing". ACM Trans. Database
Syst., Vol. 9, 3, 369/391, (1984).
[RS85] RAMAMOHANARAO, K.; SACKS-DAVIS,
R.: "Partial-Match Retrieval Using Recursive Linear Hashing". Bit, 25, 477/484, (1985).
[SA80] SAMET, H.: "Deletion in Two-Dimensional
Quad Trees". Communications of the
ACM, Vol. 23, 12, 703/710, Diciembre (1980).
[SC86] SANTANA, O.; CABRERA, J.; DIAZ,
M.; MAYOR, O.: "Análisis experimental de los esquemas de inserción del
árbol-B". AEIA, Revista de Informática y Automática, 20 pag., Madrid, (1986).
[SD87] SANTANA, O.; DIAZ, M.; MAYOR,
O.; GONZALEZ, J.: "Búsqueda de los m-vecinos más próximos en el
árbol-BD". Actas de la XIII Conferencia Latinoamericana de Informática,
Bogotá, Colombia, Vol.II, 1106/1121, Noviembre,
(1987).
[SD88] SANTANA, O.; DIAZ, M.;
HERNANDEZ, Z.; DEL PINO, J.C.: "El árbol multidimensional equilibrado en
altura: Influencia de su comportamiento dinámico en las recuperaciones: exacta,
en rango y de los vecinos más próximos". Actas de la XIV Conferencia
Latinoamericana de Informática, Buenos Aires, Argentina, Vol.I,
33/46, Septiembre, (1988).
[SD90] SANTANA, O.; DIAZ, M.;
RODRIGUEZ, G.; RIVERO, P.: "Arbol cuaternario:
Búsqueda de los m-vecinos más próximos. Report
interno Departamento de Informática y Sistemas, Universidad de Las Palmas de
G.C., 1/27, Enero, (1990).
[SH76]
SHNEIDERMAN, B.: "Reduced Combined Indexes for Efficient Multiple
Attribute Retrieval". Inform. Systems, Vol. 2, 149/154,
(1976).
[SJ86] SHARMA, K.D.; JAIN, R.:
"Choosing an Optimal Sequence of Discriminators". Inf. Systems,
Vol. 11, 4, 337/342, (1986).
[SM87a] SANTANA, O.; MAYOR, O.; DIAZ,
M.; LOPEZ, G.: "Comportamiento del árbol-BD en las fases creciente,
decreciente y estacionaria". Actas de la XIII Conferencia Latinoamericana
de Informática, Bogotá, Colombia, Vol. II, 1093/1105, Noviembre, (1987).
[SM87b] SANTANA, O.; MAYOR, O.; DIAZ,
M.; REINA, S.: "Arboles quintarios: estudio
experimental para interrogaciones exactas, parciales, en rango y en rango
parcial". Actas de la XIII Conferencia Latinoamericana de Informática,
Bogotá, Colombia, Vol. II, 1148/1168, Noviembre,
(1987).
[SO82] SCHEUERMANN, P.; OUKSEL, M.:
"Multidimensional B-Trees for Associative Searching in Database
Systems". Inform. Systems, Vol. 7, 2, 123/137, (1982).
[SR83] SACKS-DAVIS, R.; RAMAMOHANARAO,
K.: "A Two Level Superimposed Coding Scheme for Partial Match
Retrieval". Inform Systems, Vol. 8, 4, 273/280, (1983).
[SR85] SHARMA, K.D.; RANI, R.:
"Choosing Optimal Branching Factors for K-D-B Trees". Inform. Systems, Vol. 10, 1, 127/134, (1985).
[SR89] SANTANA, O.; RODRIGUEZ, G.;
DIAZ, M.; PLACIDO, A.:"The Infinite Distance in the Determination of the
Nearest Euclidean M-Neighbours in the K-D-B
Tree". IEEE Proceedings of the International Workshop on Tools for
Artificial Intelligence "Achitectures, Languages
& Algorithms", Fairfax, Virginia, USA, 146/152, Octubre,
(1989).
[ST72] STANFEL, L.E.: "Practical
Aspects of Doubly Chained Trees for Retrieval". Journal
of the Association for Computing Machinery, Vol. 19, 3, 425/436, (1972).
[ST76] STANFEL, L.E.: "Optimal
Tree Lists for Information Storage and Retrieval". Inform. Systems, Vol. 2, 65/70, (1976).
[SU63] SUSSENGUTH, E.H. Jr.: "Use
of Tree Structures for Processing Files". Comm. of the
ACM, Vol. 6, 5, 272/279, (1963).
[TA81] TAMMINEN, M.: "The
Extendible Cell Method for Closest Point Problems". Bit,
22, 27/41, (1982).
[TH81] TROPF, H.; HERZOG, H.:
"Multidimensional Range Search in Dynamically Balanced Trees". Angewandte Informatik, 2, 71/77,
(1981).
[VA84] VAISHNAVI, V.K.:
"Multidimensional Height-Balanced Trees". IEEE
Transactions on Computers, Vol. c-33, 4, 334/343, (1984).
[VR79] VOSE, M.R.; RICHARDSON, J.S.:
"An Approach to Inverted Index Maintenance". The
Computer Bulletin, 256/263, (1979).
[WI84] WILLETT, P.: "A Nearest Neighbour Search Algorithm for Bibliographic Retrieval from
Multilist Files". Information
Technology, Vol. 3, 2, 78/83, (1984).
[WI87] WILLARD, D.E.: "Multidimensional
Search Trees that Provide New Types of Memory Reductions". J. Assoc. Comput. Mach., Vol. 34, 4, 846/858,
(1987).
[YA77] YANG, C.-S.: "Avoiding
Redundant Record Accesses in Unsorted Multilist File
Organizations". Inform. Systems, Vol. 2, 155/158, Pergamon Press, (1977).
[BK ] BANKS, D.; KRONACKER, M. STONEBRAKER, M.:
"High-Concurrency Locking in R-Trees". Computer Science Div. Dept. of
EECS, University of California, Berkeley, 1/15.
[CI94] CIACCIA, P.: "Parallel Independent
Grid Files Based on a Dynamic Declustering Method
Using Multiple Error Correcting Codes". Technical
Report, Laboratory for Computer Science, University of Bologna, 1/26 (1994).
[CV95] CIACCIA, P.; VERONSI, A.: "Dynamic Declustering Methods for Parallel Grid Files". Technical Report UBLCS-95-17, Departament
of Computer Science, University of Bologna, 1/19 (1995).
[FJ ] FALOUTSOS,
C.; JAGALISH, H. V.; MANOLOPOULOS, Y.: "Analysis of the n-dimensional quadtree descomposition for
arbitrary hyper-rectangles". Institute for System Research, University of
Maryland, College Park, 1/20.
[FL ] FALOUTSOS,
C.; LIN, D.: "FastMap: A Fast Algorithm for
Indexing, Data-Mining and Visualization of Traditional and Multimedia
Datasets". Institute for System Research, University of Maryland, College
Park, 1/16.
[GR96] GOLDSTEIN, J.; RAMAKRISHNAN, R.; SHAFT,
U.; YU, J.-B.: "Using Constrains to Query R*-Trees". Tech.
Report, Departament of Computer Science, Univesity of Wisconsin, Madison, 1/34, (1996).
[JS ] JAIN, V.;
SHNEIDERMAN, B.: "Data Structures for Dinamic
Queries: An Analytical and Experimental Evaluation". Institute for System
Research, University of Maryland, 1/24.
[KS ] KORN, F.;
SIDIROPOULOS, N.; FALOUTSOS, C.; SIEGEL, E.; PROTOPAPAS, Z.: "Fast Nearest
Neighbor Search in Medical Image Databases". Departament
of Computer Science, University of Maryland, College Park, 1/26.
[NI94] NICKERSON, B. G.: "Skip List Data
Structures for Multidimensional Data". Tech. Report, University of Maryland,
Institute for Advanced Computer Studies, 1/39, (1994).
[MA90] MOON, B.; ACHARYA, A.; SALTZ, J.:
"Study of Scalable Declustering Algorithms for
Parallel Grid Files". Institute for Advanced Computer Studies, Departament of Computer Science, University of Maryland,
College Park, 1/14, (1990).
[PU90] PUGH, W.: "Skip List Cookbook".
Institute for Advanced Computer Studies, Departament
of Computer Science, University of Maryland, College Park, 1/14, (1990).
[PU90] PUGH, W.: "Concurrent Maintenance of
Skip List". Institute for Advanced Computer Studies, Departament
of Computer Science, University of Maryland, College Park, 1/13, (1990).