addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscontroller-playcrossdots-three-verticaleditemptyheartexporteye-with-lineeyefacebookfolderfullheartglobegmailgooglegroupshelp-with-circleimageimagesinstagramFill 1light-bulblinklocation-pinm-swarmSearchmailmessagesminusmoremuplabelShape 3 + Rectangle 1ShapeoutlookpersonJoin Group on CardStartprice-ribbonprintShapeShapeShapeShapeImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruserwarningyahoo

Bay Area Search - Roberto Konow

  • Aug 27, 2014 · 6:30 PM


Faster and Smaller Inverted Indexes with Treaps


We introduce a new representation of the inverted index that performs faster ranked unions and intersections while using less space. Our index is based on the treap data structure, which allows us to intersect/merge the document identifiers while simultaneously thresholding by frequency, instead of the costlier two-step classical processing methods. Further, the treap invariants allow us to elegantly encode differentially both document identifiers and frequencies. Results show that the space consumption is below 10% of the size of the corpus and the index performs queries up to twice as fast than previous compact representations, which in addition require more space.


Roberto Konow is a  computer science Ph.D candidate and part-time researcher and lecturer at Universidad Diego Portales. His Ph.D topic and interests are related to Algorithms, Data Structures, Compression and Information Retrieval. His Ph.D advisor is Dr. Gonzalo Navarro. Before he started his  Ph.D, he worked in a Japanese company, Skillupjapan, as research engineer in projects related to recommender systems. He is currently a Ph.D Technical Intern at eBay working on optimizations for the search engine. 


6:30 Eat & Greet

7:00 Talk - Great speakers, good food, free beer.

Event will be held at the eBay campus just off 17/880 @ Hamilton in the main Community building.  Look for lobby/flagpole.

Wifi: eBayGuest/BuyItNow!

I'm always looking for speakers.  Please suggest speakers or topics you would like to hear.


Join or login to comment.

  • al f.

    August 28, 2014

    • Thomas P.

      Thanks very much for the recording and for the sharing!

      September 10, 2014

  • Thomas P.

    The slides deck has been uploaded here:

    September 10, 2014

  • Ram H.

    Thank you for the wonderful presentation and great work you are doing. I learnt quite a lot and detailed pointer to implementing treaps.

    August 29, 2014

  • Thomas P.

    We will start late due to a fire on the highway that blocked the traffic.

    August 27, 2014

  • Roberto K.

    You are welcome.
    Sure, I will be there at 6:00 PM, if you want to ask me something.

    August 25, 2014

  • Xiaoyun W.

    Thanks, Roberto, Do you happen to have slides on the query processing part from SIGIR? It is a bit dense in the paper, and I am wondering whether the slides will be a bit more easy to follow. Also, will you be there early enough for some questions on Wens? Xiaoyun

    August 25, 2014

  • Roberto K.

    Hello Xiaoyun,

    Here is a link of the unofficial version of the paper:

    And here is a link of the official one (but you need to have access to the ACM library)

    Thank you for your interest!

    August 25, 2014

  • Xiaoyun W.

    Hi, Roberto, Looks very interesting...

    Is it possible to share some pointers ahead of time? Like slide or papers so that we can get a bit more prepared? Thanks.


    August 24, 2014

Our Sponsors

  • eBay

    Providing Venue

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy