Pith. sign in

REVIEW 2 major objections 4 minor 103 references

Aster: Enhancing LSM-structures for Scalable Graph Database

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A graph storage engine can get fast updates and fast lookups at once by storing each vertex as a pivot entry plus small delta entries and choosing per update based on degree.

desk verdict Hybrid LSM graph storage design that is genuinely new and mostly well-validated, but the abstract overclaims and the skewed-workload robustness proof is deferred to a tech report. read the letter →

arxiv 2501.06570 v1 pith:7G6GK7MP submitted 2025-01-11 cs.DB

Dingheng Mo , Junfeng Liu , Fan Wang , Siqiang Luo This is my paper · ORCID
classification cs.DB
keywords LSM-treegraphdatabasedisk-residentstorageadaptiveupdatesdegreesketchElias-FanoencodinghybridlayoutGremlin
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Disk-resident graph databases have historically forced a choice: store each edge as its own entry and updates are cheap but neighbor lookups are slow, or store each vertex's adjacency list as one entry and lookups are fast but updates require read-modify-write. This paper tries to remove that choice. It proposes Poly-LSM, an LSM-tree-based storage engine in which each vertex has one pivot entry holding the bulk of its adjacency list plus small delta entries holding recent edge changes, and a per-operation adaptive rule decides which kind of update to issue based on the vertex's degree and the workload's lookup/update ratio. On top of Poly-LSM the authors build Aster, a Gremlin-compatible graph database, and report that it outperforms all tested mainstream graph databases, with up to a 17x throughput improvement over the best baseline on the billion-edge Twitter graph. The interest is that, if the claims hold, a single disk-resident engine can serve mixed read/write workloads on very large evolving graphs without the usual read-write trade-off.

What carries the argument

The load-bearing mechanism is the hybrid pivot-delta entry layout inside a standard LSM-tree. Each vertex has exactly one pivot entry—a sorted adjacency list—plus zero or more delta entries, each holding a recent edge insertion or deletion; compaction folds deltas into the pivot as it pushes data down the levels. The adaptive decision is made by a cost model that compares the expected I/O cost of a delta update (write cost now plus extra reads later) with that of a pivot update (read-modify-write of the whole adjacency list now), yielding a degree threshold $d_t$: vertices with degree at or above $d_t$ use delta updates, lower-degree vertices use pivot updates. An 8-bit Morris-counter-based degree sketch estimates each vertex's degree in memory with bounded variance, and partitioned Elias-Fano encoding compresses the sorted neighbor lists to reduce space and I/O.

What would settle it

Run the same update/lookup workload on a power-law graph whose hub vertices receive most of the lookup traffic, compare measured I/O cost against the throughput predicted by the paper's uniform-workload cost model, and check whether the $O(\log m)$-competitiveness bound holds; if the actual cost of the threshold-chosen updates exceeds that of always-delta or always-pivot by more than the model allows, the uniformity assumption is violated.

Watch

Extended reading notes

Core claim

The paper's central claim is that Poly-LSM achieves update efficiency comparable to edge-based LSM-trees and lookup efficiency akin to vertex-based LSM-trees simultaneously. The device that makes this possible is a polymorphic key-value layout: each vertex is stored as one pivot entry (a sorted adjacency list) together with any number of delta entries (single-edge updates), and the LSM-tree's own compaction gradually merges delta entries into the pivot entry as data moves to deeper levels. Edge insertions and deletions can therefore start life as cheap delta writes, while lookups still terminate at the consolidated pivot entry, so read cost is bounded by the number of LSM levels rather than by vertex degree. The paper further claims that the delta-versus-pivot decision can be made optimally per operation by thresholding on a vertex-degree estimate supplied by an 8-bit sketch, and that the resulting system, Aster, outperforms all baseline graph databases in its experiments, including a 17x throughput gain over the best-performing baseline on the billion-edge Twitter dataset.

Load-bearing premise

The adaptive threshold is computed from a cost model that assumes every vertex is queried about equally often; real graph workloads are typically skewed toward a few hub vertices, and the paper defers the proof that performance stays near-optimal under such skew to an external technical report.

Editorial extensions

If this is right

  • A single disk-resident graph database can serve mixed update/lookup workloads without forcing users to pick a write-optimized or read-optimized storage layout.
  • Because delta entries are merged into pivot entries during normal LSM compaction, the hybrid layout needs no new storage primitive beyond the Merge Operator APIs already present in standard LSM engines.
  • Neighbor lookup cost is bounded by the number of LSM levels rather than the degree of the queried vertex, which is what lets performance degrade slowly as graphs grow to billion-edge scale.
  • The threshold rule is tunable: lookup-heavy or low-average-degree workloads push $d_t$ up (more pivot updates), update-heavy or high-average-degree workloads push it down (more delta updates).
  • Compressing adjacency lists with partitioned Elias-Fano encoding reduces the bytes read and written per entry, amplifying the benefit of the pivot layout for dense vertices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same pivot/delta idea could generalize beyond graphs: any LSM-backed key-value store holding large composite values could decide per key whether to write a small delta or rewrite the whole value, using a per-key size or hotness estimate instead of degree.
  • A testable extension is to relax the uniform-lookup assumption in the cost model—for example, replacing $P_u = 1/n$ with a Zipfian frequency model—and see whether the threshold and the 17x result survive skewed hub-centric workloads.
  • The 8-bit degree sketch has roughly 10% relative error, so vertices whose degree sits near $d_t$ may be assigned the 'wrong' update method; the paper argues the cost difference is small there, but measuring the cumulative effect on frequently updated hub vertices would settle that.
  • Because delta entries are timestamped in the MVCC design, the layout may extend naturally to temporal or versioned graphs, where each delta is a time-stamped edge and compaction must be careful not to collapse distinct versions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes Poly-LSM, an LSM-tree-based graph storage engine that stores graph data as polymorphic key-value entries, allowing both edge-based (delta) and vertex-based (pivot) updates. A cost model over LSM I/O is used to derive an adaptive degree threshold (Eq. 8) that selects delta versus pivot updates per vertex, and a compact Morris-counter degree sketch supports this decision in memory. The paper also describes partitioned Elias-Fano encoding for adjacency lists, and builds a full Gremlin-capable graph database, Aster, on top of RocksDB. The evaluation compares Aster with Neo4j, ArangoDB, OrientDB, SQLG, JanusGraph, and NebulaGraph across moderate, large, and billion-scale datasets, reporting up to 17x throughput improvement over the best baseline on the Twitter graph, plus an I/O cost model validation in Figure 8(C).

Significance. If the central claims hold, the paper makes a useful contribution: a single disk-resident graph storage engine that avoids the usual read/write trade-off of linked-list, relational, and single-layout LSM graph stores. The adaptive threshold is derived from input constants (I, B, T, L, theta_L, theta_U, d) rather than fitted to the experimental results, and Figure 8(C) provides an out-of-sample check of predicted versus actual I/O. The implementation of a complete Gremlin-capable database and the billion-scale Twitter evaluation are additional strengths. However, the manuscript's robustness claim for skewed workloads is not established in the paper itself, and the abstract's blanket performance claim is contradicted by the paper's own moderate-scale results.

major comments (2)
  1. [§3.3, Lemma 3.1 and Eq. (8)] The adaptive threshold in Eq. (8) is derived under the explicit uniform-workload assumption P_u = 1/n stated in Eq. (3). The only statement covering skewed workloads, Lemma 3.1, is asserted with the proof deferred to the unpublished technical report [1]. This is load-bearing for Design 1's claim of simultaneous update and lookup efficiency. Under a skewed lookup distribution, the prospective-read term in Eq. (1) should depend on the per-vertex lookup frequency f_u rather than the global average 1/n; a hot vertex with degree above d_t would then be systematically delta-updated even when its high lookup frequency makes a pivot update cheaper, and a cold vertex below d_t would be pivot-updated even when delta is cheaper. The paper should either include the proof of Lemma 3.1 or provide an experiment with a skewed lookup distribution (for example, Zipf over vertex IDs) comparing Poly-LSM against Delta-Poly, Pivot-Poly, and Vertex-LSM. In addition, the statement in §6.2 that Poly-LSM is "theoretically global optimal" is stronger than what Section 3.3 establishes, since exact optimality is only argued under the uniform-workload assumption.
  2. [Abstract and §6.2 (Figure 6, Figure 7)] The abstract claims that Aster "outperforms all baseline graph databases," and Section 6.2 states that "Aster outperforms all other databases on moderate and large-scale graphs." These statements are contradicted by the paper's own results: on DBLP with heavy lookups, Aster is reported to be slower than Neo4j, and Figure 7(D) states that Aster "slightly trails Neo4j on moderate-scale datasets" for the GetNeighbors operation. The claim should be qualified to large-scale and massive-scale datasets or to the specific workloads where it holds, and should not be stated as a blanket superiority claim.
minor comments (4)
  1. [§6.1] The text says "most entries in Pivot-Poly exist in the form of edge-based adjacency lists," but Pivot-Poly performs pivot updates, which create vertex-based adjacency-list entries; this appears to be a typo and should read "vertex-based adjacency lists" or "pivot entries."
  2. [§3.3, The Degree Sketch] The sentence "Poly-LSM's adaptive mechanism uses u's degree... based on the threshold outlined in Equation 6" refers to the wrong equation; the adaptive threshold is defined in Eq. (8), not Eq. (6).
  3. [§3.3, 1-leveling extension] The description that RocksDB's 1-leveling keeps "each buffer flush as a separate run in the first level and does not merge with existing data" is a simplification; in RocksDB's Leveled compaction, level 0 runs are eventually merged into level 1. The cost model extension may still be valid, but the wording should be more precise.
  4. [§3.4] The partitioned Elias-Fano encoding has tunable parameters (segment count and prefix length), but the paper does not state how these are chosen in the experiments or whether performance is sensitive to them; a brief note or sensitivity result would improve reproducibility.

Circularity Check

1 steps flagged · score 3.0 of 10

No fitted-input circularity found; the one self-citation issue is that Lemma 3.1's skewed-workload proof is deferred to the authors' own technical report.

  1. self citation load bearing [Section 3.3, 'Is the Adaptive Update Scheme Optimal?', footnote 4; echoed in Section 6.2]
    "In more complicated situations, when the workload is skewed over graph vertices, the cost of S is at most a log m factor of S*, as Lemma 3.1 indicates.4 ... 4The full proof of Lemma 3.1 is included in our technical report [1]."

    The threshold d_t is derived under the uniform-workload assumption P_u = 1/n (Equation 3), so the O(log m)-competitiveness for skewed workloads is not established by the paper's own derivation; the only support is the authors' unpublished technical report [1]. Section 6.2 then treats the adaptive choice as 'proven to be theoretically global optimal', importing this unverified lemma as if it were established. This makes the skewed-workload optimality claim rest on a self-citation rather than on an independent proof. The empirical benchmark results remain independent, so this is a partial self-citation issue rather than a fully circular derivation.

full rationale

The core derivation chain is not circular: the adaptive threshold d_t (Eq. 8) is a closed-form function of stated constants (I, B, T, L, theta_L, theta_U, d), not a fitted parameter, and Figure 8(C) compares model predictions against measured I/O, which is a genuine out-of-sample check. The central empirical claim that Aster outperforms external baseline systems is validated against Neo4j, ArangoDB, OrientDB, SQLG, JanusGraph, NebulaGraph, DuckDB, and Umbra, and the LSM-variant comparisons are built on the same RocksDB base. No 'prediction' reduces to its input by construction. The only circularity-adjacent item is Lemma 3.1: its O(log m)-competitiveness for skewed workloads is load-bearing for the 'theoretically global optimal' statement, but the proof is deferred to the authors' own technical report [1], so that theoretical guarantee is not independently supported. This raises the score slightly but does not undermine the paper's main independent experimental contribution.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central design relies on LSM-tree cost-model assumptions: uniform key distribution, fixed workload mix, negligible Bloom filter false positives, and an approximate 1-I/O cost for retrieving delta entries. These are standard modeling assumptions but not guaranteed in real skewed graph workloads. Lemma 3.1, which is supposed to cover skew, is unproven in the paper. No fitted free parameters are required for the core adaptive threshold; the Elias-Fano compression has an unspecified tunable parameter.

free parameters (2)
  • Elias-Fano partition segment count = unspecified
    Section 3.4 notes the compression rate can be tuned by adjusting the number of segments or prefix length, but the paper does not state the value used in experiments or whether it was tuned per dataset.
  • Degree sketch bits per vertex = 8 (4 exponent, 4 mantissa)
    Section 3.3 and 6.1 fix 8 bits per vertex; this caps the representable degree near 1,015,792 and forces vertices above that to always use delta updates. It is a design constant, not fitted to data, but it affects the adaptive decision.
assumptions (5)
  • domain assumption Uniform workload with fixed proportions and uniform key-value distribution
    Section 3.3 builds the cost model on this assumption; real graph workloads are typically skewed.
  • domain assumption Probability that a lookup targets vertex u is 1/n
    Equation 3 uses P_u = 1/n; query skew would invalidate the threshold derivation.
  • domain assumption Bloom filter false positives are negligible
    Section 3.3 assumes false positive I/Os are negligible at 10 bits per key; the paper notes the false positive rate is below 1%.
  • domain assumption Expected delta-entry retrieval cost is 1 I/O
    Section 3.3 approximates the cost of reading delta entries of a vertex during a lookup as 1 I/O, although the exact sum C_R in Equation 6 can exceed 1 (about 1.28 for Wikipedia, as computed in the paper).
  • ad hoc to paper Lemma 3.1 competitiveness bound
    The O(1)/O(log m) competitiveness of the adaptive scheme is stated but proved only in the authors' technical report [1], not in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Aster: Enhancing LSM-structures for Scalable Graph Database." pith.science (2026). https://pith.science/paper/7G6GK7MP

@misc{pith2026250106570,
  author       = {Pith},
  title        = {Pith review of: Aster: Enhancing LSM-structures for Scalable Graph Database},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7G6GK7MP}},
  note         = {Machine review of arXiv:2501.06570}
}
read the original abstract

There is a proliferation of applications requiring the management of large-scale, evolving graphs under workloads with intensive graph updates and lookups. Driven by this challenge, we introduce Poly-LSM, a high-performance key-value storage engine for graphs with the following novel techniques: (1) Poly-LSM is embedded with a new design of graph-oriented LSM-tree structure that features a hybrid storage model for concisely and effectively storing graph data. (2) Poly-LSM utilizes an adaptive mechanism to handle edge insertions and deletions on graphs with optimized I/O efficiency. (3) Poly-LSM exploits the skewness of graph data to encode the key-value entries. Building upon this foundation, we further implement Aster, a robust and versatile graph database that supports Gremlin query language facilitating various graph applications. In our experiments, we compared Aster against several mainstream real-world graph databases. The results demonstrate that Aster outperforms all baseline graph databases, especially on large-scale graphs. Notably, on the billion-scale Twitter graph dataset, Aster achieves up to 17x throughput improvement compared to the best-performing baseline graph system.

Figures

Figures reproduced from arXiv: 2501.06570 by the authors.

Figure 1
Figure 1. The left figure illustrates the sub-optimal trade-off between lookup and update in existing LSM-based [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Diagram of the LSM-tree structure. to effectively manage and navigate graph structures for diverse graph applications ranging from fundamental operations to sophisticated queries. Aster provides a graph query interface utilizing Gremlin [77], a powerful data-flow query language. Moreover, it is able to efficiently parse graph queries into fundamental operations within Poly-LSM which are subsequently assembled into a… view at source ↗
Figure 3
Figure 3. An overview of the Poly-LSM demonstrating the workflow of several basic operations including add new vertex, delta edge update, and pivot edge update. In this figure, Buf represents the memory buffer of the LSM-tree. Edge-based LSM-trees. Each graph edge corresponds to a key-value entry in the LSM-tree. A notable example of graph database systems employing this layout is NebulaGraph, which creates a tuple for each e… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The degree sketch allows Poly-LSM to index the degree of each vertex in memory with very few bits. 0 and 15. The update process of the degree sketch is shown in Algorithm 1. Let 𝐸𝑢 denote the exponent of vertex 𝑢 in the degree sketch, and 𝑀𝑢 denote its mantissa. Every …
Figure 5
Figure 5. Figure 5: The architecture of Aster. enables users to perform queries through Gremlin with Poly-LSM as the storage backend. We will also introduce our distinctive graph traversal optimization for Poly-LSM and implementations of some necessary functions in graph database systems,…
Figure 6
Figure 6. Figure 6: Aster demonstrates strong efficiency and scalability across various workloads and dominates all baselines on large-scale and massive-scale graph datasets. lookups and 90% updates) to read-heavy tasks (90% lookups and 10% updates), on various graph datasets from moderat…
Figure 7
Figure 7. Figure 7: Time required for processing graph structure update, traversal, and property queries. [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: (A) and (B) shows Poly-LSM exhibits strong robustness as the workload changes and outperforms other LSM-tree-based baselines. (C) indicates the cost model of Poly-LSM accurately predicts the I/O overhead. NebulaGraph time out while loading the massive-scale Twitter dat…
Figure 9
Figure 9. Figure 9: In-memory comparison with memory-centric systems. [PITH_FULL_IMAGE:figures/full_fig_p021_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

103 extracted references · 67 canonical work pages

  1. [1]

    Aster Technical Report

    -. Aster Technical Report. https://sites.google.com/view/aster-technical-report

  2. [2]

    ArangoDB

    2024. ArangoDB. https://www.arangodb.com/

    2024

  3. [3]

    Berkeley DB Java Edition Architecture

    2024. Berkeley DB Java Edition Architecture. https://www.oracle.com/technetwork/database/berkeleydb/learnmore/ bdb-je-architecture-whitepaper-366830.pdf

    2024

  4. [4]

    JanusGraph

    2024. JanusGraph. https://janusgraph.org/

    2024

  5. [5]

    2024. MySQL. https://www.mysql.com/

    2024

  6. [6]

    2024. Neo4j. https://neo4j.com/

    2024

  7. [7]

    OrientDB

    2024. OrientDB. https://github.com/orientechnologies/orientdb

    2024

  8. [8]

    Sparsity Technologies, Sparksee

    2024. Sparsity Technologies, Sparksee. http://www.sparsity-technologies.com/

    2024

Show all 103 references
  1. [9]

    2024. SQLG. http://www.sqlg.org/

    2024

  2. [10]

    Wail Y Alkowaileet, Sattam Alsubaiee, and Michael J Carey. 2019. An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version). arXiv preprint arXiv:1910.08185 (2019)

    2019 arXiv

  3. [11]

    Fatemeh Almodaresi, Jamshed Khan, Sergey Madaminov, Prashant Pandey, Michael Ferdman, Rob Johnson, and Rob Patro. 2021. An incrementally updatable and scalable system for large-scale sequence search using LSM trees. BioRxiv (2021), 2021–02

    2021

  4. [12]

    Apache. 2024. TinkerPop. https://tinkerpop.apache.org/. 6Note that CDLP requires tracking the number of labels for each vertex’s neighbors, which is not well-suited to the edge-centric co-processing model used in Mosaic and GridGraph, resulting in relatively slower performance...

    2024

  5. [13]

    Diego Arroyuelo, Benjamin Bustos, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, and Juan Reutter. 2024. Worst-Case-Optimal Similarity Joins on Graph Databases. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–26

    2024

  6. [14]

    Zhichao Cao, Siying Dong, Sagar Vemuri, and David HC Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In18th USENIX Conference on File and Storage Technologies (FAST 20) . 209–223

    2020

  7. [15]

    Javad Ghareh Chamani, Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili

  8. [16]

    Helen HW Chan, Chieh-Jan Mike Liang, Yongkun Li, Wenjia He, Patrick PC Lee, Lianjie Zhu, Yaozu Dong, Yinlong Xu, Yu Xu, Jin Jiang, et al. 2018. HashKV: Enabling Efficient Updates in KV Storage via Hashing. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 1007–1019

    2018

  9. [17]

    Hongzhi Chen, Changji Li, Chenguang Zheng, Chenghuan Huang, Juncheng Fang, James Cheng, and Jian Zhang. 2022. G-tran: a high performance distributed graph database with a decentralized architecture. Proceedings of the VLDB Endowment 15, 11 (2022), 2545–2558

    2022

  10. [18]

    Zehao Chen, Bingzhe Li, Xiaojun Cai, Zhiping Jia, Lei Ju, Zili Shao, and Zhaoyan Shen. 2023. ChainKV: A Semantics- Aware Key-Value Store for Ethereum System. Proceedings of the ACM on Management of Data 1, 4 (2023), 1–23

    2023

  11. [19]

    Source Code. 2024. WiredTiger. https://github.com/wiredtiger/wiredtiger

    2024

  12. [20]

    Miklós Csűrös. 2010. Approximate counting with a floating-point counter. InInternational Computing and Combinatorics Conference. Springer, 358–367

    2010

  13. [21]

    Pengjie Cui, Haotian Liu, Bo Tang, and Ye Yuan. 2024. CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor. Proc. VLDB Endow. 17, 6 (2024), 1405–1417. https://www.vldb.org/pvldb/vol17/ p1405-yuan.pdf

    2024

  14. [22]

    Ali Davoudian, Liu Chen, and Mengchi Liu. 2018. A survey on NoSQL stores. ACM Computing Surveys (CSUR) 51, 2 (2018), 1–43

    2018

  15. [23]

    Niv Dayan, Manos Athanassoulis, and Stratos Idreos. 2017. Monkey: Optimal navigable key-value store. In Proceedings of the 2017 ACM International Conference on Management of Data . 79–94

    2017

  16. [24]

    Niv Dayan and Stratos Idreos. 2018. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD ’18). Association for Computing Machi...

    2018

  17. [25]

    Niv Dayan and Moshe Twitto. 2021. Chucky: A Succinct Cuckoo Filter for LSM-Tree. In Proceedings of the 2021 International Conference on Management of Data . 365–378

    2021

  18. [26]

    Niv Dayan, Tamar Weiss, Shmuel Dashevsky, Michael Pan, Edward Bortnikov, and Moshe Twitto. 2022. Spooky: granulating LSM-tree compactions correctly. Proceedings of the VLDB Endowment 15, 11 (2022), 3071–3084

    2022

  19. [27]

    Dean De Leo and Peter Boncz. 2021. Teseo and the analysis of structural dynamic graphs. Proceedings of the VLDB Endowment 14, 6 (2021), 1053–1066

    2021

  20. [28]

    DGraph. 2024. DGraph. https://dgraph.io/

    2024

  21. [29]

    Ahmed Eldawy, Vagelis Hristidis, Saheli Ghosh, Majid Saeedan, Akil Sevim, AB Siddique, Samriddhi Singla, Ganesh Sivaram, Tin Vu, and Yaming Zhang. 2021. Beast: Scalable exploratory analytics on spatio-temporal data. InProceedings of the 30th ACM International Conference on Inf...

    2021

  22. [30]

    Facebook. 2024. Merge Operator. https://github.com/facebook/rocksdb/wiki/Merge-Operator

    2024

  23. [31]

    Facebook. 2024. MyRocks. https://myrocks.io/

    2024

  24. [32]

    Facebook. 2024. RocksDB. https://github.com/facebook/rocksdb

    2024

  25. [33]

    Wenfei Fan. 2022. Big graphs: challenges and opportunities. Proceedings of the VLDB Endowment 15, 12 (2022), 3782–3797

    2022

  26. [34]

    Wenfei Fan, Tao He, Longbin Lai, Xue Li, Yong Li, Zhao Li, Zhengping Qian, Chao Tian, Lei Wang, Jingbo Xu, et al

  27. [35]

    Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. KÙZU graph database management system. In The Conference on Innovative Data Systems Research

    2023

  28. [36]

    Scott Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. 2020. A large-scale database for graph representation learning. arXiv preprint arXiv:2011.07682 (2020)

    2020 arXiv

  29. [37]

    Per Fuchs, Domagoj Margan, and Jana Giceva. 2022. Sortledton: a universal, transactional graph data structure. Proceedings of the VLDB Endowment 15, 6 (2022), 1173–1186

    2022

  30. [38]

    Wook-Shin Han, Sangyeon Lee, Kyungyeol Park, Jeong-Hoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. 2013. TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discover...

    2013

  31. [39]

    Jiamin Hou, Zhanhao Zhao, Zhouyu Wang, Wei Lu, Guodong Jin, Dong Wen, and Xiaoyong Du. 2024. AeonG: An Efficient Built-in Temporal Support in Graph Databases. arXiv:cs.DB/2304.12212

    2024 arXiv

  32. [40]

    Gui Huang, Xuntao Cheng, Jianying Wang, Yujie Wang, Dengcheng He, Tieying Zhang, Feifei Li, Sheng Wang, Wei Cao, and Qiang Li. 2019. X-Engine: An optimized storage engine for large-scale E-commerce transaction processing. In Proceedings of the 2019 International Conference on ...

    2019

  33. [41]

    Haoyu Huang and Shahram Ghandeharizadeh. 2021. Nova-LSM: a distributed, component-based LSM-tree key-value store. In Proceedings of the 2021 International Conference on Management of Data . 749–763

    2021

  34. [42]

    Kai Huang, Haibo Hu, Qingqing Ye, Kai Tian, Bolong Zheng, and Xiaofang Zhou. 2023. TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–26

    2023

  35. [43]

    Kai Huang, Houdong Liang, Chongchong Yao, Xi Zhao, Yue Cui, Yao Tian, Ruiyuan Zhang, and Xiaofang Zhou. 2023. VisualNeo: Bridging the Gap between Visual Query Interfaces and Graph Query Engines. Proceedings of the VLDB Endowment 16, 12 (2023), 4010–4013

    2023

  36. [44]

    Kai Huang, Qingqing Ye, Jing Zhao, Xi Zhao, Haibo Hu, and Xiaofang Zhou. 2022. VINCENT: towards efficient exploratory subgraph search in graph databases. Proceedings of the VLDB Endowment 15, 12 (2022), 3634–3637

    2022

  37. [45]

    Andy Huynh, Harshal Chaudhari, Evimaria Terzi, and Manos Athanassoulis. 2021. Endure: A Robust Tuning Paradigm for LSM Trees Under Workload Uncertainty. arXiv preprint arXiv:2110.13801 (2021)

    2021 arXiv

  38. [46]

    Alexandru Iosup, Tim Hegeman, Wing Lung Ngai, Stijn Heldens, Arnau Prat-Pérez, Thomas Manhardto, Hassan Chafio, Mihai Capotă, Narayanan Sundaram, Michael Anderson, Ilie Gabriel Tănase, Yinglong Xia, Lifeng Nai, and Peter Boncz. 2016. LDBC graphalytics: a benchmark for large-sc...

    2016

  39. [47]

    Taewoo Kim, Alexander Behm, Michael Blow, Vinayak Borkar, Yingyi Bu, Michael J Carey, Murtadha Hubail, Shiva Jahangiri, Jianfeng Jia, Chen Li, et al. 2020. Robust and efficient memory management in Apache AsterixDB. Software: Practice and Experience 50, 7 (2020), 1114–1151

    2020

  40. [48]

    Young-Seok Kim, Taewoo Kim, Michael J Carey, and Chen Li. 2017. A comparative study of log-structured merge- tree-based spatial indexes for big data. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE) . IEEE, 147–150

    2017

  41. [49]

    Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In Proceedings of the 19th international conference on World wide web . 591–600

    2010

  42. [50]

    Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi:Large-Scale graph computation on just a PC. In 10th USENIX symposium on operating systems design and implementation (OSDI 12) . 31–46

    2012

  43. [51]

    Aapo Kyrola and Carlos Guestrin. 2014. GraphChi-DB: Simple design for a scalable graph database system–on just a PC. arXiv preprint arXiv:1403.0701 (2014)

    2014 arXiv

  44. [52]

    Cockroach Labs. 2024. CockroachDB. https://github.com/cockroachdb/cockroach

    2024

  45. [53]

    Avinash Lakshman and Prashant Malik. 2010. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review 44, 2 (2010), 35–40

    2010

  46. [54]

    Changji Li, Hongzhi Chen, Shuai Zhang, Yingqian Hu, Chao Chen, Zhenjie Zhang, Meng Li, Xiangchen Li, Dongqing Han, Xiaohui Chen, et al. 2022. ByteGraph: a high-performance distributed graph database in ByteDance. Proceedings of the VLDB Endowment 15, 12 (2022), 3306–3318

    2022

  47. [55]

    Hongzheng Li, Yingxia Shao, Junping Du, Bin Cui, and Lei Chen. 2022. An I/O-efficient disk-based graph system for scalable second-order random walk of large graphs. Proceedings of the VLDB Endowment 15, 8 (2022), 1619–1631

    2022

  48. [56]

    Meng Li, Deyi Chen, Haipeng Dai, Rongbiao Xie, Siqiang Luo, Rong Gu, Tong Yang, and Guihai Chen. 2022. Seesaw Counting Filter: An Efficient Guardian for Vulnerable Negative Keys During Dynamic Filtering. In Proceedings of the ACM Web Conference 2022. 2759–2767

    2022

  49. [57]

    Matteo Lissandrini, Martin Brugnara, and Yannis Velegrakis. 2018. Beyond macrobenchmarks: microbenchmark-based graph database evaluation. Proc. VLDB Endow. 12, 4 (dec 2018), 390–403. https://doi.org/10.14778/3297753.3297759

    2018

  50. [58]

    Junfeng Liu, Fan Wang, Dingheng Mo, and Siqiang Luo. 2024. Structural Designs Meet Optimality: Exploring Optimized LSM-tree Structures in A Colossal Configuration Space. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–26

    2024

  51. [59]

    Weifeng Liu and Brian Vinter. 2015. CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication. In Proceedings of the 29th ACM on International Conference on Supercomputing (ICS ’15) . Association for Computing Machinery, New York, NY, USA, 339–35...

    2015

  52. [60]

    Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Hariharan Gopalakrishnan, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau. 2017. Wisckey: Separating keys from values in ssd-conscious storage. ACM Transactions on Storage (TOS) 13, 1 (2017), 1–28

    2017

  53. [61]

    Chen Luo and Michael J Carey. 2020. Breaking down memory walls: adaptive memory management in LSM-based storage systems. Proceedings of the VLDB Endowment 14, 3 (2020), 241–254. Proc. ACM Manag. Data, Vol. 3, No. 1 (SIGMOD), Article 12. Publication date: February 2025. Aster: ...

    2020

  54. [62]

    Siqiang Luo, Zichen Zhu, Xiaokui Xiao, Yin Yang, Chunbo Li, and Ben Kao. 2023. Multi-Task Processing in Vertex- Centric Graph Systems: Evaluations and Insights.. In EDBT. 247–259

    2023

  55. [63]

    Steffen Maass, Changwoo Min, Sanidhya Kashyap, Woonhak Kang, Mohan Kumar, and Taesoo Kim. 2017. Mosaic: Processing a Trillion-Edge Graph on a Single Machine. In Proceedings of the Twelfth European Conference on Computer Systems (EuroSys ’17). Association for Computing Machiner...

    2017

  56. [64]

    Qizhong Mao, Mohiuddin Abdul Qader, and Vagelis Hristidis. 2020. Comprehensive comparison of LSM architectures for spatial data. In 2020 IEEE International Conference on Big Data (Big Data) . IEEE, 455–460

    2020

  57. [65]

    Dingheng Mo, Fanchao Chen, Siqiang Luo, and Caihua Shan. 2023. Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads. Proceedings of the ACM on Management of Data 1, 3 (2023), 1–25

    2023

  58. [66]

    Bruce Momjian. 2001. PostgreSQL: introduction and concepts . Vol. 192. Addison-Wesley New York

    2001

  59. [67]

    Robert Morris. 1978. Counting large numbers of events in small registers. Commun. ACM 21, 10 (1978), 840–842

    1978

  60. [68]

    Thomas Neumann and Michael J Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance.. In CIDR, Vol. 20. 29

    2020

  61. [69]

    Giuseppe Ottaviano and Rossano Venturini. 2014. Partitioned elias-fano indexes. InProceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval . 273–282

    2014

  62. [70]

    Tarikul Islam Papon, Taishan Chen, Shuo Zhang, and Manos Athanassoulis. 2024. CAVE: Concurrency-Aware Graph Processing on SSDs. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–26

    2024

  63. [71]

    PingCAP. 2024. TiDB. https://github.com/pingcap/tidb

    2024

  64. [72]

    Mohiuddin Abdul Qader, Shiwen Cheng, and Vagelis Hristidis. 2018. A comparative study of secondary indexing techniques in LSM-based NoSQL databases. In Proceedings of the 2018 International Conference on Management of Data . 551–566

    2018

  65. [73]

    Mark Raasveldt and Hannes Mühleisen. 2019. Duckdb: an embeddable analytical database. In Proceedings of the 2019 International Conference on Management of Data . 1981–1984

    2019

  66. [74]

    Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. Pebblesdb: Building key-value stores using fragmented log-structured merge trees. In Proceedings of the 26th Symposium on Operating Systems Principles . 497–514

    2017

  67. [75]

    Pandian Raju, Soujanya Ponnapalli, Evan Kaminsky, Gilad Oved, Zachary Keener, Vijay Chidambaram, and Ittai Abraham. 2018. mLSM: Making authenticated storage faster in ethereum. In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18)

    2018

  68. [76]

    Kai Ren, Qing Zheng, Joy Arulraj, and Garth Gibson. 2017. SlimDB: A space-efficient key-value storage engine for semi-sorted data. Proceedings of the VLDB Endowment 10, 13 (2017), 2037–2048

    2017

  69. [77]

    Marko A Rodriguez. 2015. The gremlin graph traversal machine and language (invited talk). In Proceedings of the 15th Symposium on Database Programming Languages . 1–10

    2015

  70. [78]

    Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. 2013. X-stream: Edge-centric graph processing using streaming partitions. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles . 472–488

    2013

  71. [79]

    Benedek Rozemberczki and Rik Sarkar. 2021. Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings. arXiv:cs.SI/2101.03091

    2021 arXiv

  72. [80]

    Sherif Sakr, Faisal Moeen Orakzai, Ibrahim Abdelaziz, and Zuhair Khayyat. 2016. Large-scale graph processing using Apache Giraph. Springer

    2016

  73. [81]

    Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, and Manos Athanassoulis. 2020. Lethe: A tunable delete- aware LSM engine. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . 893–908

    2020

  74. [82]

    Russell Sears and Raghu Ramakrishnan. 2012. bLSM: a general purpose log structured merge tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data . 217–228

    2012

  75. [83]

    Jifan Shi, Biao Wang, and Yun Xu. 2024. Spruce: a Fast yet Space-saving Structure for Dynamic Graph Storage. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–26

    2024

  76. [84]

    Jaewoo Shin, Jianguo Wang, and Walid G Aref. 2021. The LSM RUM-tree: a log structured merge R-tree for update- intensive spatial workloads. In 2021 IEEE 37th international conference on data engineering (ICDE) . IEEE, 2285–2290

    2021

  77. [85]

    Li Su, Xiaoming Qin, Zichao Zhang, Rui Yang, Le Xu, Indranil Gupta, Wenyuan Yu, Kai Zeng, and Jingren Zhou

  78. [86]

    Tin Vu, Ahmed Eldawy, Vagelis Hristidis, and Vassilis Tsotras. 2021. Incremental partitioning for efficient spatial data analytics. Proceedings of the VLDB Endowment 15, 3 (2021), 713–726

    2021

  79. [87]

    Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High- Dimensional Vector Similarity Search on Data Segment. Proceedin...

    2024

  80. [88]

    Min Wu, Xinglu Yi, Hui Yu, Yu Liu, and Yujue Wang. 2022. Nebula Graph: An open source distributed graph database. arXiv preprint arXiv:2206.07278 (2022)

    2022 arXiv

  81. [89]

    Xingbo Wu, Yuehai Xu, Zili Shao, and Song Jiang. 2015. LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data Items. In 2015 USENIX Annual Technical Conference (USENIX ATC 15) . 71–82

    2015

  82. [90]

    Yi Xu, Henry Zhu, Prashant Pandey, Alex Conway, Rob Johnson, Aishwarya Ganesan, and Ramnatthan Alagappan

  83. [91]

    Hao Yan, Shuai Ding, and Torsten Suel. 2009. Inverted index compression and query processing with optimized document ordering. In Proceedings of the 18th international conference on World wide web . 401–410

    2009

  84. [92]

    Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics . 1–8

    2012

  85. [93]

    Weiping Yu, Siqiang Luo, Zihao Yu, and Gao Cong. 2024. CAMAL: Optimizing LSM-trees via Active Learning. Proceedings of the ACM on Management of Data 2, 4 (2024), 1–26

    2024

  86. [94]

    Yu, Geoffrey X and Markakis, Markos and Kipf, Andreas and Larson, Per-Åke and Minhas, Umar Farooq and Kraska, Tim. 2022. TreeLine: an update-in-place key-value store for modern storage. Proceedings of the VLDB Endowment 16, 1 (2022), 99–112

    2022

  87. [95]

    Teng Zhang, Jian Tan, Xin Cai, Jianying Wang, Feifei Li, and Jianling Sun. 2022. SA-LSM: optimize data layout for LSM-tree based storage using survival analysis. Proceedings of the VLDB Endowment 15, 10 (2022), 2161–2174

    2022

  88. [96]

    Xin Zhang, Qizhong Mao, Ahmed Eldawy, Vagelis Hristidis, and Yihan Sun. 2022. Bi-directional Log-Structured Merge Tree. In Proceedings of the 34th International Conference on Scientific and Statistical Database Management . 1–4

    2022

  89. [97]

    Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph:Large-Scale graph processing on a single machine using 2-level hierarchical partitioning. In 2015 USENIX Annual Technical Conference (USENIX ATC 15) . 375–386

    2015

  90. [98]

    Xiaoke Zhu, Yang Liu, Shuhao Liu, and Wenfei Fan. 2023. MiniGraph: Querying Big Graphs with a Single Machine. Proceedings of the VLDB Endowment 16, 9 (2023), 2172–2185

    2023

  91. [99]

    Zeyang Zhuang, Penghui Li, Pingchuan Ma, Wei Meng, and Shuai Wang. 2023. Testing Graph Database Systems via Graph-Aware Metamorphic Relations. Proceedings of the VLDB Endowment 17, 4 (2023), 836–848. Received July 2024; revised September 2024; accepted November 2024 Proc. ACM ...

    2023

  92. [2021]

    Proceedings of the VLDB Endowment 14, 12 (2021), 2879–2892

    GraphScope: a unified engine for big graph processing. Proceedings of the VLDB Endowment 14, 12 (2021), 2879–2892

    2021

  93. [2022]

    Proceedings of the VLDB Endowment 15, 10 (2022), 2045–2057

    Banyan: a scoped dataflow engine for graph query service. Proceedings of the VLDB Endowment 15, 10 (2022), 2045–2057

    2022

  94. [2023]

    Proceedings of the VLDB Endowment 16, 13 (2023), 4324–4338

    GraphOS: Towards Oblivious Graph Processing. Proceedings of the VLDB Endowment 16, 13 (2023), 4324–4338

    2023

  95. [2024]

    In 22nd USENIX Conference on File and Storage Technologies (FAST 24)

    IONIA:High-Performance Replication for Modern Disk-based KV Stores. In 22nd USENIX Conference on File and Storage Technologies (FAST 24). 225–241

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.