Types of Queries:

Now after defining these data structure our database is ready to answer fundamental queries [4] like

• Whole Match Queries: Given a collection of N objects $O_{1}$,.., $O_{n}$ and a query object Q find data objects that are within distance $\epsilon$ from Q
• Sub-pattern Match: Given a collection of N objects $O_{1}$,.., $O_{n}$ and a query (sub-) object Q and a tolerance $\epsilon$ identify the parts of the data objects that match the query Q
• K- Nearest Neighbor queries: Given a collection of N objects $O_{1}$,.., $O_{n}$ 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 $O_{1}$ ,.., $O_{n}$ find all objects that are within distance $\epsilon$ 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?