Multimedia Databases

here is my seminar report, images are missing as i used latex2html for it.
here is the link
http://www.cse.iitb.ac.in/~ajitb/seminar/

Now after defining these data structure our database is ready to answer fundamental queries like:

• Whole Match Queries: Given a collection of N objects O1,.., On and aquery object Q find data objects that are within distance delta from Q
• Sub-pattern Match: Given a collection of N objects O1,.., On and a query(sub-) object Q and a tolerance delta identify the parts of the data objects that match the query Q.
• K- Nearest Neighbor queries: Given a collection of N objects O1,.., On and a query object Q find the K most similar data objects to Q.
• All pairs queries (or ”spatial joins”): Given a collection of N objects O1 ,.., On find all objects that are within distance delta from each other.
  

for solving such queries we first need to find a distance function between two objects and find one or more numerical feature-extraction functions (to provide a quick test). Then Use a SAM (e.g., R-tree) to store and retrieve k-d feature vectors. here is an example of queries in context to computer games which uses these data structures :

• Visibility - What can I see?
  
• Ray intersections - What did the player just shoot?
• Collision detection - Did the player just hit a wall?
• Proximity queries - Where is the nearest power-up?
  

The main purpose is to is to support efficient spatial selection, for example range queries or nearest neighbour queries of spatial objects. Without a spatial index,every object in database need to be checked whether it meets selection criterion,i.e complete linear scan of relational database.
Clustering is needed to group those objects which are often requested together. Otherwise, many different disk pages will have to be fetched, resulting in slow response. For spatial selecting the clustering implies storing objects which are close together in reality also close together in the computer memory (instead of scattered over the whole memory).
In traditional database systems sorting (or ordering) the data is the basis for efficient searching. Higher dimensional data can not be sorted in an obvious manner, as it is possible for text strings, numbers, or dates (one-dimensional data). Basically, computer memory is one-dimensional. However, spatial data is 2D, 3D (or even higher) and must be organized somehow in the memory. An intuitive solution to organize the data is using a regular grid just as on a paper map. Each grid cell has a unique name; e.g. ’A3’, ’C6’, or ’D5’. The cells are stored in some order in the memory and can each contain a (fixed) number of object references. In a grid
cell, a reference is stored to an object whenever the object (partially) overlaps the cell. However, this will not be very efficient due to the irregular data distribution of spatial data: many cells will be empty, e.g. in the ocean, while many other cells will be overfull, e.g. in the city center. Therefore, more advanced techniques have been developed.

Let’s say we divide the picture area into 4 sections. Those 4 sections are then further divided into 4 subsections. We continue this process, repeatedly dividing a square region by 4. We must impose a limit to the levels of division otherwise we could go on dividing the picture forever. Generally, this limit is imposed due to storage considerations or to limit processing time or due to the resolution of the output device. A pixel is the smallest subsection of the quad tree.
To summarize, a square or quadrant in the picture is either :

1. entirely one color
2. composed of 4 smaller sub-squares

To represent a picture using a quad tree, each leaf must represent a uniform area of the picture. If the picture is black and white, we only need one bit to represent the colour in each leaf; for example, 0 could mean black and 1 could mean white.

Now consider the following image :
The definition of a picture is a two-dimensional array, where the elements of the array are colored points .

Given Image in pixel form In Quad tree-form


Now when this image is represneted as quad tree it will look like :