Efficiently find marked referenced records-CodePudding

The

CodePudding user response：

To find all the marked records that are reachable from a given record is equivalent counting the marked records in the component that contains the given record.

This can be done with breadth first or depth first search.

There is no faster algorithm. To improve your performance I believe you need to:

Implement an efficient search code using an optimising compiler

Switch to a high performance database engine

Optimize your queries. ( Do not read records one at a time! )

Optimize your hardware configuration ( no networks, no spinning disks )

CodePudding user response：

This problem is related to fully dynamic transitive closure. I'm not intimately familiar with the research literature on the latter (probably most of which is not practical), but there is one algorithmic trick that you might not know about, related to your "maximum depth" idea.

Add a binary flag ("open" or "closed") to each node, and store both incoming and outgoing arcs. The rules are, every node that can reach an open node is open, and (equivalently) every node that can be reached by a closed node is closed. Each closed node also stores the set of marked nodes that it can reach. To query, traverse forward (outgoing arcs) from the queried node via open nodes, stopping at closed nodes. To update, traverse backward (incoming arcs) from the updated node via closed nodes, stopping at open nodes.

A closed node with incoming arcs from open nodes only can be converted to open. An open node with outgoing arcs to closed nodes only can be converted to closed. Conversion requires updates proportional to (in- or out-) degree. At this scale, I would suggest dumping the whole graph periodically and computing a reasonable set of adjustments in main memory.