- Basic idea- Divide space into cells by a grid
- Example: latitude-longitude, ESRI Arc/SDE
- Store data in each cell in distinct disk sector
- Efficient for find, insert, nearest neighbor
- But may have wastage of disk storage space
- non-uniform data distribution over space
- Refinement of basic idea into Grid Files
- Use non-uniform grids
- Linear scale store row and column boundaries
- Allow sharing of disk sectors across grid cell
- Grid File component
- Linear scale - row/column boundaries
- Grid directory: cell --> disk sector address
- data sectors on disk
- Operation implementation
- Scales and grid directory in main memory
- Steps for find, nearest neighbor
- Search linear scales
- Identify selected grid directory cells
- Retrieve selected disk sectors
- Performance overview
- Efficient in terms of I/O costs
- Needs large main memory for grid directory
| 
|
|
Última modificación: Friday, 18 de November de 2005, 18:24