Systems and methods for discovering frequently accessed subtrees
AssigneeQisda Corporation
InventorsCheng-Enn Hsieh, Arbee Chen
Life of this patent
Estimating the term…
Abstract
A method for discovering frequently accessed subtrees, performed by an electronic apparatus, comprises the following steps. A request is received from a source. A global prefix tree (GPT) comprising multiple traversal paths is acquired, each traversal path representing one of a plurality of frequently accessed subtrees. A response comprising the GPT is transmitted to the source, thereby enabling the source to discover the frequently accessed subtrees based on the GPT. The GPT is generated in response to multiple data streams respectively comprising accessed nodes of a partially traversed theoretical tree.
Claims14
A method for discovering a plurality of frequently accessed subtrees, performed by an electronic apparatus, the electronic apparatus having a storage device and a processing unit for executing steps of the method, the method comprising the steps of:
- acquiring and storing a plurality of data streams in the storage device, the data streams respectively comprising accessed nodes of a partially traversed theoretical tree;
- generating an augmented prefix tree (APT) according to each of the acquired data streams;
- merging the generated APTs into a global prefix tree (GPT) comprising a plurality of first traversal paths and a plurality of second traversal paths, each of the first traversal paths representing a frequent subtree, and each of the second traversal paths representing a non-frequent subtree;
- and
- periodically removing the second traversal paths from the GPT.
A system for discovering frequently accessed subtrees, comprising:
- a processing unit;
- a storage module storing a plurality of data streams respectively comprising accessed nodes of a partially traversed theoretical tree;
- a subtree generation module executed by the processing unit, the subtree generation module acquiring the data streams from the storage module, generating an augmented prefix tree (APT) according to each of the acquired data streams, merging the generated APTs into a global prefix tree (GPT) and storing the GPT in the storage module, the GPT comprising a plurality of first traversal paths and a plurality of second traversal paths, each of the first traversal paths representing a frequent subtree, and each of the second traversal paths representing a non-frequent subtree;
- and
- a subtree maintenance module executed by the processing unit, the subtree maintenance module periodically removing the second traversal paths from the GPT and storing the resulting GPT in the storage module.
Dependencies are inferred from the claim text.