A. Juozapavicius: "Search and Retrieval of Multidimensional Data"

Catalog description:

This course (project) has a goal to give an experience for students how to design and implement search engines, which are important issues in diverse applications like DBMS, computer graphics, computational geometry, VLSI design, GIS, and others. It will cover the design of efficient indices by evaluating and testing various representations of multidimensional data in computer memory, search operations, retrieval of data. Students may choose application data corresponding to their interests.

Current texts:

Mikhail J. Atallah (editor). Algorithms and Theory of Computation Handbook, CRC Press LLC, London, New York, 1999

Goals:

The course (project) is intended as an introduction and survey of the field of complex data structures and algorithms. The emphasis will be on fundamental techniques of representation of multidimensional data which underlie many applications. The experience in design and implementation of efficient indices for search and retrieval of data operations will be gained (this leads to the construction of search engines).

Content:

• Models of computer memory, access methods and fundamental data structures, the nature and physics of multidimensional data;
• point data, point queries, range queries of point data, logical combinations point and range queries;
• bucketing methods, space decomposition methods;
• region data, boundary-based representation, interior-based representation, space-ordering methods (especially for the 2-D and 3-D spaces);
• rectangle data;
• line data and boundaries of regions;
• analysis of the design and implementation issues.

Typical requirements:

Basic courses in data structures and algorithms, logic and programming, discrete mathematics are necessary

Helpful background:

Programming in C++ or JAVA are desirable