diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -159,6 +159,8 @@
 
     //! Index in mempool's vTxHashes
     mutable size_t vTxHashesIdx;
+    //! epoch when last touched, useful for graph algorithms
+    mutable uint64_t m_epoch;
 };
 
 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
@@ -481,6 +483,8 @@
     mutable bool blockSinceLastRollingFeeBump;
     //! minimum fee to get into the pool, decreases exponentially
     mutable double rollingMinimumFeeRate;
+    mutable uint64_t m_epoch;
+    mutable bool m_has_epoch_guard;
 
     void trackPackageRemoved(const CFeeRate &rate) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
@@ -824,6 +828,59 @@
      */
     void removeUnchecked(txiter entry, MemPoolRemovalReason reason)
         EXCLUSIVE_LOCKS_REQUIRED(cs);
+
+public:
+    /**
+     * EpochGuard: RAII-style guard for using epoch-based graph traversal
+     * algorithms. When walking ancestors or descendants, we generally want to
+     * avoid visiting the same transactions twice. Some traversal algorithms use
+     * std::set (or setEntries) to deduplicate the transaction we visit.
+     * However, use of std::set is algorithmically undesirable because it both
+     * adds an asymptotic factor of O(log n) to traverals cost and triggers O(n)
+     * more dynamic memory allocations.
+     *     In many algorithms we can replace std::set with an internal mempool
+     * counter to track the time (or, "epoch") that we began a traversal, and
+     * check + update a per-transaction epoch for each transaction we look at to
+     * determine if that transaction has not yet been visited during the current
+     * traversal's epoch.
+     *     Algorithms using std::set can be replaced on a one by one basis.
+     * Both techniques are not fundamentally incompatible across the codebase.
+     * Generally speaking, however, the remaining use of std::set for mempool
+     * traversal should be viewed as a TODO for replacement with an epoch based
+     * traversal, rather than a preference for std::set over epochs in that
+     * algorithm.
+     */
+    class EpochGuard {
+        const CTxMemPool &pool;
+
+    public:
+        EpochGuard(const CTxMemPool &in);
+        ~EpochGuard();
+    };
+    // N.B. GetFreshEpoch modifies mutable state via the EpochGuard construction
+    // (and later destruction)
+    EpochGuard GetFreshEpoch() const EXCLUSIVE_LOCKS_REQUIRED(cs);
+
+    /**
+     * visited marks a CTxMemPoolEntry as having been traversed
+     * during the lifetime of the most recently created EpochGuard
+     * and returns false if we are the first visitor, true otherwise.
+     *
+     * An EpochGuard must be held when visited is called or an assert will be
+     * triggered.
+     *
+     */
+    bool visited(txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
+        assert(m_has_epoch_guard);
+        bool ret = it->m_epoch >= m_epoch;
+        it->m_epoch = std::max(it->m_epoch, m_epoch);
+        return ret;
+    }
+
+    bool visited(std::optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
+        assert(m_has_epoch_guard);
+        return !it || visited(*it);
+    }
 };
 
 /**
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -32,7 +32,7 @@
     : tx(_tx), nFee(_nFee), nTxSize(tx->GetTotalSize()),
       nUsageSize(RecursiveDynamicUsage(tx)), nTime(_nTime),
       entryHeight(_entryHeight), spendsCoinbase(_spendsCoinbase),
-      sigOpCount(_sigOpsCount), lockPoints(lp) {
+      sigOpCount(_sigOpsCount), lockPoints(lp), m_epoch(0) {
     nCountWithDescendants = 1;
     nSizeWithDescendants = GetTxSize();
     nSigOpCountWithDescendants = sigOpCount;
@@ -151,8 +151,6 @@
     // setMemPoolChildren will be updated, an assumption made in
     // UpdateForDescendants.
     for (const TxId &txid : reverse_iterate(txidsToUpdate)) {
-        // we cache the in-mempool children to avoid duplicate updates
-        setEntries setChildren;
         // calculate children from mapNextTx
         txiter it = mapTx.find(txid);
         if (it == mapTx.end()) {
@@ -162,19 +160,23 @@
         auto iter = mapNextTx.lower_bound(COutPoint(txid, 0));
         // First calculate the children, and update setMemPoolChildren to
         // include them, and update their setMemPoolParents to include this tx.
-        for (; iter != mapNextTx.end() && iter->first->GetTxId() == txid;
-             ++iter) {
-            const TxId &childTxId = iter->second->GetId();
-            txiter childIter = mapTx.find(childTxId);
-            assert(childIter != mapTx.end());
-            // We can skip updating entries we've encountered before or that are
-            // in the block (which are already accounted for).
-            if (setChildren.insert(childIter).second &&
-                !setAlreadyIncluded.count(childTxId)) {
-                UpdateChild(it, childIter, true);
-                UpdateParent(childIter, it, true);
+        // we cache the in-mempool children to avoid duplicate updates
+        {
+            const auto epoch = GetFreshEpoch();
+            for (; iter != mapNextTx.end() && iter->first->GetTxId() == txid;
+                 ++iter) {
+                const TxId &childTxId = iter->second->GetId();
+                txiter childIter = mapTx.find(childTxId);
+                assert(childIter != mapTx.end());
+                // We can skip updating entries we've encountered before or that
+                // are in the block (which are already accounted for).
+                if (!visited(childIter) &&
+                    !setAlreadyIncluded.count(childTxId)) {
+                    UpdateChild(it, childIter, true);
+                    UpdateParent(childIter, it, true);
+                }
             }
-        }
+        } // release epoch guard for UpdateForDescendants
         UpdateForDescendants(it, mapMemPoolDescendantsToUpdate,
                              setAlreadyIncluded);
     }
@@ -387,7 +389,8 @@
     assert(int(nSigOpCountWithAncestors) >= 0);
 }
 
-CTxMemPool::CTxMemPool() : nTransactionsUpdated(0) {
+CTxMemPool::CTxMemPool()
+    : nTransactionsUpdated(0), m_epoch(0), m_has_epoch_guard(false) {
     // lock free clear
     _clear();
 
@@ -1424,3 +1427,19 @@
                    std::chrono::hours{
                        gArgs.GetArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY)});
 }
+
+CTxMemPool::EpochGuard CTxMemPool::GetFreshEpoch() const {
+    return EpochGuard(*this);
+}
+
+CTxMemPool::EpochGuard::EpochGuard(const CTxMemPool &in) : pool(in) {
+    assert(!pool.m_has_epoch_guard);
+    ++pool.m_epoch;
+    pool.m_has_epoch_guard = true;
+}
+
+CTxMemPool::EpochGuard::~EpochGuard() {
+    // prevents stale results being used
+    ++pool.m_epoch;
+    pool.m_has_epoch_guard = false;
+}