Microsoft Corporation
GENERATION AND TRAVERSAL OF A HIERARCHICAL INDEX STRUCTURE FOR EFFICIENT DATA RETRIEVAL

Abstract:

Methods, systems, apparatuses, and computer program products are described herein for the generation and traversal of a hierarchical index structure. The structure indexes search keys from data ingested from different data sources and enables efficient retrieval of the keys. As data is ingested, index nodes are generated at the lowest level of the structure. The nodes are analyzed to determine whether such nodes comprise duplicate keys. Responsive to doing so, a new index node is generated located at a higher level of the structure. This process results in a DAG comprising orphan nodes including different search keys. When processing a query for search keys, the orphan index nodes are initially analyzed for the keys. Upon finding a search key, its child nodes are recursively searched until location information specifying the location of ingested data in which the search key is located is found.