Fast query on hierarchical databases

Prof. Oded Shmueli | Computer Science

The Technology

Hierarchical databases, which include tree structured ones such as XML documents, are commonly employed in information retrieval systems. However, previous hierarchical processing algorithms perform poorly in multi-threaded environments, leading to slow data retrieval. Viewing the database as a collection of streams, which are processed in parallel, we arrive at superior performance.
Another related challenge lies in efficiently processing queries on the more complex graph databases using SIMD technology, enabling massive parallelism on SIMD hardware, especially via GPUs. While there are parallel solutions using multi-threaded CPU computing platforms, the technology here focuses on a GPU parallel algorithm to tackle this issue.
Our novel approach involves leveraging the thread ID to determine the specific data portion that a particular thread will handle during pattern matching. Although the number of bits in a thread ID is quite limited, we developed methods to overcome this data representation limitation. These methods are optimized for the SIMD architectures, particularly for GPUs.


  • Minimal run time for queries over hierarchical databases

Applications and Opportunities

  • Improve performance of database systems that support graph structured documents in the multi-core GPU environment
  • Processing queries over XML database systems
arrow Business Development Contacts
Shikma Litmanovitz
Director of Business Development, Physical Science