Rectangle Data Representation
Multivariate Cross-sectional Data (ไม่ใช่ Time-series) = Rectangular Data: Column = Variable/Feature, Row = Case/Record
3 วิธีการแทน Rectangle Data
1. Point-based Representation (Map เป็น Higher-D Points)
Map Rectangle → 4D Point ใช้ Point-based Structures: Grid File, PR Quadtree, Point Quadtree, k-d Tree
Mapping Techniques: (x₁,y₁,x₂,y₂) ของมุมตรงข้าม, หรือ (x,y,width,height) ของมุมหนึ่ง
ข้อเสีย: ไม่ได้ประโยชน์จาก Locality ของ Rectangle Data → Storage/Spatial Operations ไม่ Efficient
2. Line-based Representation (แทนด้วย Lines ที่ประกอบ)
Rectangle = 4 Line Segments ใช้ Line-based Structures: PM Quadtree, PMR Quadtree
ข้อเสีย: Spatial Operation บน Line Segments อาจไม่ผ่านเงื่อนไข แม้ Rectangle ที่ประกอบจะผ่าน
3. Area-based Representation (แทนด้วย Area ที่ครอบครอง) - แนะนำ
จัดกลุ่ม Rectangles ด้วย Minimum Bounding Boxes แบบ Hierarchical
- MX-CIF Quadtrees: Space-based Quadtree Partitioning Rectangle → Smallest Enclosing Quadtree Block
- R-Trees: Partition เป็น Hierarchically Nested Minimum Bounding Boxes
ข้อเสีย R-Trees: ไม่ใช้ Locality ของ Data
สรุปการเลือก
| วิธี | โครงสร้างตัวอย่าง | ข้อดี | ข้อเสีย |
|---|---|---|---|
| Point-based | Grid File, k-d Tree, Point Quadtree | ใช้โครงสร้าง Point ที่มีอยู่ได้ | ไม่ Exploit Rectangle Locality |
| Line-based | PM Quadtree, PMR Quadtree | เหมาะ Line-based Queries | Line Operation ≠ Rectangle Operation |
| Area-based | MX-CIF Quadtree, R-Tree | Natural สำหรับ Rectangle, รองรับ Spatial Queries ดี | R-Tree: ไม่ใช้ Locality (แต่ Practical ดี) |
