Abstract Structures
1. Abstract Structure
ID: 4850e361-e569-4b8e-a0e3-cedcc7e4b3a3 CREATED: <2025-02-28 Fri 18:19>
2. Graph
ID: e2fd1fd6-2393-45a2-a073-0c44bfcfc2a0 CREATED: <2025-02-28 Fri 19:00>
– Graph (discrete mathematics) - Wikipedia – Graph theory - Wikipedia
2.1. Vertex
ID: e70dcd77-790b-4588-8abc-71b2f30c6a86 CREATED: <2025-02-28 Fri 19:15>
2.2. Edge
ID: 2c184ae0-2523-4f44-9711-4e50e1c93c55 CREATED: <2025-02-28 Fri 19:15>
A link between vertices, often represented as a line optionally with arrows as allowed by the applicable graph model (directed, undirected, acyclic, etc)
3. Linked List
ID: 8805be63-567a-472d-a70c-6155ba2f3d02 CREATED: <2025-02-28 Fri 19:18>
4. Tuple
ID: 2616620b-782c-4c1f-97f9-e8f2d4fb8a38 CREATED: <2025-02-28 Fri 19:19>
5. Curve
ID: 51e7d9ad-28a2-4284-94a1-18a642d0cf3d CREATED: <2025-03-03 Mon 16:59>
5.1. Elliptic Curve
ID: b4579e67-0855-44e1-971d-1a727694af17 CREATED: <2025-03-03 Mon 16:59>
5.2. Hilbert Curve
ID: 67a3835e-7b81-4a16-9a79-c0673b4833f2 CREATED: <2025-05-07 Wed 16:51>
– wiki
A popular type of space-filling curve. Can be found in recursive and non-recursive variants. Used for mapping between 1d and 2d space while preserving locality fairly well.
adishavit/hilbert: Doug Moore's Fast Hilbert Curve Generation, Sorting, and Range Queries Efficient 3D Hilbert Curve Generation and Inverse (C99) · GitHub also in CL: cl-ascii-art/hilbert-space-filling-curve.lisp
6. Tree
ID: 9fffae3b-e504-46a3-8f30-9f47a00ec5ba CREATED: <2025-04-14 Mon 19:09>
– wiki
6.1. k-d tree
ID: 91c3a4e5-b6c4-49e7-8b6e-eac6e88e0b67 CREATED: <2025-03-03 Mon 20:50>
6.2. LSM Tree
6.3. B Tree
ID: 6dcb49d0-45e6-4c81-8299-d03ccdaf1633 CREATED: <2025-04-14 Mon 19:10>
6.3.1. B+ Tree
ID: 4240d8d8-a646-4372-8bb5-37d029b325c2 CREATED: <2025-04-14 Mon 19:10>
– wiki <- LSM Tree <- Hilbert R-Tree
6.4. R Tree
ID: 0e58efd5-14fe-4562-b09f-a92519084ef9 CREATED: <2025-05-07 Wed 17:13>
Searching on one number is a solved problem; searching on two or more, and asking for locations that are nearby in both x and y directions, requires craftier algorithms.
- used for spatial access methods
- indexing multi-dimensional info such as geocoordinates, polygons, etc.
- key insight: group nearby objects and represent them with their
minimum bounding rectanglein the next higher level of the tree - like B-Tree, is a balanced search tree
- Minimum bounding rectangle (MBR)
6.4.1. Hilbert R-Tree
ID: 9da67ff9-b19f-47a9-adee-59b660672adc CREATED: <2025-05-07 Wed 17:13>
Can be thought of as an extension to B+ Trees for multidemnsional objects.
- performance depends on the quality of the algorithm that clusters
the data rectangles on a node.
- Hilbert curve used for linear ordering on the data rectangles
- two types: static and dynamic
- both use hilbert curve for better ordering
- optimize for minimizing the area of the resulting MBRs
- both use hilbert curve for better ordering
- Packed Hilbert R-trees suitable for static DBs - very rare or no updates at all
- Dynamic Hilbert R-tree suitable for dynamic database with real-time
query/update/insertion/deletion
- every node has well-defined set of sibling nodes via proposed ordering on the R-tree nodes
- sorts rectangles according to the hilbert value (lenght of the hilbert curve from the origin to a point) of the center (MBR)
- given the ordering, and thus the set of siblings, deferred splitting can be used
- by adjusting the split policy, can achieve a degree of space utilization as high as desired - unlike other R-tree variants.
6.4.2. Z-order Curve
ID: 61a74ac4-47ff-4f67-afea-e11bb4ebd809 CREATED: <2025-05-07 Wed 17:37>
– wiki
6.4.3. X Tree
ID: 58645bde-a83e-468b-bf9f-1984eb517ba2 CREATED: <2025-05-07 Wed 18:07>
– the X-tree: An Index Structure for High-Dimensional Data
rodp63/Xtree: X-tree data structure in c++ for high dimensional data indexing
6.5. Radix Tree
ID: 1c3da977-929d-418f-9d3b-e59ac009c987 CREATED: <2025-05-07 Wed 17:07>
– wiki