Proximity Search in Databases

Roy Goldman, Narayanan Shivakumar,

Suresh Venkatasubramanian, Hector Garcia-Molina

1998

 

 

 

מוצג ע"י: אייל מישור

הקדמה

  1. מה זה proximity search ?

  2. במה מתאפיין חיפוש כזה ?

  3. מה החידוש במאמר ?

  4. איך עושים את זה ?

    5. דוגמה

    Internet Movie Database (www.imdb.com)

    over 140,000 movies

    over 500,000 film industry workers

    Queries Structure:

    Find <keyword> Near <keyword>

    דוגמה - המשך

    הבעיה

    ranking objects in the Find set based on their proximity to objects in the Near set

     

     

     

     

     

    ה-framework של הפתרון

     

    IMDB

    IMDB

    חישוב ה-proximity

  5. הגדרת ה-bond:

  6. הגדרת ה-score:

    7. מציאת המרחקים

  7. בזמן חיפוש (Dijkstra’s single-source shortest path)

  8. חישוב מקדים (Floyd-Warshall’s all-pairs shortest path)

  9. חישוב מקדים באמצעות Self Joins ........

    10.  

     

     

    Self-Joins

    Hub Indexing

    Constructing Hub Index

  10. נתון H

  11. נבנה את Dist החדשה:


  12. נחשב מרחקים קצרים ב-H ע”י אתחול מ-Dist ושימוש ב-Floyd-Warshall

    13. בחירת ה-Hubs

  13. נתונה מטריצה בגודל M לשמירת המרחקים בין ה-hub-ים.

  14. בחר שורש M צמתים עם הדרגה הגבוהה ביותר להיות
    hub-ים

    15.  

     

     

    Performance Experiments

  15. Sun SPARC/Ultra II (2x200 Mhz) running SunOS 5.6, with 256 Mbs RAM, and 18 Gbs local disk space

  16. IMDB - 4MB of 1997 films.

    17.  

     

     

     

    S = 10; no more than 2.5% hubs

    S = 10; no more than 2.5% hubs

    K= 12 no more than 2.5% hubs

    S = 10; K = 12

    הרחבות

  17. שיפור השיטה למציאת hubs

  18. תמיכה ב-queries מורכבים יותר (הוספת not, קינון)

  19. הכנסת proximity search ל-SQL

  20. עדכון אינקרמנטלי של האינדקסים כשהנתונים משתנים

  21. שמירת המסלולים הקצרים ולא רק המרחקים.