VII

Applications

49IP Router Tables Sartaj Sahni, Kun Suk Kim and Haibin Lu

Introduction•Longest Matching-Prefix•Highest-Priority Matching•Most-Specific-Range Matching•Acknowledgments•References

50Multi-Dimensional Packet Classification Pankaj Gupta

Introduction•Performance Metrics for Classification Algorithms•Classification Algorithms•Summary•References

51Data Structures in Web Information Retrieval Monika Henzinger

Introduction•Inverted Indices•Fingerprints•Finding Near-Duplicate Documents•Conclusions•References

52The Web as a Dynamic Graph S. N. Maheshwari

Introduction•Experimental Observations•Theoretical Growth Models•Properties of Web Graphs and Web Algorithmics•Conclusions•References

53Layout Data Structures Dinesh P. Mehta

Introduction•VLSI Technology•Layout Data Structures: An Overview•Corner Stitching•Corner Stitching Extensions•Quad Trees and Variants•Concluding Remarks•Acknowledgments•References

54Floorplan Representation in VLSI Zhou Feng, Bo Yao and Chung-Kuan Cheng

Introduction•Graph Based Representations•Placement Based Representations•Relationships of the Representations•Rectilinear Shape Handling•Conclusions•Acknowledgments•References

55Computer Graphics Dale McMullin and Alyn Rockwood

Introduction•Basic Applications•Data Structures•Applications of Previously Discussed Structures•References

56Geographic Information Systems Bernhard Seeger and Peter Widmayer

Geographic Information Systems:What They Are All About•Space Filling Curves: Order in Many Dimensions•Spatial Join•Models, Toolboxes, and Systems for Geographic Information•Acknowledgment•References

57Collision Detection Ming C. Lin and Dinesh Manocha

Introduction•Convex Polytopes•General Polygonal Models•Penetration Depth Computation•Large Environments•References

58Image Data Structures S. S. Iyengar, V. K. Vaishnavi and S. Gunasekaran

Introduction•What is Image Data?•Quadtrees•Virtual Quadtrees•Quadtrees and R-trees•Octrees•Translation Invariant Data Structure (TID)•Content-Based Image Retrieval System•Summary•Acknowledgments•References

59Computational Biology Paolo Ferragina, Stefan Kurtz, Stefano Lonardi and Giovanni Manzini

Introduction•Discovering Unusual Words•ComparingWhole Genomes•The FM-index•References

60Data Structures for Cheminformatics Dinesh P. Mehta and John D. Crabtree

Introduction•Exact Searches•Chemical Fingerprints and Similarity Search•References

61Elimination Structures in Scientific Computing Alex Pothen and Sivan Toledo

The Elimination Tree•Applications of Etrees•The Clique Tree•Clique Covers and Quotient Graphs•Column Elimination Trees and Elimination DAGS•Acknowledgments•References

62Data Structures for Databases Joachim Hammer and Markus Schneider

Overview of the Functionality of a Database Management System•Data Structures for Query Processing•Data Structures for Buffer Management•Data Structures for Disk Space Management•Conclusion•References

63Data Structures for Big Data Stores Arun A. Ravindran and Dinesh P. Mehta

Introduction•Data Models•Partitioning•Replication and Consistency•Persistence•Concurrency•Conclusion•References

64Data Mining Vipin Kumar, Pang-Ning Tan and Michael Steinbach

Introduction•Classification•Association Analysis•Clustering•Conclusion•Acknowledgments•References

65Computational Geometry: Fundamental Structures Mark de Berg and Bettina Speckmann

Introduction•Arrangements•Convex Hulls•Voronoi Diagrams•Triangulations•References

66Computational Geometry: Proximity and Location Sunil Arya and David M. Mount

Introduction•Point Location•Proximity Structures•Nearest Neighbor Searching•Sources and Related Material•Acknowledgments•References

67Computational Geometry: Generalized (or Colored) Intersection Searching Prosenjit Gupta, Ravi Janardan, Saladi Rahul and Michiel Smid

Geometric Intersection Searching Problems•Summary of Known Results•Techniques•Conclusion and Future Directions•Acknowledgments•References