Abstract Structures

1. Abstract Structure

ID: 4850e361-e569-4b8e-a0e3-cedcc7e4b3a3
CREATED: <2025-02-28 Fri 18:19>

[2025-02-28 Fri 18:19] – Abstract structure - Wikipedia

2. Graph

ID: e2fd1fd6-2393-45a2-a073-0c44bfcfc2a0
CREATED: <2025-02-28 Fri 19:00>

[2025-02-28 Fri 19:00] – Graph (discrete mathematics) - Wikipedia [2025-02-28 Fri 19:00] – Graph theory - Wikipedia

2.1. Vertex

ID: e70dcd77-790b-4588-8abc-71b2f30c6a86
CREATED: <2025-02-28 Fri 19:15>

[2025-02-28 Fri 19:15] – Vertex (graph theory) - Wikipedia

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>

[2025-02-28 Fri 19:18] – Linked list - Wikipedia

4. Tuple

ID: 2616620b-782c-4c1f-97f9-e8f2d4fb8a38
CREATED: <2025-02-28 Fri 19:19>

[2025-02-28 Fri 19:19] – Tuple - Wikipedia

5. Curve

ID: 51e7d9ad-28a2-4284-94a1-18a642d0cf3d
CREATED: <2025-03-03 Mon 16:59>

[2025-03-03 Mon 16:59] – Algebraic curve - Wikipedia

5.1. Elliptic Curve

ID: b4579e67-0855-44e1-971d-1a727694af17
CREATED: <2025-03-03 Mon 16:59>

[2025-03-03 Mon 17:00] – Elliptic curve - Wikipedia [2025-03-03 Mon 17:01] << ECC

5.2. Hilbert Curve

ID: 67a3835e-7b81-4a16-9a79-c0673b4833f2
CREATED: <2025-05-07 Wed 16:51>

[2025-05-07 Wed 16:52] – 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>

[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>

[2025-03-03 Mon 20:50] – k-d tree - Wikipedia

6.2. LSM Tree

ID: 03324c5d-0caa-493c-993a-175cb3c9548e
CREATED: <2025-04-15 Tue 15:02>

[2025-04-15 Tue 15:02] – wiki [2025-04-15 Tue 15:04] -> RocksDB [2025-04-15 Tue 15:05] -> B+ Tree

6.3. B Tree

ID: 6dcb49d0-45e6-4c81-8299-d03ccdaf1633
CREATED: <2025-04-14 Mon 19:10>

[2025-04-14 Mon 19:10] – wiki [2025-05-07 Wed 17:17] <- R Tree

A self-balancing tree that maintains sorted data and allows search, seek, insert, and deletes in log n time.

While working at Boeing Research Labs, Rudolf Bayer and Edward M. McCreight invented B-trees to efficiently manage index pages for large random-access files. The basic assumption was that indices would be so voluminous that only small chunks of the tree could fit in main memory. Bayer and McCreight's paper Organization and maintenance of large ordered indices was first circulated in July 1970 and later published in Acta Informatica.

6.3.1. B+ Tree

ID: 4240d8d8-a646-4372-8bb5-37d029b325c2
CREATED: <2025-04-14 Mon 19:10>

[2025-04-14 Mon 19:11] – wiki [2025-04-15 Tue 15:05] <- LSM Tree [2025-05-07 Wed 17:15] <- Hilbert R-Tree

6.4. R Tree

ID: 0e58efd5-14fe-4562-b09f-a92519084ef9
CREATED: <2025-05-07 Wed 17:13>

[2025-05-07 Wed 17:15] – wiki [2025-05-07 Wed 17:17] -> B Tree

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 rectangle in 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>

[2025-05-07 Wed 17:13] – wiki [2025-05-07 Wed 17:15] -> B+ Tree

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
  • 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>

[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>

[2025-05-07 Wed 18:08] – 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>

[2025-05-07 Wed 17:08] – wiki