Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Logarithmic merge

  • Auxiliary and main index: index construction time is O(T2) as each posting is touched in each merge.

  • Logarithmic merge: Each posting is merged O(log T) times, so complexity is O(T log T)

  • So logarithmic merge is much more efficient for index construction

  • But query processing now requires the merging of O(log T) indexes

    • Whereas it is O(1) if you just have a main and auxiliary index


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.