Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Beyond Heuristics: I/O-oriented Algorithms and Structures with Performance Guarantees

Tao, Y.

    System development often results in algorithms and access methods that are heuristic in nature. They have the merits of being easy to understand, simple to implement, and reasonably effective on many real datasets. Nonetheless, common criticism is that they typically come with no non-trivial performance guarantees. For years the database community has been striving to discover methods that are small and sweet. That is, such a method should be implementable in practice (i.e., small), and in the mean time, must retain attractive efficiency even in the worst case (i.e., sweet). This talk serves as an introduction to the current progress in the research of small and sweet algorithms and data structures. We will review solutions to several classic problems including spatial join, skyline retrieval, range searching, and so on. Special discussion will be dedicated to techniques generally useful for obtaining good worst-case I/O bounds.
Cite as: Tao, Y. (2012). Beyond Heuristics: I/O-oriented Algorithms and Structures with Performance Guarantees. In Proc. Australasian Database Conference (ADC 2012) Melbourne, Australia. CRPIT, 124. Zhang, R. and Zhang, Y. Eds., ACS. 3
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS