• ES Español
• EN English

5.34. Advanced Data Structures (Mandatory)

5.34.1. Justification ↑ Back to top

Algorithms and data structures are a fundamental part of Computer Science that allow us to organize information efficiently. For any professional in the field, a solid foundation in this area is crucial. This course focuses on advanced structures such as Multidimensional Access Methods, Spatio-Temporal Access Methods, and Metric Access Methods, which are essential for high-performance applications in search engines, geographic information systems (GIS), and big data processing.

5.34.2. Generales Goals ↑ Back to top

1. Understand, design, and implement innovative data structures for multidimensional data.
2. Apply similarity search techniques and metric indexing to complex data types.
3. Analyze the "Curse of Dimensionality" and its impact on search efficiency.
4. Research and present contemporary indexing methods for Big Data in English.

5.34.3. Contribution to Outcomes ↑ Back to top

AG-C08) Problem Analysis: Identifies, formulates, and analyzes complex computing problems. (Usage)

AG-C12) Applies computer science theory and software development fundamentals to produce computer-based solutions. (Usage)

5.34.4. Content ↑ Back to top

5.34.4.1. Object-Oriented Programming: Encapsulation, Subtyping, and Reflection (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cuadros-Vargas et al., 2004; Knuth, 1997b; Gamma et al., 1994b; Vandevoorde et al., 2018)

Topics

1. Static and dynamic implementation techniques.
2. Data abstraction and encapsulation.
3. Abstract Data Types (ADT).
4. Compile-time vs. Runtime polymorphism.
5. Generic data structures and C++ Templates.
6. Reusable components and design patterns for data structures.

Learning Outcomes

1. Evaluate the impact of static and dynamic techniques on data structure design [Assessment].
2. Implement generic and reusable data structures using advanced programming paradigms [Usage].
3. Analyze performance trade-offs between different implementation strategies [Assessment].

5.34.4.2. Multidimensional Access Methods (Part I) (8 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Gaede and Günther, 1998; Samet, 2006)

Topics

1. Introduction to multidimensional data.
2. Vector space representation.
3. The Curse of Dimensionality: theoretical foundations.
4. Impact of high dimensionality on traditional indexing.
5. Real-world applications in search engines and pattern recognition.

Learning Outcomes

1. Explain the significance of multidimensional data representation [Familiarity].
2. Analyze the complexity and performance degradation in high-dimensional spaces [Usage].
3. Discuss real-world scenarios where dimensionality impact is critical [Usage].

5.34.4.3. Multidimensional Access Methods (Part II) (20 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Samet, 2006)

Topics

1. Spatial data structures: Quadtree and Octree.
2. Point Access Methods: Kd-Tree.
3. Region Access Methods: R-Tree (Guttman), R+ tree, R* tree.
4. Variations of R-trees and their relation to paging and block size.
5. Advanced structures: X-tree and SS-tree.

Learning Outcomes

1. Implement spatial data structures for high-volume data indexing [Usage].
2. Evaluate the limitations of tree-based spatial structures in specific domains [Assessment].
3. Implement range search and Nearest Neighbor (k-NN) strategies [Usage].

5.34.4.4. Metric Access Methods (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Samet, 2006; Zezula et al., 2007)

Topics

1. Metric Spaces: definitions and properties.
2. Similarity search vs. Exact search.
3. Vantage Point Tree (VP-Tree).
4. Slim-Tree and M-Tree.
5. Pivot-based indexing.

Learning Outcomes

1. Model similarity search problems using metric space properties [Usage].
2. Compare metric access methods against multidimensional methods for non-vector data [Assessment].

5.34.4.5. Technical and Professional Communication (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Navarro, 2016; Traina Jr et al., 2000)

Topics

1. Seminar on recent research papers (SIGMOD, VLDB, ICDE).
2. Indexing for Big Data and streaming data.
3. Compact data structures and succinct representations.
4. Future trends in similarity search.

Learning Outcomes

1. Research new methods for indexing large volumes of complex data [Usage].
2. Present and lead technical discussions in English on state-of-the-art methods [Assessment].
3. Identify potential thesis topics within the advanced data structures domain [Familiarity].

5.34.5. Bibliography ↑ Back to top

Cuadros-Vargas, E., Romero, R. A. F., Mock, M., and Brisaboa, N. (2004). Implementing data structures: An incremental approach. Available at: http://socios.spc.org.pe/ecuadros/cursos/pdfs/.

Knuth, D. E. (1997b). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley Professional, 3rd edition.

Gamma, E., Helm, R., Johnson, R., and Vlissides, J. M. (1994b). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional.

Vandevoorde, D., Josuttis, N. M., and Gregor, D. (2018). C++ Templates: The Complete Guide. Addison-Wesley Professional.

Gaede, V. and Günther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2):170–231.

Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Elsevier/Morgan Kaufmann.

Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2007). Similarity Search: The Metric Space Approach. Springer.thebibliography

Navarro, G. (2016). Compact Data Structures. Cambridge University Press.

Traina Jr, C., Traina, A. J. M., Seeger, B., and Faloutsos, C. (2000). Slim-trees: High performance metric trees minimizing overlap between nodes. In Advances in Database Technology - EDBT 2000. Springer.